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

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?

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

• Let me know if you're having a hard-time with the "$\equiv$" notation, I'll change it to something similar to your usage of $k$ in your question... – barak manos Sep 1 '16 at 10:43

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

• Question about division: $\forall n,m,k(n,m,k \in \mathbb{N}, n|k \overset{def}{=} m \cdot n = k)$, right? – Gal Grünfeld Sep 1 '16 at 10:35
• It should be written $$n\mid k: \Leftrightarrow \exists m \text{ such that } m\cdot n=k$$ – b00n heT Sep 1 '16 at 10:37
• Alright. Thanks for making it more precise. I understand the difference. I just have a question about the notation (since I'm a newbie, like I said): about the "$:\Leftrightarrow$" - shouldn't the whole thing be "$n|k \overset{def}{=}n|k\Leftrightarrow\exists m\in Z|m\cdot n =k$"? – Gal Grünfeld Sep 1 '16 at 10:45

Do you know the following result?

If a prime $p$ divides a product $xy$, then it divides at least one of $x$ or $y$.

Proof: Suppose $p$ does not divide $x$. We will use Bezout's identity.Since $p$ doesn't divide $x$ and $p$ is prime, it is relatively prime to $x$. Hence, there exist integers $m$ and $n$ such that $mx+pn=1$.

Now, multiply both sides of the equation by $y$, and we get $mxy+pny=y$. Thus, the left hand side is divisible by $p$, because $p |xy$ and $p | pny$. Hence, the right hand side also must divide $p$ : in other words, $p | y$.

Thus, since $3$ is a prime, $3 | n^2$ means that $3 | n * n$, means that $3 | n$ or $3|n$. These are the same, and one of them must happen, hence $3 | n$.

• Oh, it is circular. I will edit the proof, I wrote it too casually. – астон вілла олоф мэллбэрг Sep 1 '16 at 10:30
• Ok, edited, and uses Bezout's identity, which does not require any concept of unique prime factorization. – астон вілла олоф мэллбэрг Sep 1 '16 at 10:40
• I knew how to prove it if I assume the theorem you wrote above. I suppose I knew it intuitively, but never saw a proof of it. We didn't learn anything in number theory and arithmetics. So I didn't know things like Betzout's identity, and therefore didn't know how to prove the theorem. I guess this lesson of the course isn't built well, but thanks for the help! :) – Gal Grünfeld Sep 1 '16 at 10:40
• @GalGrünfeld There are many things we know but cannot write down on paper. There are many good books on number theory,which you can refer to in case your lesson is not interesting. Nearly every book will cover the axioms of natural numbers first, then the concept of division, gcd, and then Bezout's identity. Or of course, you could post on this website and we will be very happy to relieve you of your lesson problems. – астон вілла олоф мэллбэрг Sep 1 '16 at 10:42

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