Past exam of the mathematics course of the University of Cambridge / 2018 / ia / Paper 4 / 1E (Numbers and Sets)

Fermat's little theorem states that if $p$ is prime, then $a^p\equiv a(\mathrm{mod}p)$ for every integer $a$; equivalently, $a^{p-1}\equiv 1(\mathrm{mod}p)$ when $p\nmid a$.

If $p\equiv 3(\mathrm{mod}4)$ and $x^2\equiv -1(\mathrm{mod}p)$, thenbecause $(p-1)/2$ is odd. This contradicts Fermat's theorem, so $x^2\equiv -1(\mathrm{mod}p)$ has no solution.

If the primes congruent to $1(\mathrm{mod}4)$ were $p_1,\dots ,p_k$, set $N=(2p_1\cdots p_k{)}^2+1$. Any prime divisor $q$ of $N$ is odd and has $-1$ as a quadratic residue. The preceding result forces $q\equiv 1(\mathrm{mod}4)$, but $q$ divides none of the $p_i$ because $N\equiv 1(\mathrm{mod}{p}_i)$. This contradiction proves that infinitely many primes are congruent to $1(\mathrm{mod}4)$.