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$

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$.

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.

For a in (mod 3), there are three different kinds of numbers:

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 $$