# Proof that $\sqrt{5}$ is irrational

In my textbook the following proof is given for the fact that $\sqrt{5}$ is irrational:

$x = \frac{p}{q}$ and $x^2 = 5$. We choose $p$ and $q$ so that the have no common factors, so we know that $p$ and $q$ aren't both divisible by $5$.

$$\left(\dfrac{p}{q}\right)^2 = 5\\ \text{ so } p^2=5q^2$$

This means that $p^2$ is divisble by 5. But this also means that $p$ is divisible by 5.

$p=5k$, so $p^2=25k^2$ and so $q^2=5k^2$. This means that both $q$ and $p$ are divisible by 5, and since that can't be the case, we've proven that $\sqrt{5}$ is irrational.

What bothers me with this proof is the beginning, in which we choose a $p$ and $q$ so that they haven't got a common factor. How can we know for sure that there exists a $p$ and $q$ with no common factors such that $x=\dfrac{p}{q} = \sqrt{5}$? Because it seems that step could be used for every number

Edit:

I found out what started my confusion: I thought that any fraction with numerator 1 had a common factor, since every integer can be divided by 1. This has given me another question: Are confusions like this the reason why 1 is not considered a prime number?

• A maybe cleaner way to see it: suppose $\sqrt{5}$ is rational, so it equals $\frac{p}{q}$, and thus $p^2 = 5q^2$. The left hand side has an even number of factors of 5, being a square, and the right hand side an odd number (square has even number plus one extra 5), and this is absurd, as they are the same number... – Henno Brandsma Dec 22 '12 at 21:42
• Yes, 1 being counted as prime (or any number with a multiplicative inverse, so we could add it in a product and cancelling it with another term, like -1) would "spoil" a unique prime factorization result... – Henno Brandsma Dec 22 '12 at 21:44
• "How can we know for sure that there exists a p and q with no common factors such that $x=\frac{p}{q}=\sqrt{5}$? Because it seems that step could be used for every number" It might be instructive to try and push the proof through with $x = \frac{p}{q} = \sqrt{4}$ and see where it fails. – Austin Mohr Dec 23 '12 at 6:31

We know that by the definition of rational numbers, essentially: rationals can be written as $\frac{p}{q}$ for integers $p,q$, $q \neq 0$.

If for some choice they would have a common factor, we could divide it out, with the same quotient (our rational number) remaining, and they would have one factor less in common. As the number of common factors is finite, we have to repeat this at most finitely many times to have a choice of $p$ and $q$ with no common factors.

The proof starts by assuming we have done this step already.

More formally, you could consider the set $A:= \{(n,m) \in \mathbb{N} \times \mathbb{N}: n^2 = 5m^2\}$, and if $\sqrt{5}$ were rational, $A$ would be non-empty (as $\sqrt{5} > 0$ we can pick two positive integers WLOG.) But $\mathbb{N} \times \mathbb{N}$ is well-ordered in the order $(a,b) < (c,d)$ iff $c < d$ or $c=d$ and $a<b$. (This is just the product of the ordinal $\omega$ with itself in set theory.). Let $(n,m)$ be the minimum of this non-empty set. If $a|n$ and $a|m$ would both hold for some $a > 1$, then $(n',m'):=(\frac{n}{a}, \frac{m}{a}) \in A$ and $(n',m') < (n,m)$, contradicting minimality. This agument can easily be adapted to show any fraction has a unique (modulo the sign of $p,q$, or demand $q>0$) equivalent representation $\frac{p}{q}$ where there is no $a>1$ such that $a|p$ and $a|q$.

• I think I misunderstood common factor, because I thought numbers like $\dfrac{1}{2}$ have a common factor too (both are divisible by 1) – JohnPhteven Dec 22 '12 at 21:38
• No, 1 does not count. – Henno Brandsma Dec 22 '12 at 21:40
• +1, With the caveat that you must still show that this "dividing out" eventually terminates with $p$ and $q$ relatively prime. – user7530 Dec 22 '12 at 22:14

if $p,q$ have a common factor, just reduce the fraction and start the proof from scratch. This is a standard technique in such irrationality proofs.

• I think what the OP is looking for is an understanding of "just reduce the fraction" — that the process in general is always possible, and terminates with a fraction $p/q$ in which $p$ and $q$ have no common factor (greater than $1$). – ShreevatsaR Dec 23 '12 at 6:24

We're assuming their existence, and reaching something which is absurd. This leads us to conclude that their existence is indeed impossible, whence the result follows.

The core of a proof by contradiction is the following: we assume a premise $p$. With that, we work out conclusions $q,r,s,t$ by means we know are correct, and reach a contradiction $C$, which we know is absurd. Since we are sure all the intermediate steps we took are correct, we must conclude that the premise $p$ was incorrect in the first place.

It is clear that neither $p$ nor $q$ can be $0$.

Let $5^k$ be the highest power of $5$ that divides $p$, and let $5^l$ be the highest power of $5$ that divides $q$.

Suppose that $k\le l$. Let $p=5^kp'$ and $q=5^kq'$. Then $\dfrac{p}{q}=\dfrac{p'}{q'}$ and $5$ does not divide $p'$.

Similarly, if $l\le k$, let $p=5^lp'$ and $q=5^lq'$. Then $5$ does not divide $q'$.

Thus the fraction $\dfrac{p}{q}$ can always be replaced by an equivalent fraction $\dfrac{p'}{q'}$ such that $5$ fails to divide at least one of $p'$ or $q'$.

Exactly what MSEoris said, you can always reduce a fraction to such a point that they have no common factors, if $\frac{p}{q}$ had a common factor n, then $nk_0 = p$ $nk_1 = q$ then $\frac{p}{q} = \frac{nk_0}{nk_1} = \frac{k_0}{k_1}$, now if $k_0, k_1$ have a common factor do the same and you will eventually get a fraction with no common factor

Suppose $\sqrt{5}$ is rational. Then there is a smallest positive integer $q$ such that $\sqrt{5} = p/q$. Then $\sqrt{5} = \sqrt{5}\frac{\sqrt{5}-2}{\sqrt{5}-2} = \frac{5-2\sqrt{5}}{\sqrt{5}-2} = \frac{5-2p/q}{p/q-2} = \frac{5q-2p}{p-2q}$.

Since $2 < \sqrt{5} < 3$, $2 < p/q < 3$, or $2q < p < 3q$, so $0 < p-2q < q$. We have thus found a representation of $\sqrt{5}$ with a smaller denominator, which contradicts the specification of $q$.

Therefore $\sqrt{5}$ is irrational.

This can be easily generalized to prove that if $n$ is a positive integer that is not a square of an integer, then $\sqrt{n}$ is irrational. (Copy, paste, and edit used to create the following.)

Let $k$ be such that $k^2 < n < (k+1)^2$. Suppose $\sqrt{n}$ is rational. Then there is a smallest positive integer $q$ such that $\sqrt{n} = p/q$.

Then $\sqrt{n} = \sqrt{n}\frac{\sqrt{n}-k}{\sqrt{n}-k} = \frac{n-k\sqrt{n}}{\sqrt{n}-k} = \frac{n-kp/q}{p/q-k} = \frac{nq-kp}{p-kq}$.

Since $k < \sqrt{n} < k+1$, $k < p/q < k+1$, or $kq < p < (k+1)q$, so $0 < p-kq < q$. We have thus found a representation of $\sqrt{n}$ with a smaller denominator, which contradicts the specification of $q$.

Note: This is certainly not original - but I had fun working it out based on the proof I know that $\sqrt{2}$ is irrational.

Note 2: It is interesting that this does not use any divisibility properties. Another type of proof can be based on the Pell equation: If there is a solution in positive integers $x$ and $y$ to $x^2-ny^2 = 1$, then $\sqrt{n}$ is irrational. This is done by (1) showing that there are solutions to the equation with arbitrarily large $x$ and $y$; (2) showing that the assumption that $\sqrt{n}$ is rational contradicts (1).

Of course the analysis of the general Pell equation is decidedly non-trivial (at least to me), but solutions for particular values of $n$, such as 2 or 5, are easily generated by hand. Don't try this for $n = 61$, though.

You just stated a proof by contradiction. You assumed that there exists $p$ and $q$ that are relatively prime such that $\frac{p^2}{q^2} = 5$. You came to the conclusion that $p$ and $q$ cannot be relatively prime, contradicting your assumption. Therefore, there are no such $p$ and $q$, and therefore no rational number, whose square is 5.

One can show a more general result which is the following.

Proposition: If $p$ is a prime number then $\sqrt{p}$ is irrational.

Proof: assume that $\sqrt{p}$ is rational then we must have $$p=\frac{n^2}{m^2}$$ for some positive integers $n,m$ with no common divisors. but then$$n^2=pm^2$$ which implies that $p$ divides $n^2$ but then using "Euclid's Lemma" we must have $p$ divides $n$, which implies that $n=pk$ for some $k\in \Bbb N$, but then $$pm^2=n^2=(pk)^2=p^2k^2$$ which implies$$m^2=pk^2$$ that is $p$ divides $m^2$, again using Euclid's lemma we must have $p$ divides $m$. Thus, we have found a common divisor of $n$ and $m$ which is contrary to the assumption. Thus, we must have $\sqrt{p}$ is irrational.