Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 4 (Numbers and Sets)

A prime number is an integer greater than one whose only positive divisors are one and itself. In particular, one is not a prime number. Every integer greater than one has a prime number divisor, by taking its smallest divisor greater than one.

Suppose there were only finitely many prime numbers congruent to $-1$ modulo six, and let their product be $P$, with empty product one. The integer $N=6P-1>1$ has no divisor two or three and is divisible by none of the listed prime numbers, since $N\equiv -1(\mathrm{mod}{p}_j)$. Every prime number divisor of $N$ is therefore $1$ or $-1$ modulo six. If all these divisors were $1$ modulo six, their product, with multiplicities, would also be $1$ modulo six. But $N\equiv -1(\mathrm{mod}6)$. Hence at least one divisor is an unlisted prime number congruent to $-1$ modulo six, a contradiction. There are infinitely many primes of the form $6k-1$.

For the other class, suppose its prime numbers were a finite list with product $P$. None is divisible by three. The integer $M=4P^2+3$ is odd and is $1$ modulo three, since $P^2\equiv 1(\mathrm{mod}3)$. Thus a prime number divisor $q$ of $M$ satisfies $q>3$. The residue $x=2P$ solves $x^2\equiv -3(\mathrm{mod}q)$, so the allowed quadratic-congruence fact gives $q\equiv 1(\mathrm{mod}6)$. However, for every listed divisor $p_j$, $M\equiv 3(\mathrm{mod}{p}_j)$, and $p_j>3$, so none divides $M$. We have again found an unlisted prime number in the supposedly complete list. There are infinitely many primes of the form $6k+1$. Both arguments remain valid for an empty starting list.