4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hint: Use Euclid's Lemma. $\endgroup$ – Mr Pie May 14 '18 at 1:48
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mr Pie May 14 '18 at 1:37
  • $\begingroup$ @user477343 their reasoning is absolutely fine. 6 is not a prime number and so your counter example does not work. $\endgroup$ – Sul May 14 '18 at 1:45
  • $\begingroup$ @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 :/ $\endgroup$ – Mr Pie May 14 '18 at 3:02
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Mr Pie May 14 '18 at 4:33
  • 1
    $\begingroup$ Basically, yes. $\endgroup$ – abc... May 14 '18 at 4:34
  • $\begingroup$ Nice and concise $(+1)$ $\endgroup$ – Mr Pie May 14 '18 at 4:35
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.