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

$$n\in \Bbb N$$

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

I started solving this by induction, but I'm not sure that I'm going in the right direction, any suggestions?

• This has got nothing to do with calculus or division algebras. Oct 26, 2014 at 18:52
• If a prime $p$ divides a product $ab$, then either $p$ divides $a$ or $p$ divides $b$. You have that $p$ divides the product $n \cdot n = n^2$. So, what can you say?
– user71641
Oct 26, 2014 at 18:54
• Feb 15, 2015 at 16:29

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

• This is not true. 4|10*2 but 4 does not divide 10 and 4 does not divide 2
– 123
Oct 26, 2014 at 18:50
• @mathtastic So what you're saying is... $4$ is prime. Oct 26, 2014 at 18:51
• sorry I didn't mention p should be a prime when I firstly posted the answer
– Fan
Oct 26, 2014 at 18:52
• Edward Jiang - No. 4 is obviously not prime. However, that condition was an edit added after I made my comment. The statement is now true. The original statement was: $p|ab$ implies $p|a$ or $p|b$
– 123
Oct 26, 2014 at 18:53

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$.)

• Thank you. The only problem I now have is that it seems we can do the same with proving 4 | p^2 => 4 | p, because: If p = 4k then p^2 = (4k)^2 = 4(4k^2) => 4|p^2 If p = 4k + 1 then 4 does not divide p^2 If p = 4k + 2 then 4 does not divide p^2 So we see that if 4 does not divide p (i.e., in the last two cases), then 4 does not divide p^2. This is the same as saying that 4 does not divide p^2 implies 4 divides p. (But this is not true for p = 2). Apr 17, 2016 at 11:08
• If $n=4k+2$ then $n^2=(4k+2)^2=16k^2+16k+4=4(4k^2+4k+1)$ and $4\mid n^2$. So the same argument does not work with $4$ instead of $3$. Apr 17, 2016 at 11:23
• Got it. Thanks a ton! Apr 17, 2016 at 12:02

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$

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

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.

Proof by contrapositive: ("If $$3 \not \mid n$$, then $$3 \not \mid n^2$$" is logically equivalent to "If $$3\mid n^2$$, then $$3\mid n$$")

Since we have $$3 \not \mid n$$, then there are remainders $$r=1,2$$ So, we have that $$n=3k_1+1$$ or $$n=3k_2+2$$ for some $$k_1,k_2 \in \mathbb{N}$$.

Then, if $$n=3k_1+1$$ we have that $$n^2=9k_1^2+6k_1+1$$. Note $$n^2=3(3k_1^2+2k_1)+1$$, where $$3k_1^2+2k_1 \in \mathbb{N}$$, since $$\mathbb{N}$$ closed under multiplication and addition. So, since we have remainder $$r=1$$ we see that $$3 \not\mid n^2$$.

Then, if $$n=3k_2+2$$ we have that $$n^2=9k_2^2+12k_2+4$$. Note $$n^2=3(3k_2^2+4k_2+1)+1$$, where $$3k_2^2+4k_2+1\in \mathbb{N}$$ since $$\mathbb{N}$$ closed under multiplication and addition. So, since we have remainder $$r=1$$ we see that $$3 \not\mid n^2$$

Thus, we have that $$3 \not\mid n^2$$, which shows the contrapositive to be true.

Q.E.D.

• First line ("If $3\mid n$, then $3\mid n^2$") is mixed up. Dec 13, 2018 at 2:24
• Thanks for that! Dec 13, 2018 at 7:23

$n$ is an integer, so by Euclid's algorithm, $n=3a+b$ where $a$ is an integer, and $b$ is either 0,1 or 2, then $n^2=9a^2+6ab+b^2$, and therefore $3|n^2\Rightarrow 3|b^2$. And now we got Dr. Sonhard Graubner proof as $3|b^2\Rightarrow b^2\neq 1,4\Rightarrow b\neq 1,2 \Rightarrow b=0\Rightarrow n=3a\Rightarrow 3|n$

As fan wrote, if $p$ is prime and divides $ab$ then $p$ divides either $a$ or $b$ (or both). Here is a proof of that theorem.

Since the only divisors of a prime number are $1$ and itself, either $GCD(p,a)=1$ or $GCD(p,a)=p$. (GCD means Greatest Common Divisor.) The second means that $p$ divides $a$ and we're done.

If $GCD(p,a)=1$ then by Bezout's theorem we can find integers $x$ and $y$ such that $$px+ay=1$$ Multiply this by $b$ and we get $$pbx+(ab)y=b$$

$p$ obviously divides the first term and by hypothesis it divides the second, so $p$ must also divide the third term, $b$, and we are done again.

Proof by induction: assume $$n>3$$ and that it is true for $$k.

If we have $$3|n^2$$ then $$3$$ divides each term of $$n^2 - 6n +9 = (n-3)^2$$. So we see that $$3| (n-3)^2$$ and by the induction hypothesis $$3 | (n-3)$$ which implies $$3 | n$$

The statement is vacuously true for $$n=1,2$$ and obviously true for $$n=3$$.

Proof by contraposition:

Suppose $$3 \nmid n$$, then $$n \equiv 1 (mod 3)$$ or $$n \equiv 2 (mod 3)$$

So $$n^2 \equiv 1^2 \equiv 1 (mod 3)$$ or $$n^2 \equiv 2^2 \equiv 1 (mod 3)$$

Therefore $$3 \nmid n^2$$

$$n^3 + 2n = n(n^2 + 2) = n[(n^2 - 1) + 3] = 3n + {n(n-1)(n+1)} \Rightarrow P + Q$$

Here: $$P = 3n \Rightarrow \text{divisible by } 3$$ $$Q = n(n-1)(n+1) \Rightarrow \text{this is a multiplication of three consecutive number and hence it is divisible by } 3$$ $$\therefore P + Q \text{ is divisible by } 3$$

• Welcome to Mathematics Stack Exchange. Please use MathJax to format your answer; just using the * symbol has another function than you intend. May 19, 2017 at 17:15
• What does the divisibility of $n^3+2n$ by $3$ have to do with the question? May 19, 2017 at 17:30
• @epimorphic I think the intention is "$n^3 + 2n$ is always divisible by $3$; if $n^2$ is divisible by $3$, then so is $n^3$, and hence $2n = (n^3+2n) - n^3$. Since $3$ is a prime and doesn't divide $2$, it divides $n$". The argument would be more economic using $n^3-n$ and $n = n^3 - (n^3-n)$. May 19, 2017 at 18:18
• @DanielFischer I see. Would be nice if that was carried out fully... May 19, 2017 at 18:45