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

Question

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

Answer 1

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

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

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

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

Answer 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.

Answer 6

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.

Answer 7

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

Answer 8

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.

Answer 9

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

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

Answer 10

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$

Answer 11

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