 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2016/discrete-mathematics-continuous-mathematics-and-probability/3/a/solution

3 ∤ a

a = 3 q + 1

a = 3 q + 2

for an integer

q

. Squaring gives respectively

a^{2} = 3 (3 q^{2} + 2 q) + 1

a^{2} = 3 (3 q^{2} + 4 q + 1) + 1

. Both have remainder

1

upon division by

3

, so

3 ∤ a^{2}

. Taking the contrapositive yields $3 ∣ a^{2} \Rightarrow 3 ∣ a$ .

 New to topics? Read the docs here!