Prove that if $n$ is not divisible by $3$, then $n^2 \equiv 1 \pmod 3$

Question

I can see that it is true for all cases where $n$ is not divisible by $3$, such as $n = 1$, $n = 2$, $n = 4$, etc. However I can't figure out how to prove it.

Answer 1

There are three mutually exclusive cases for an integer $n$:

1. $n\equiv 0\pmod{3}$ (that is, $n$ is divisible by $3$);
2. $n\equiv 1\pmod{3}$
3. $n\equiv 2\pmod{3}$

In case 2, $n^2\equiv 1\pmod{3}$; in case 3, $$ n^2\equiv 4\equiv 1\pmod{3} $$

Just recall that from $a\equiv b\pmod{k}$ and $c\equiv d\pmod{k}$ you can deduce that $ac\equiv bd\pmod{k}$.

Answer 2

Any number $n\in\mathbb{Z}$ can be written as $n=3k+c$, where $c\in\lbrace 0,1,2\rbrace$. This is just saying that $n\equiv c\bmod 3$.

Now that we've written $n=3k+c$, let's try squaring this. This gives us $$n^2=(3k+c)^2=9k^2+6ck+c^2=3(k^2+2ck)+c^2.$$ Now, we know $c\neq 0$, so it follows that $c=1$ or $c=2$. Either way, $c^2\bmod 3=1$. So, we have that $$n^2\bmod 3=\underbrace{3(k^2+2ck)}_{0}\bmod 3+1\bmod 3=1\bmod 3.$$

Answer 3

Consider the following cases:

• $n\equiv\color\red1\pmod3 \implies n^2\equiv\color\red1^2\equiv3\cdot0+1\equiv1\pmod3$
• $n\equiv\color\red2\pmod3 \implies n^2\equiv\color\red2^2\equiv3\cdot1+1\equiv1\pmod3$

Answer 4

Hint:

Just observe that $2\equiv -1\mod3$.

Answer 5

We have to show that $3$ divides $(n-1)(n+1)$. Since $3$ does not divide $n$, the statement is equivalent to the fact that $3$ divides $(n-1)(n+1)n$ or $(n-1)n(n+1)$. This equivalence of statements can be observed from prime decomposition or can be proven directly. But $(n-1)n(n+1)$ is just product of $3$ consecutive numbers, so obviously it is divisible by $3$.

This proof is not as rigorous as others, but it gives you some alternative intuition related to the problem.