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?

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$.

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.

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.

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.

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'$.