How to prove if $3\nmid n$, then $n^2$ has a remainder $1$ when divided by $3$?

Question

Lets say: $n^2=3k+1$ ; $n\neq3$.

I'm trying to prove this by induction, therefore:

$(n+1)^2=n^2+2n+1=3k+2n+2$

Any suggestion on how to move foward?

Answer 1

You don't need induction for this.

Between 3 consecutive numbers $n-1$, $n$ and $n+1$ there is exactly on divisible by 3. In your case that is $n-1$ or $n+1$ so their product $(n-1)(n+1)=n^2-1$ is divisible by 3. So the remainder when $n^2$ is divided by 3 is 1.

Answer 2

You are close here and you need no direct induction: write $\;n=3k+a\;$ , with $\;a\in\{1,2\}\;$ , then

$$n^2=(3k+a)^2=9k^2+6ka+a^2=a^2\pmod 3$$

Now just check that both $\;1^2=2^2=1\pmod 3\;$ and we're done.

Answer 3

If 3 does not divide $n$, that means that $n$ has remainder 1 or 2 by division with 3.

So either $n=3k+1$ or $n=3k+2$.

In both cases we have $n^2=(3k+1)^2=9k^2+6k+1=3(3k^2+2k)+1\equiv 1\mod 3$

or $n^2=(3k+2)^2=3(3k^2+4k)+4=3(3k^2+4k)+3\cdot 1+1\equiv 1\mod 3$

Answer 4

We can see that $1^2\equiv 1\mod 3$ and $2^2\equiv 1\mod 3$. Now prove that $(a+3)^2\equiv a^2\mod 3$. Now by induction can you see that we have our result?

Answer 5

It's very simple using congruences modulo $3$: if $n\not\equiv 0\bmod 3$, then $n\equiv 1\;\text{ or }\;2\bmod 3$, so $$n^2\equiv 1^2=1\;\text{ or }\;2^2=4\equiv 1 \text{ again, }\bmod 3$$