Prove: $\forall n\in\mathbb{N}(3|n^2\Rightarrow 3|n)$

Question

guys.

I just started to learn infinitesimal mathematics 1 (I think it's analagous to calculus A - the professor said that it's the most theoretical course on calculus offered in the university (The Technion, in Israel).

So I'm just saying that I'm a noobie.

We weren't really taught things in number theory and things that are related to mathematics, specifically, but the course has a short introduction about $\mathbb{R}$eal numbers.

In the homework I've got, I'm supposed to prove this:

$\forall n\in\mathbb{N}(3|n^2\Rightarrow 3|n)$

(meaning that $3$ divides $n^2\Rightarrow 3$ divides $n$.

What I did so far is this:

$3|n^2 \because given\Rightarrow$

$n^2 = 3k\,|\, k\in\mathbb{N}$

$n^2 = 3k\, \>|:3\Rightarrow$

$\frac{n^2}{3}=k$

I really don't know what to do beyond this.

I need to rely on high school knowledge and intuitive logic and formulate that. The idea of doing this is practicing making formal proofs.

What knowledge am I suppose to rely on?

Thanks for everyone in advance!

Answer 1

You want to prove the statement $\color\red{3|n^2}\implies\color\green{3|n}$.

Instead, prove the equivalent statement $\neg(\color\green{3|n})\implies\neg(\color\red{3|n^2})$:

$\neg(3|n)\implies$

$3\not|n\implies$

$n\not\equiv0\pmod3\implies$

$[n\equiv1\pmod3]\vee[n\equiv2\pmod3]\implies$

$[n^2\equiv1^2\pmod3]\vee[n^2\equiv2^2\pmod3]\implies$

$[n^2\equiv1\pmod3]\vee[n^2\equiv4\pmod3]\implies$

$[n^2\equiv1\pmod3]\vee[n^2\equiv1\pmod3]\implies$

$n^2\equiv1\pmod3\implies$

$n^2\not\equiv0\pmod3\implies$

$3\not|n^2\implies$

$\neg(3|n^2)$

Answer 2

Hint: instead of that prove more generally that if $p$ is a prime number and $p$ divides a product (of integer numbers) $ab$ the $p$ divides $a$ or $p$ divides $b$. Then use the fact that $3$ is prime

Answer 3

Calculate the squares modulo $3$. Any integer is congruent to $0$, $1$ or $-1$, so squares are congruent to $0^2=0$, $1^2=1$ pr $(-1)^2=1$ respectively.

The only case with $n^2\equiv 0\mod 3$ is $n\equiv 0\mod 3$.