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

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

#### Solutions Collecting From Web of "Prove that if $3\mid n^2$ then $3\mid n$."

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.

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?

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.

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$ ?

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.