Past exam of the options I course of the University of Oxford / 2011 / C / 1

A prime number is an integer $p>1$ whose only positive divisors are $1$ and $p$. The restriction $p>1$ excludes the unit $1$.

The fundamental theorem of arithmetic says that every integer $n>1$ is a product of prime numbers, uniquely up to reordering. Equivalently, $n={\prod }_p{p}^{a_p}$ for a unique family of nonnegative integer exponents, only finitely many of which are nonzero.

If the complete list of prime numbers were $p_1,\dots ,p_k$, then $N=p_1\cdots p_k+1>1$ would have a prime divisor by the fundamental theorem of arithmetic. No $p_i$ divides it, since $N\equiv 1(\mathrm{mod}{p}_i)$. This contradicts completeness of the list. Hence there are infinitely many prime numbers.

Every integer has one of the six residues $0,1,2,3,4,5$ modulo $6$. A prime number other than $2$ or $3$ is divisible by neither $2$ nor $3$, eliminating residues $0,2,3,4$. Thus

Suppose there were only finitely many prime numbers congruent to $5$ modulo $6$, and list them as $p_1,\dots ,p_k$. The list is nonempty since it contains $5$. Let $N=6p_1\cdots p_k-1$. It is greater than one and divisible by neither $2$ nor $3$. Every prime factor therefore has residue $1$ or $-1$ modulo $6$. Since $N\equiv -1(\mathrm{mod}6)$, at least one prime factor $q$ must have residue $-1$. But $N\equiv -1(\mathrm{mod}{p}_i)$ for every listed prime, so $q$ is not on the list. This contradiction proves there are infinitely many primes congruent to $5$ modulo $6$.