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?
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?
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$.
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
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.
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.
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).
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.
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.
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).
Here are some of my favorite (sketches) of proofs for the irrationality of $\sqrt{2}$.
[Reposted from closed topicProve the square root of 2 is irrational
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$
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.
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 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 means $0 More generally We can prove, more generally, that if $n$ is an integer and $n^2 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 and hence $nq . Therefore $0 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 Uniqueness follows from: If $0\leq m So if $n^2\leq D< (n+1)^2$ and $m^2\leq D< (m+1)^2$, then we can't have $m 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)
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$.