Prove that if $3\mid n^2 $ then $3\mid n $.

Question

$n \in \mathbb{N}$

Prove that if $3\mid n^2 $ then $3\mid n $

I want to prove this in a accepted formal way, I thought about the fact that every integer can be written as multiplication of prime numbers. and if we raise this integer to the power two we will get multiples of each prime. $3\mid n^2 $, it means that this $"3"$ must have been in $"n"$ before raising it to the power. I am going to the right direction? and if yes, can someone hint how can I write it formally?

Answer 1

Your proof is correct.

Every number $n$ has a unique decomposition in primes: $$ n = p_1^{k_1} p_2^{k_2} \dots p_m^{k_m} $$ hence $$ n^2 = p_1^{2k_1} p_2^{2k_2} \dots p_m^{2k_m}. $$ If 3 divides $n^2$ then one of the $p_i$s is equal to $3$ and the corresponding exponent $2k_i$ is different from zero. Hence $k_i$ is different from zero and also $n$ is divisible by 3.

Answer 2

This is the hint : suppose that $3$ does not divide $n$. Then there exists integers $u, v$ such that $nu + 3v = 1$. Now what happens if you multiply both sides by $n$ ?

Answer 3

Different approach/hint: Assume that $m^2$ is a multiple of 3, write $m = 3k + a$ with $k \in \mathbb{N} \cup \{ 0 \}$ and $a \in \{ 0 , 1 , 2\}$. You have to show that $a \equiv 0$. Square both sides and then use the assumption that $m^2$ is a multiple of $3$, i.e., there exists a $s \in \mathbb{N} \cup \{0\}$ such that $m^2 = 3s$.

Can you finish this?

Answer 4

You have the right idea by thinking in terms of unique prime factorization. From Euclid's lemma we know that if $p\in\mathbb{Z}$ is prime and $p\mid ab$ then $p\mid a$ or $p\mid b$. Since $3\mid n^2 = n\cdot n$ then 3 must divide $n$.

Of course, if you have never heard of Euclid's lemma before you should try proving it yourself since your proof will provide a nice generalization of your question.

Answer 5

Assume that $3 \mid n^2$. We want to show that $3 \mid n$, for $n \in \mathbb{N}$.

Suppose to the contrary that $3 \nmid n$.

Since $3 \mid n$ means that there exists an $m \in \mathbb{Z}$ such that $n = 3m$, $3 \nmid n$ means that for all $r \in \mathbb{Z}$, $n \neq 3r$.

Note that we can square both sides of the inequation

$$n \neq 3r$$

to get

$$n^2 \neq 9r^2$$

for all $r^2 \in \mathbb{Z}$.

The last inequation implies that

$$3^2 = 9 \nmid n^2$$

which further implies that

$$3 \nmid n^2.$$

This contradicts $3 \mid n^2$, and we are done.