# Proving $\sqrt{2}$ is irrational without using prime factorization

Prove that $\sqrt{2}$ is irrational without using prime factorization.

The standard proof that $\sqrt{2}$ is irrational uses prime factorization in an essential way. So I wondered if there is a proof that does not use it.

This was inspired by the fact that I know two proofs that $\sqrt{2}$ is irrational that do not use prime factorization.

The first uses $$\sqrt{2}=\sqrt{2}\frac{\sqrt{2}-1}{\sqrt{2}-1}=\frac{2-\sqrt{2}}{\sqrt{2}-1}$$ to show that if $\sqrt{2} = \dfrac{a}{b}$ then $$\sqrt{2}=\frac{2-\dfrac{a}{b}}{\dfrac{a}{b}-1}=\frac{2b-a}{a-b}$$ is a rational $\sqrt{2}$ with a smaller denominator.

The second uses $$(x^2-2y^2)^2=(x^2+2y^2)^2-2(2xy)^2$$ and $3^2-2\cdot 2^2 = 1$ to show that $x^2-2y^2=1$ has arbitrarily large solutions and this contradicts $\sqrt{2}$ being rational.

I have not been able to extend either of these proofs to $\sqrt{2}$. Results that I do not consider "legal" in solving this problem include Fermat's Last Theorem (which definitely uses unique factorization) and the rational root theorem (which uses unique factorization in its proof).

• Do you mind using the fact that even integers have even cubes, and odd integers have odd cubes? – G Tony Jacobs May 12 '18 at 17:16
• How about adapting the classical proof that $\sqrt2$ is irrational? – Arthur May 12 '18 at 17:17
• If I'm right it is due that $\sqrt{2}$ has an infinite continued fraction (if I'm right this is the reasoning in Proof 21, from this Cut the Knot). The continued fraction is well-known, you can compute it with Wolfram Alpha. – user243301 May 12 '18 at 17:55
• The continued fraction for $\sqrt{2}$ is, as far as I know, not known. – marty cohen May 12 '18 at 22:18
• I believe that a rigorous proof can be done about the irrationality of $\sqrt{2}$ using continued fractions. If you or some user can clarify what about it or my previous words, I am going to accept it if I am wrong. Many thanks. – user243301 May 13 '18 at 9:34

## 7 Answers

You can do it using the concept of odds and evens which is sort of a poor mans version of unique prime factorization but surely acceptable. After all the classic proof of the irrationality of $\sqrt 2$ used even and odds without assuming unique prime factorization.

First note: If $b \in \mathbb Z$ is $b = 2m$ is even, then $b^3 = 8m^3$ is even and if $b = 2m + 1$ is odd then $b^3 = 8m^3 + 12m^2 + 6m + 1$ is odd.

So if $\frac ab; b\ne 0$ and $a$ and $b$ in "lowest terms" (have no factors in common, in particular are not both even), and if $(\frac ab)^3 = 2$ then....

$2a^3 = b^3$ and so $b^3$ is even and so $b$ is even and so $b = 2m$ and so $2a^3 = 8m^3$ and so $a^3 = 4m^3$ and so $a^3$ is even and so $a$ is even and so $a$ and $b$ are both even but we said that wasn't the case so that's impossible and nyah nyah nyah nyah nyah.

• Which opens the question just what were the assumptions of the original proof. We got that if $(\frac ab)^2 = 2$ then both $a$ and $b$ were divisible by two but that was not assumed to be a problem. It wasn't assumed fractions had lowest terms. But this lead to infinite regress, somehow that was not acceptable. – fleablood May 12 '18 at 17:29
• +1 and the second in mind for "and nyah nyah nyah nyah nyah". :-) – Przemysław Scherwentke May 12 '18 at 17:29
• @PrzemysławScherwentke Thank you. The idea being that once the set up was done everything would be exactly as the "classic" proof and we can just rattle it off in a single run on sentence. – fleablood May 12 '18 at 17:32

There is a general theorem known as "rational roots test" which is as follows :

Given integers $a_0,\ldots,a_n$ (with $n\ge 1$) and a rational root $p/q$ of the polynomial $P=a_nX^n+\ldots+a_0$ (with $(p,q)\in\mathbb{Z}\times\mathbb{N^\star}$ and $gcd(p,q)=1$), we must have $p\mid a_0$ and $q\mid a_n$.

The proof of this theorem requires Gauss theorem and not prime factorization.

Applying it to $P=X^3-2$, we are led to a short list of possible rational roots, and none of them is an effective root of $P$. As a conclusion $P$ doesn't have any rational roots. And so, $2^{1/3}$ is irrational.

If $\sqrt2$ we rational, it would be $a/b$ for $a$, $b\in\Bbb N$. Then there is $n\in\Bbb N$ with $n\sqrt2$ and $n\sqrt4$ integers, say $n=b^2$. Let $n$ be the least positive integer with $n\sqrt2$, $n\sqrt4\in\Bbb N$. But $(\sqrt2-1)n$ would be an even smaller one...

• Could you complete this argument? – Jack Lam May 15 '18 at 14:07

Suppose $\sqrt{2} = \dfrac{a}{b} \in \mathbb{Q}$ where $a, b \in \mathbb{N}_+$, $(a, b) = 1$. Now suppose $n \in \mathbb{N}_+$ satisfies$$(\sqrt{2} - 1)^n < \frac{1}{b}.$$ Note that there exist $c_0, c_1, c_2 \in \mathbb{Z}$ such that$$(\sqrt{2} - 1)^n = c_2 (\sqrt{2})^2 + c_1 \sqrt{2} + c_0,$$ thus\begin{align*} \sqrt{2} &= \frac{\sqrt{2} (\sqrt{2} - 1)^n}{(\sqrt{2} - 1)^n} = \frac{\sqrt{2} (c_2 (\sqrt{2})^2 + c_1 \sqrt{2} + c_0)}{c_2 (\sqrt{2})^2 + c_1 \sqrt{2} + c_0} = \frac{c_1 (\sqrt{2})^2 + c_0 \sqrt{2} + 2c_2}{c_2 (\sqrt{2})^2 + c_1 \sqrt{2} + c_0}\\ &= \frac{c_1 \left(\dfrac{a}{b}\right)^2 + c_0 \dfrac{a}{b} + 2c_2}{c_2 \left(\dfrac{a}{b}\right)^2 + c_1 \dfrac{a}{b} + c_0} = \frac{c_1 a^2 + c_0 ab + 2c_2 b^2}{c_2 a^2 + c_1 ab + c_0 b^2}, \end{align*} and$$c_2 a^2 + c_1 ab + c_0 b^2 = (c_2 (\sqrt{2})^2 + c_1 \sqrt{2} + c_0) b^2\\ \Longrightarrow 0 < c_2 a^2 + c_1 ab + c_0 b^2 = (\sqrt{2} - 1)^n b^2 < b,$$ contradictory to the minimality of $b$. Therefore, $\sqrt{2} \not\in \mathbb{Q}$.

• Yest, this this the kind of an answer that I am expecting. +1, but I will wait with a bounty in case of another answers. – Przemysław Scherwentke May 15 '18 at 2:40

Let us use the fact that $a,b$ are coprime, then $a^n, b^n$ are coprime. This is a consequence of $\mathbb{F}_{p}$ being a field.

Now, define $f : \mathbb{Q} \to \mathbb{N}$ as follows: For irreducible fraction $a/b$, $f(a/b) = ab$. Some properties of $f$:

$$f(r^n) = f(r)^{n}$$ $$f(r) = r \implies r \in \mathbb{Z}$$

Now if $s = \sqrt{2} \in \mathbb{Q}$, then by the first property, $$f(s)^3 = f(s^3) = f(2) = 2$$

Therefore, $f(s) = \sqrt{2} = s$. By the second property,

$$\sqrt{2} \in \mathbb{Z}$$

Absurd! (By extension this shows that $\sqrt[n]{m} \in \mathbb{Z}$ or $\sqrt[n]{m} \in \mathbb{R} \setminus \mathbb{Q}$)

• Wouldn't it be ℚ⇒ℕ? – Jack Lam May 15 '18 at 14:05

let $\sqrt{2}=\frac pq.$

then $2=\frac{p^3}{q^3}$ , $2q^3=p^3$, $q^3+q^3=p^3.$

But

'Fermat's Last Theorem' (sometimes called Fermat's conjecture, especially in older texts) states that no three positive integers $a$, $b$, and $c$ satisfy the equation $a^n + b^n = c^n$ for any integer value of $n$ greater than $2$.

• This is nice, though I wonder if there is a proof of FLT for exponent $n=3$ that does not use prime factorization... – Sil May 17 '18 at 19:33
• +1 for a nice joke. – Przemysław Scherwentke May 17 '18 at 20:30
• This is already known.quora.com/… – Takahiro Waki May 18 '18 at 4:17

Assume that $\sqrt{2}=\dfrac{a}{b}$ with $a,b\in\mathbb{Z^+}$

We will have $\dfrac{a^3}{b^3}=2\Leftrightarrow a^3=2b^3$ $(*)$

The above implies that $a$ must be divisible by $2$ (if $a$ is odd then $a^3$ is odd), let $a=2a_1$ with $a_1\in\mathbb{N}$, then $a^3=2b^3\Leftrightarrow 8a_1^3=2b^3\Leftrightarrow4a_1^3=b^3$

The above implies that $b$ must be divisible by $2$ (if $b$ is odd then $b^3$ is odd), let $b=2b_1$ with $b_1\in\mathbb{N}$, then $4a_1^3=b^3\Leftrightarrow 4a_1^3=(2b_1)^3\Leftrightarrow 4a_1^3=8b_1^3\Leftrightarrow a_1^3=2b_1^3$.

This will continue for an infinite loop, let $n\in\mathbb{Z^+}$ and $a_n=2a_{n+1}$ then

$$a^3=2b^3\Leftrightarrow a_1^3=2b_1^3\Leftrightarrow a_2^3=2b_2^3\Leftrightarrow a_3^3=2b_3^3\Leftrightarrow\cdots\Leftrightarrow a_n^3=2b_n^3\Leftrightarrow a_{n+1}^3=2b_{n+1}^3$$

Because $a_{n+1}\in\mathbb{Z^+}$,

$$2|a_{n},b_{n}\Rightarrow2^2|a_{n-1},b_{n-1}\Rightarrow2^3|a_{n-2},b_{n-2}\Rightarrow\cdots\Rightarrow 2^{n+1}|a,b$$

$a,b$ must be divisible by $2^{n+1}$ for all $n\in\mathbb{N}$, this is only possible if $a=b=0$, which makes $\sqrt{2}=\dfrac{a}{b}$ undefined.

By contradicition, $\sqrt{2}$ is irrational.

Alternatively...

If $\sqrt{2}$ is rational then it can be expressed in the form $\sqrt{2}=\dfrac{a}{b}$ with $a,b\in\mathbb{Z^+}$ and $\dfrac{a}{b}$ is an irreducible fraction or $GCD(a,b)=1$.

Because we have proven that both $a$ and $b$ are even numbers, $\dfrac{a}{b}$ now becomes reducible, which also contradicts the condition above. This will be a much quicker conclusion compared to the "infinite loop" method.