Past exam of the mathematics course of the University of Cambridge / 2006 / ii / Paper 3 / 11H / Solution

The Prime number theorem states that $\pi (x)\sim x/\log x$, where $\pi (x)$ counts primes not exceeding $x$. Dirichlet theorem on primes in arithmetic progressions states that if $\gcd (a,m)=1$, then the progression $a+jm$ contains infinitely many primes.

If $x^2\equiv -1(\mathrm{mod}p)$ for an odd prime $p$, the multiplicative order of $x$ modulo $p$ is four. Lagrange's theorem therefore gives $4\mid p-1$. Conversely, Wilson's theorem gives $(p-1)!\equiv -1(\mathrm{mod}p)$. Pairing the factors $j$ and $p-j$ yieldsFor $p\equiv 1(\mathrm{mod}4)$, the sign is positive, so the factorial supplies a square root of $-1$. Thus $-1$ is a quadratic residue exactly when $p\equiv 1(\mathrm{mod}4)$.

Write $P={\prod }_j{p}_j$. The odd integer $4P-1$ is $3$ modulo $4$. If all of its prime factors were $1$ modulo $4$, their product, with multiplicities, would be $1$ modulo $4$, so at least one factor is $3$ modulo $4$. Every prime factor $q$ of $4P^2+1$ is odd and satisfies $(2P{)}^2\equiv -1(\mathrm{mod}q)$; the criterion just proved gives $q\equiv 1(\mathrm{mod}4)$. Neither integer is divisible by any $p_j$, since their residues modulo $p_j$ are respectively $-1$ and $1$. Starting with any finite list thus produces a new prime in each residue class. Both classes contain infinitely many primes, independently of the general Dirichlet theorem on primes in arithmetic progressions.