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?
Best Answer
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$.