# Trying to prove that if $n^2=3q$, then $n=3p$ for $n,p,q \in\mathbb{N}$.

While trying to prove that $\sqrt{3}$ is irrational, I had to use the assumption that if $n^2$ is divisible by 3, then so is $n$.

Mathematically, I am trying to prove that if $n^2=3q$, then $n=3p$ for some $n,p,q\in\mathbb{N}$.

I came up with a proof by contradiction but I am not sure if it's logically correct.

Let $n,p,q,\in\mathbb{N}$ and let $n^2=3p$. Thus, $n^2$ is divisible by 3. Now assume that $n$ is not divisible by $3$, or $n\neq 3q$.

We have that $$n=\sqrt{3}\sqrt{p}\neq 3q$$ This means that $$p\neq 3q^2$$ At this point, can I say that I have reached a contradiction because $p=12\in\mathbb{N}$ and $q=2\in\mathbb{N}$ provide a counter-example to the last statement?

EDIT: I am looking for an elementary proof that does not use Euclid's lemma.

• Hint: Use Euclid's Lemma. – Mr Pie May 14 '18 at 1:48

Assume n is not divisible by 3, then n is the product of primes and powers of primes, none of which is 3. $n^2$ is the product of the same set of primes and powers, with each exponent multiplied by 2. However 3 is still not on the list, so it does not divide $n^2$.

• Say we have the number $9$ instead of $3$. $9\mid 6^2$ but $9\nmid 6$. So, your reasoning is incorrect, unless I did not understand it properly. – Mr Pie May 14 '18 at 1:37
• @user477343 their reasoning is absolutely fine. 6 is not a prime number and so your counter example does not work. – Sul May 14 '18 at 1:45
• @SxS yes I re-read it, and it is fine. I thought $3.n^2$ was the product he was referring to, but it turns out the dot was just a full stop. Perhaps I should have deleted my comment :/ – Mr Pie May 14 '18 at 3:02

This is equivalent to "if $3\nmid n$ then $3\nmid n^2$".

If $3\nmid n$ then $n=3k+1$ or $n=3k-1$ for some integer $k$ and then $n^2=9k^2\pm6k+1=3(3k^2\pm2k)+1$ and so leaves remainder $1$ when one divides by $3$.

If $3\mid n^2$, then consider the congruence mod $3$:

$$n^2\equiv1\Leftrightarrow n\equiv 1\text{ or } 2\pmod 3.$$

Thus $3\mid n$.

• If $n^2\equiv 1\pmod 3$ then $3\mid n\pm 1$, follows that $n\equiv 1,2\pmod 3$ and $3\nmid n$. $$\therefore n\equiv 0\pmod 3\Leftrightarrow n^2\equiv 0\pmod 3.$$ Is this what you are proving? – Mr Pie May 14 '18 at 4:33
• Basically, yes. – abc... May 14 '18 at 4:34
• Nice and concise $(+1)$ – Mr Pie May 14 '18 at 4:35

Euclid's Lemma:

If a prime $p$ divides the product $ab$ of two integers $a$ and $b$, then $p$ must divide at least one of those integers $a$ and $b$.

Notation: $u\mid v$ is read as "$u$ divides $v$," and $u\nmid v$ is read as "$u$ does not divide $v$."

Proof: Suppose that $p\nmid a$. Then, $a$ and $p$ are relatively prime (coprime) to each other; their greatest common divisor is $1$.

Now, suppose that $ab = pq$ for some integer $q$. Then, since $p\nmid a$, it follows that $q\mid a$. Thus, for an integer $r$, we have that $a = qr$, then $qr\cdot b = pq$ if (and only if!) $p=br$. But if $p\mid r$ then, since $r\mid a$, it follows that $p\mid a$. This is contrary to what we supposed, thus $p\mid b$.

Of course, then, if we suppose that $p\nmid b$, we obtain that $p\mid a$; this completes the proof. $\quad\quad\quad\,\,\bigcirc$

Now, let $ab = n^2$.