Prove that if $n^2$ is divided by 3, then also $n$ can also be divided by 3.

Solution 1:

Hint: $p|ab \implies p|a$ or $p|b$ if $p$ is a prime

Solution 2:

For every $n\in\mathbb Z$ you have three possible cases. Either $n=3k$ or $n=3k+1$ or $n=3k+2$ (for some $k\in\mathbb Z$).

Let us consider each of these cases separately:

• If $n=3k$, then $n^2=(3k)^2=3(3k^2)$, which means $3\mid n^2$.
• If $n=3k+1$, then $n^2=(3k+1)^2=9k^2+6k+1=3(3k^2+2k)+1$. This implies $3\nmid n^2$.
• If $n=3k+2$, then $n^2=(3k+2)^2=9k^2+12k+4=3(3k^2+4k+1)+1$. So we have again $3\nmid n^2$.

So we see that if $3\nmid n$ (i.e., in the last two cases), then $3\nmid n^2$. This is the same as saying that $3\mid n^2$ implies $3\mid n$.

Notice that we have in fact proved also that if $3\nmid n$, then the remainder of $n^2$ modulo $3$ is $1$.

Once you learn a bit about congruences, you will be able to write down arguments like this in more elegant and more economical way. This is the way it was done in this answer.

Maybe it is also worth to mention that instead of $n=3k+2$ we can use $n=3k-1$. This can sometimes simplify the calculations slightly. (In this case we get $n^2=(3k-1)^2=9k^2-6k+1=3(3k^2-2k)+1$.)

Solution 3:

if $n\equiv 0,1,2 \mod 3$ then $n^2\equiv 0,1 \mod 3$ therefore $n^2\equiv 0\mod 3$ then $n \equiv 0 \mod 3$

Solution 4:

Think about the fundamental theorem of arithmetic.

Decomposing into a product of primes, suppose $n = p_1^{k_1}p_2^{k_2} \cdot \cdot \cdot p_n^{k_n}$ where $k_i \in \mathbb{N}$. What happens to the prime decomposition when $n$ is squared? What if $p|n^2$ for some prime $p$?

Solution 5:

Everything comes from Bézout's lemma. Suppose that $3$ does not divide $n$, then $GCD(3, n) = 1$ and there are integers $a$ and $b$ such that $3a + nb = 1$. Now if you multiply both sides by n you get $3an + n^2b = n$. $3$ divides the left hand side, so it divides $n$ too, which gives the desired contradiction.