= 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\pmod 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\pmod p$. Pairing the factors $j$ and $p-j$ yields
$$
(-1)^{(p-1)/2}\left(\left(\frac{p-1}{2}\right)!\right)^2\equiv-1\pmod p.
$$
For $p\equiv1\pmod4$, the sign is positive, so the factorial supplies a square root of $-1$. Thus \b[$-1$ is a quadratic residue exactly when $p\equiv1\pmod4$].
Write $P=\prod_jp_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\pmod q$; the criterion just proved gives $q\equiv1\pmod4$. 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. \b[Both classes contain infinitely many primes], independently of the general <Dirichlet theorem on primes in arithmetic progressions>.
Back to article page
