Prove if $3$ does not divide $n$, then $n^2=1+3k$ for some integer $k$

Question

I am proving by cases but am getting confused. I am not sure if this leads to a contradiction or not.

Here's what I have so far:

Direct Proof. Suppose $3$ does not divide $n$.

Case 1: remainder upon division is $1$ then $n=3k+1$, for some integer $k$ and $n^2=(3k+1)^2$ ... this is where I am getting confused.

Case 2: remainder upon division is $2$ then $n=3k+2$ for some integer $k$ and $n^2=(3k+2)^2$ ... and here.

Because the problem says "If $3$ does not divide $n$, then $n^2=1+3k$" but this is not what I am getting. So does this result in a contradiction or not? And so is the proof false and I need to provide a counter example?

A little lost, thanks!

Answer 1

Note that$$(3k+2)^2=9k^2+12k+4=3m+4=3m+3+1=3(m+1)+1=3l+1$$

---

Or rewrite your integers as $$3k-1 , 3k, 3k+1$$

and then $$(3k-1)^2=9k^2-6k+1=3(9k^2-6k)+1=3p+1$$ I hope you can handle the rest!

Answer 2

It's as simple as:

If $n \nmid 3$, then $n \equiv 1$ or $2 \pmod 3$.

So $n^2 \equiv 1^2 = 1$ or $2^2 = 4 \equiv 1 \pmod 3$, i.e. $n^2 \equiv 1 \pmod 3$, giving the required result.