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

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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