How can you prove that the square root of two is irrational?

Question

I have read a few proofs that $\sqrt{2}$ is irrational.

I have never, however, been able to really grasp what they were talking about.

Is there a simplified proof that $\sqrt{2}$ is irrational?

Answer 1

You use a proof by contradiction. Basically, you suppose that $\sqrt{2}$ can be written as $p/q$. Then you know that $2q^2 = p^2$. However, both $q^2$ and $p^2$ have an even number of factors of two, so $2q^2$ has an odd number of factors of 2, which means it can't be equal to $p^2$.

Answer 2

Another method is to use continued fractions (which was used in one of the first proofs irrationality of $\displaystyle \pi$).

Instead of $\displaystyle \sqrt{2}$, we will consider $\displaystyle 1 + \sqrt{2}$.

Now $\displaystyle v = 1 + \sqrt{2}$ satisfies

$$v^2 - 2v - 1 = 0$$

i.e

$$v = 2 + \frac{1}{v}$$

This leads us to the following continued fraction representation

$$1 + \sqrt{2} = 2 + \cfrac{1}{2 + \cfrac{1}{2 + \dots}}$$

Any number with an infinite simple continued fraction is irrational and any number with a finite simple continued fraction is rational and has at most two such simple continued fraction representations.

Thus it follows that $\displaystyle 1 + \sqrt{2}$ is irrational, and so $\displaystyle \sqrt{2}$ is irrational.

Exercise: Show that the Golden Ratio is irrational.

More information here: http://en.wikipedia.org/wiki/Continued_fraction

Answer 3

If $\sqrt 2$ were rational, we could write it as a fraction $a/b$ in lowest terms. Then $$a^2 = 2 b^2.$$ Look at the last digit of $a^2$. It has to be $0$, $1$, $4$, $5$, $6$ or $9$. Now look at the last digit of $2b^2$. It has to be $0$, $2$ or $8$. As $a^2$ and $2b^2$ are the same number, its last digit must be $0$. But that's only possible if $a$ ends in $0$ and $b$ ends in $0$ or $5$. Either way both $a$ and $b$ are multiples of $5$ contradicting $a/b$ being in lowest terms.

Answer 4

Consider this proof by contradiction:

Assume that $\sqrt{2}$ is rational. Then there exists some rational $R=\sqrt{2}=\frac{Q}{D}$, where $Q$ and $D$ are positive integers and relatively prime (since $R$ can be expressed in simplified form).

Now consider $R^2 = 2 = \frac{Q^2}{D^2}$. Since $Q$ and $D$ are relatively prime, this means that only $Q^2$ can have $2$ in its prime decomposition, and the exponent must be one. Thus, $Q^2 = 2^1 x$, for some odd integer $x$. But $Q^2$ is a square, and thus the exponents for all of its prime factors must be even. Here we have a contradiction.

Thus, $\sqrt{2}$ must be irrational.

Answer 5

The continued fraction proof in Aryabhata's answer can be recast into an elementary form that requires no knowledge of continued fractions. Below is a variant of such that John Conway (JHC) often mentions, followed by my (WGD) reinterpretation of it to highlight the key role played by the principality of (denominator) ideals in $\:\mathbb Z\:$ (which I call unique fractionization).

---

THEOREM (JHC) $\quad \rm r = \sqrt{n}\ \:$ is integral if rational,$\:$ for $\:\rm n\in\mathbb{N}$

Proof $\ \ \ $ Put $\ \ \displaystyle\rm r = \frac{A}B ,\;$ least $\rm\; B>0\:.\;$ $\ \displaystyle\rm\sqrt{n}\; = \frac{n}{\sqrt{n}} \ \Rightarrow\ \frac{A}B = \frac{nB}A.\ \:$ Taking fractional parts yields $\rm\displaystyle\ \frac{b}B = \frac{a}A\ $ for $\rm\ 0 \le b < B\:.\ $ But $\rm\displaystyle\ B\nmid A\ \Rightarrow\:\ b\ne 0\ \:\Rightarrow\ \frac{A}B = \frac{a}b\ $ contra $\rm B $ least. $\:$ QED

Abstracting out the Euclidean descent at the heart of the above proof yields the following

---

THEOREM (WGD) $\quad \rm r = \sqrt{n}\ \:$ is integral if rational,$\:$ for $\:\rm n\in\mathbb{N}$

Proof $\ \ $ Put $\ \ \displaystyle\rm r = \frac{A}B ,\;$ least $\rm\; B>0\:.\;$ $\ \displaystyle\rm\sqrt{n}\; = \frac{n}{\sqrt{n}} \ \Rightarrow\ \frac{A}B = \frac{nB}A\ \Rightarrow\ B\:|\:A\ $ by this key result:

---

Unique Fractionization $\ $ The least denominator $\rm\:B\:$ of a fraction divides every denominator.

Proof $\rm\displaystyle\ \ \frac{A}B = \frac{C}D\ \Rightarrow\ \frac{D}B = \frac{C}A \:.\ $ Taking fractional parts $\rm\displaystyle\ \frac{b}B = \frac{a}A\ $ where $\rm\ 0 \le b < B\:.\ $ But

$\rm\displaystyle\ \:B\nmid D\ \Rightarrow\ b\ne 0\ \Rightarrow\ \frac{A}B = \frac{a}b\ \ $ contra leastness of $\rm\:B.\,$ Thus $\rm\,B\mid D\,$ as claimed $\quad $ QED

---

Thus JHC's proof essentially "inlines" the above proof - which can be more conceptually viewed as the principality of (denominator) ideals in $\mathbb Z,\,$ cf. my post here. See also this sci.math discussion between John Conway and I (click "plain text" to get correct format).

Answer 6

You can also use the rational root test on the polynomial equation $x^2-2=0$ (whose solutions are $\pm \sqrt{2}$). If this equation were to have a rational solution $\frac{a}{b}$, then $a \vert 2$ and $b \vert 1$, hence $\frac{a}{b}\in \{\pm 1, \pm 2\}$. However, it's straightforward to check that none of $1,-1,2,-2$ satisfy the equation $x^2-2=0$. Therefore the equation has no rational roots and $\sqrt{2}$ is irrational.

Answer 7

There is also a proof of this theorem that uses the well ordering property of the set of positive integers, that is in a non empty set of positive integers there is always a least element. The proof follows the approach of proof by contradiction but uses the well ordering principle to find the contradiction :) -

Let us assume $\sqrt{2}$ is rational, hence it can be written down in the form $\sqrt{2}=a/b$ assuming that both $a$ and $b$ are positive integers in that case if we look at the set $S = \{k\sqrt{2} \mid k, k\sqrt{2}\text{ are integers}\}$ we find that it's a non empty set of positive integers, it's non empty because $a = b\sqrt{2}$ is in the above set. Now using the Well ordering principle we know that every set of positive integers which is non-empty has a minimum element, we assume that smallest element to be $s$ and let it equal to $s =t\sqrt{2}$. Now an interesting thing happens if we take the difference between the following quantities $s\sqrt{2} - s = (s-t)\sqrt{2} = s(\sqrt{2} - 1)$ which is a smaller element than $s$ itself, hence contradicting the very existence of $s$ being the smallest element. Hence we find that $\sqrt{2}$ is irrational.

I know the proof but I am still amazed at how the author came up with the set assumption. Sometimes such assumptions make you feel kinda dumb :). If anyone has some insight regarding how to come up with such assumptions kindly post your answer in the comment, otherwise I would just assume that it was a workaround.

Answer 8

Another one that is understandable by high schoolers and below.

---

We will use the following lemma:

If $n$ is an integer, $n^2$ is even (resp. odd) iff $n$ is even (resp. odd).

For the high-schoolers, the proof is about writing $(2k)^2 = 2(2k^2)$ and $(2k+1)^2=2(2k^2+2k)+1$ ...

---

Now, assume $\sqrt 2 = \frac{a}{b}$ with $a$ and $b$ strictly positive integers.

Then $a^2=2b^2$, $\implies a^2$ is even ($=2b^2$), $\implies a$ is even (from the lemma), $\implies a=2a_1$ with $a_1 \in \mathbb N^*$, $\implies b^2=2a_1^2$.

Repeat with $b$ to find that $b=2b_1$ with $b_1 \in \mathbb N^*$ and $(a_1,b_1)$ verifies $a_1^2=2b_1^2$.

By repeating these two steps, we build two sequences $(a_n)_{n\in \mathbb N}$ and $(b_n)_{n\in \mathbb N}$ with values in $\mathbb N^*$ and strictly decreasing, which is impossible, ergo $\sqrt{2}$ is irrational.

(Here of course we use the well-ordering principle which most high schoolders would not know about, but the intuition that the sequence would hit $0$ after at most $a_0=a$ steps is easy to get).

Answer 9

Here are some of my favorite (sketches) of proofs for the irrationality of $\sqrt{2}$.

• Using Newton's method to approximate roots of the polynomial $f(x) = x^2 - 2$, then showing that the sequence does not converge to a rational number.
• Proof by contradiction, assume that $\sqrt{2} = \frac{n}{m}$ for some $n,m \in \mathbb{Z}$ with $m \neq 0$, then $2m^{2} = n^2$, hence $n$ must be even and we can let $n = 2k$ for some $k \in \mathbb{Z}$, but then $m^2 = 2k^2$ will also be even, which is impossible if $\frac{n}{m}$ is reduced. Therefore, $\sqrt{2}$ cannot be expressed as a ratio of integers.
• Since $f(x) = x^2 -2$ is irreducible over $\mathbb{Q}[x]$, its roots must lie in some finite extension field $\mathbb{Q}(\sqrt{2})$ over the rationals.

[Reposted from closed topicProve the square root of 2 is irrational

Answer 10

Let $x^2-2=0$ be the polynomial equations this have a possibles rational solutions $\pm1,\pm2$ and no one of this is a solution then the solution is irrational and we now that this are $\pm \sqrt2$

Answer 11

The irrationality of the square root of 2 follows from our knowledge of how Pythagorean triples behave, specifically, that for positive integers x, y, and z, if x^2 + y^2 = z^2, then x is not equal to y. But if the square root of 2 were rational, then there would exist positive integers a and b such that a/b = the square root of 2. Then a^2/b^2 = 2. Then a^2 = 2b^2. Then b^2 + b^2 = a^2, and so we would have a Pythagorean triple with x = y, a contradiction.

Answer 12

Here's a short algebraic proof. It nowhere uses prime.

You need to first show that $1<\sqrt{2}<2,$ but that is obvious.

We first assume that $\sqrt{2}$ is rational. Then pick the smallest positive $q$ so that $p=q\sqrt{2}$ is an integer. Then $q<p<2q.$

Now compute:

$$\left(\frac{2q-p}{p-q}\right)^2 = \frac{4q^2-4pq+p^2}{p^2-2pq+q^2}=\frac{6q^2-4pq}{3q^2-2pq}=2$$

But $q<p<2q$ means $0<p-q<q$, and $\frac{2q-p}{p-q}=\sqrt{2},$ contradicting the assumption that $q$ was the least possible positive denominator.

---

More generally

We can prove, more generally, that if $n$ is an integer and $n^2<D<(n+1)^2$ then $\sqrt{D}$ is irrational. In the case $D=2$ we have $n=1$.

If $\sqrt{D}$ is rational, find the least positive $q$ such that there is a $p$ such that $\frac{p}{q}=\sqrt{D}$. So $p^2=Dq^2$ means $n^2q^2<p^2<(n+1)^2q^2$ and hence $nq<p<(n+1)q$.

Therefore $0<p-nq<q$.

But then:

$$\left(\frac{Dq-pn}{p-qn}\right)^2=\frac{D^2q^2-2Dpqn + p^2n^2}{p^2-2pqn+q^2n^2}=\frac{D^2q^2-2Dpqn + Dq^2n^2}{Dq^2-2pqn+q^2n^2}=D\tag{*}$$

contradicting the fact that $q$ was the smallest positive denominator for $\sqrt{D}$.

---

You can prove if $D\geq 0$ is an integer, then there is exactly one non-negative integer $n$ such that $n^2\leq D<(n+1)^2$. We first prove $n$ exists:

Since $(1+D)^2=D+(1+D+D^2)$, we know that $D<(1+D)^2$ and hence there is a least positive $m$ such that $D<m^2.$ We know $m\neq 0$ because $D\geq 0^2$, so $m\geq 1$. Let $n=m-1$. Then $n^2\leq D<(n+1)^2$.

Uniqueness follows from:

If $0\leq m<n$ then $1\leq m+1\leq n$ and thus $(m+1)^2\leq n^2$.

So if $n^2\leq D< (n+1)^2$ and $m^2\leq D< (m+1)^2$, then we can't have $m<n$ or we'd have $D<(m+1)^2\leq n^2\leq D$. Similarly, we can't have $m>n$. So we must have $m=n$.

Together, the above say that if $D\geq 0$ then $\sqrt{D}$ is rational if and only if $\sqrt{D}$ is an integer.

---

(*) The magic trick in the above computation is that If $\frac{np}{nq}=\sqrt{D}$ then $\frac{Dq}{p}=\sqrt{D}.$ And if $\frac{a}{b}=\frac{c}{d}$ then $d\neq b$ then $$\frac {a-c}{b-d}=\frac{a}{b}.$$

---

The expression is arrived by computing (using that $p=q\sqrt{D}):$

$$0<\left(p+q\sqrt{D}\right)\left(\sqrt{D}-n\right)=(qD-np)+(p-nq)\sqrt{D}$$

From this we see $(qD-np)^2-D(p-nq)^2=0.$

And $p-nq=q(\sqrt{D}-n)<q.$ since $0<\sqrt{D}-n<1.$

Answer 13

Proposition: In base $2$ any square must end in an even number of trailing zeros.

The proposition comes directly from, for example, multiplying a binary number with itself using the standard algorithm or simply by squaring

$$ (\sum_{k=t}^{N} b_k 2^k)^2=B2^{2t+1}+b_t2^{2t}$$

If we can represent $\sqrt{2}=\frac{p}{q}$ then

$$ 2q^2=p^2 $$

Multiplying by $2$ is shifting all bits of a binary number to the left, so if the number was ending in $m$ trailing zeros after multiplication by $2$ it will end in $m+1$ zeros.

This means that $2q^2$ is ending in odd while $p^2$ is ending in an even number of zeros. Thus, these two cannot be equal.

*Notice that this proof does not care about the relative primality of $p$ and $q$.