Prove or disprove: For every integer a, if a is not congruent to 0 (mod 3), the a^2 is congruent to 1 (mod 3)
Solution 1:
Hint $\ 3\, $ divides one of $\,a\!-\!1,\,a,\,a\!+\!1,\ $ so $\ 3\nmid a\,\Rightarrow\,3\mid(a\!-\!1)(a\!+\!1) = a^2\!-1$
Remark$\ $ Said modly, $\ {\rm mod}\ 3\!:\ a\not\equiv 0\,\Rightarrow\, a\equiv \pm 1\,\Rightarrow\, a^2\equiv 1$
Solution 2:
If $a$ is not a multiple of $3$, either one of these must hold:
$a \equiv 1 \pmod 3$
or $a \equiv 2 \pmod 3$
Basically, those are saying that the remainder on dividing $a$ by $3$ is either $1$ or $2$.
Now, the second can also be expressed as $a \equiv -1 \pmod 3$
So everything can be more concisely expressed as $a \equiv \pm 1 \pmod 3$,
allowing us to square easily giving: $a^2 \equiv 1 \pmod 3$.
Solution 3:
For the two cases I think one case is letting the integer be $(3n+1)$ and the other be $(3n+2)$. Squaring both reveals what you need I believe.
Solution 4:
For a in (mod 3), there are three different kinds of numbers:
- a = 3m
- a = 3m+1
- a = 3m+2
We can take the last 2 which aren't equal to 0 (mod 3)
The second one:
$$ a^2 = (3m+1)^2 $$ $$ = 9m^2 + 6m + 1 $$ $$ = 3(3m^2 + 2) + 1 $$ $$ = 3k + 1, k = 3m^2 + 2\in \Z^+ $$ $$ \equiv 1\mod 3 $$
The third one:
$$ a^2 = (3m+2)^2 $$ $$ = 9m^2 + 12m + 4 $$ $$ = 3(3m^2 + 4 + 1) + 1 $$ $$ = 3j + 1, j = 3m^2 + 4 + 1\in \Z^+ $$ $$ \equiv 1\mod 3 $$