For every integer $a$, if $a \not\equiv 0\pmod3$, then, $a^2\equiv 1\pmod3$.

Question

It is always confusing to prove with $\not\equiv$. Should I try contrapositive?

Answer 1

Well, in this case the contrapositive is "if $a^2$ is $\textit{not}$ congruent to $1$ mod $3$ then ..." which will cause you the same kind of problem.

In this case, you might just try working directly with the hypothesis. If $a$ is not congruent to $0$, then it has to be congruent to either $1$ or $2$, right? Consider each of these cases separately, and you should see why this is true.

Answer 2

HINT:

if $a$ is not divisible by $3$, then $a=3n+1$ or $a=3n+2$.

Calculate $a^2$, and take $\text{mod}3$ to conclude.

Answer 3

If $a \not\equiv 0 \bmod 3$ then either $a \equiv 1 \bmod 3$ or $a \equiv 2 \bmod 3$.

• If $a \equiv 1 \bmod 3$ then $a^2 \equiv 1^2 = 1\equiv 1 \bmod 3$.
• If $a \equiv 2 \bmod 3$ then $a^2 \equiv 2^2 = 4 \equiv 1 \bmod 3$.

Hence, if $a \not\equiv 0 \bmod 3$ then $a^2 \equiv 1 \bmod 3$.