Prove that for every $n\in\mathbb{N}$, $n^2$ is divisible by 3 or has a form $3k+1$?

Question

I tried to do this by induction, but it doesn't make any sense:
$n^2=3k$ or $n^2=3k+1$

1. option: $(n+1)^2= 3k+2n+1$
2. option: $(n+1)^2= 3k+2n+2$

Is there any other way on proving this problem?

Answer 1

In terms of 3 n can only be two things:

$3k, 3k \pm 1$

The remainders of n divided by 3 are either $0$ and $\pm 1$

This is modular arithmetic in it's basic form. Expanding the first leads to a term divisible by $3$, expanding the second has terms divisible by 3 and then the $1^2$. Hence thy conjecture.

Answer 2

For some integer $m$, one of the following must be true:

1. $n = 3m$
2. $n = 3m + 1$
3. $n = 3m + 2$

In case $1$), it should be clear that $n^2$ is divisible by $3$.

In case $2$), we have $n^2 = (3m + 1)^2 = 9m^2 + 6m + 1 = 3(3m^2 + 2m) + 1$, so with $k = 3m^2 + 2m$, we have $n^2 = 3k + 1$.

Can you complete case $3$?

Answer 3

For all $n$ natural number, $n = 3k$ or $n=3k+1$ or $n=3k+2$

When $n=3k$, $n^2=9k^2=3(3k^2)$, thus is divisible by 3

When $n=3k+1$, $n^2=9k^2+6k+1=3(3k^2+2k)+1$, thus is in the form of $3n+1$

When $n=3k+2$, $n^2=9k^2+12k+4=3(3k^2+4k+1)+1$, thus is in the form of $3n+1$

Thus, covering all the cases and finishing the proof

Answer 4

$2=-1$ is not perfect square modulo $3$ because $3$ is not congruent to $1$ modulo $4$. This is a consequence of the quadratic reciprocity law. This leaves you with the two possibilities: $n^2 = 0$ (mod 3) or $n^2 = 1$ (mod 3).

Answer 5

Every $n \in \mathbb{N}$ must be of one of the following forms: $3k$ or $3k+1$ or $3k+2$

Can you see the following:

If $n$ is of the form $3k$, then $n^2$ is also of the form $3k$

If $n$ is of the form $3k + 1$, then $n^2$ is also of the form $3k + 1$

If $n$ is of the form $3k + 2$, then $n^2$ is also of the form $3k + 1$

That completes the proof!

Answer 6

Because you wanted to proceed by induction ...

Base case: $0^3 = 0$ is divisible by 3

For any $n$, we have 2 cases.

First take $(n + 1)^2 = n^2 + 2n + 1$

Case 1: $n^2$ is divisible by 3

Let $n = 3k$. What can we conclude?

Case 2: $n^2$ is $3k + 1$.

$$ n^2 + 2n + 1 = n^2 - 1 + 2(n + 1) = (n - 1)(n + 1) + 2(n + 1)$$

We know $n$ is even as $n^2$ is even (fundamental theorem of arithmetic).

Then if $n + 1$ is divisible by 3, we are done.

If $n + 1$ is not, then because $n$ is even, for odd $m$, $n + 1 = 3m + 2$.

$$2(n + 1) = 2(3m + 2 + 1) = 2(3m + 3) = 6m + 6$$.

And you can see that it is divisible by 3.