There is the proposition

Every integer $n$ can be represented uniquely as the product $2^km$ where $m$ is odd and $k\ge0$.

I have to use this to prove that $\sqrt{2}$ is irrational. As is it usual, assume the contrapositive

$$ \sqrt{2}=a/b, $$

where $a,b$ are integers and $b\neq 0$. Therefore

$$ a^2=2b^2. $$

Using the proposition, $b^2=2^jn$, with $n$ odd and $j\ge0$. Therefore $a^2$ is even (what the hell do I need this, since $a^2$ is clearly even, but I have to use the proposition...). Then I can continue in the usual way and finish the proof.

At this point, this proof seems very lame. Any ideas how to improve it?

  • 2
    $\begingroup$ Write $a$ and $b$ in that form then compare the parity of the exponents of $2$ in the resultant $2$-unique factorization of both sides $\endgroup$ – Bill Dubuque Jul 26 '17 at 2:55
  • $\begingroup$ If I do that I get, say $2^{2k}m^2=2^{2j+1}n^2$. I can determine that $n=m$. On the other hand, it says that $k\ge1$. Is this the punchline? $\endgroup$ – user2820579 Jul 26 '17 at 3:01
  • 1
    $\begingroup$ Hint: $m,n\,$ odd $\,\Rightarrow\, m^2$ and $n^2$ odd, so both sides are in said unique form, so $\,2k = 2j+1,\,$ contradiction. $\endgroup$ – Bill Dubuque Jul 26 '17 at 3:02
  • $\begingroup$ You are totally right. Thanks a lot! $\endgroup$ – user2820579 Jul 26 '17 at 3:04

A easy way to show $\sqrt{2}$ is not a rational number:

Suppose $\sqrt{2}$ is rational. note that $\sqrt{2}>1$, so w.l.o.g. I can take $a,b\in \mathbb{N}$ such that $\sqrt{2}=\frac{a}{b}$

Then $a^2=2b^2$. Note that $a^2\equiv 0,1(\mod 3)$

Case 1:

If $a^2\equiv 1(\mod 3)$, then $b^2\equiv 1(\mod 3)\Rightarrow 2b^2\equiv 2(\mod 3)$, but $a^2=2b^2$, then $a^2\equiv 2(\mod 3)\Rightarrow 1\equiv 2(\mod 3)$, which is impossible.

Case 2:

If $a^2\equiv 0(\mod 3)$, then $b^2\equiv 0(\mod 3)$, then $a=3c$, $b=3d$ where $c,d \in \mathbb{N}$.

Now we again get $c^2=2d^2$, since $9c^2=2\times9d^2$. This lead to a loop. The loop is we can not go to case 1(since that case is impossible). Then we have stay in case 2, which will lead to $3\mid c$ and $3\mid d$ and this process will continue until we end up to $1=2$ which is again impossible.

So there does not exist $a,b\in \mathbb{N}$ such that $a^2=2b^2$. Hence $\sqrt{2}$ is not a rational number$.\space\space\space\blacksquare$

  • $\begingroup$ Why do we have $a^2 \equiv 1, 0 (\text{mod 3})$? $\endgroup$ – Pablo S. Ocal Jul 26 '17 at 17:54
  • $\begingroup$ @galahad Since $a\equiv 0,1,2 (\mod 3)$, $a^2\equiv 0,1,4 (\mod 3)$. Now $4\equiv 1 (\mod 3)$., then $a^2\equiv 0,1 (\mod 3)$ $\endgroup$ – MAN-MADE Jul 26 '17 at 18:11

Try applying the Proposition before squaring: consider $\sqrt{2} = a/b$ an irreducible fraction, write $a = 2^i n$ and $b = 2^j m$. We have multiple cases:

  • If $n=1$ or $m=1$, then respectively we must have $j=0$ or $i=0$ because of $a/b$ being irreducible, then (squaring the original equality) respectively $m^2=4^i/2$ or $n^2 = 2\cdot 4^j m^2$. Thus either $m^2$ is even or $n^2$ is even, but $m$ and $n$ are odd and the square of an odd number is an odd number, a contradiction.

Assume $n\neq 1 \neq m$. Since $a/b$ is reducible, we must have either $i=0$ or $j=0$.

  • If $i=0$ (notice that this contains the case $j = 0 = i$), squaring we obtain that:

$$2 = \frac{n^2}{4^j m^2} \text{ so } 2\cdot 4^j m^2 = n^2 \text{ is even, which is again a contradiction because $n$ is odd.}$$

  • If $j=0$ and $i\neq 0$, squaring we obtain that:

$$2 = \frac{4^i n^2}{m^2} \text{ so } m^2 = \frac{4^i n^2}{2} \text{ is even ($i>0$), which is again a contradiction because $n$ is odd.}$$

Notice how the fact that $n$ and $m$ can be $1$ forces you to consider extra cases (alternatively, you could say that the integers do not have multiplicative inverses and include the first case in the other two).


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.