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

We prove the contrapositive. If $3\nmid a$, Euclidean division gives $a=3q+1$ or $a=3q+2$ for an integer $q$. Squaring gives respectively $a^2=3(3q^2+2q)+1$ or $a^2=3(3q^2+4q+1)+1$. Both have remainder $1$ upon division by $3$, so $3\nmid a^2$. Taking the contrapositive yields $3\mid a^2\Rightarrow 3\mid a$.