= Solution
<Fermat's little theorem> states that if $p$ is prime, then $a^p\equiv a\pmod p$ for every integer $a$; equivalently, $a^{p-1}\equiv1\pmod p$ when $p\nmid a$.
If $p\equiv3\pmod4$ and $x^2\equiv-1\pmod p$, then
$$
x^{p-1}=(x^2)^{(p-1)/2}\equiv(-1)^{(p-1)/2}=-1\pmod p,
$$
because $(p-1)/2$ is odd. This contradicts Fermat's theorem, so \b[$x^2\equiv-1\pmod p$ has no solution].
If the primes congruent to $1\pmod4$ were $p_1,\ldots,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\equiv1\pmod4$, but $q$ divides none of the $p_i$ because $N\equiv1\pmod{p_i}$. This contradiction proves that \b[infinitely many primes are congruent to $1\pmod4$].
Back to article page
