Exercise 3.1.20* (There are infinitely many primes of each of the forms $8n+1$, $8n + 3$, $8n + 5$, $8n+7$)

Proof. Let $p$ be an odd prime.

(a)

If $p\mid x^2+1$ for some integer $x$, then $-1$ is a quadratic residue modulo $p$, thus $\left(\frac{-1}{p}\right)={(-1)}^{(p-1)∕2}=1$, thus $$p\equiv 1(\mathit{mod}4).$$

(b)

If $p\mid x^2-2$ for some integer $x$, then $2$ is a quadratic residue modulo $p$, thus $\left(\frac{2}{p}\right)={(-1)}^{(p^2-1)∕8}=1$, thus (see Problem 10) $$p\equiv 1,7(\mathit{mod}8).$$

(c)

If $p\mid x^2+2$, then $\left(\frac{-2}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{2}{p}\right)=1$, thus ${(-1)}^{(p-1)∕2}{(-1)}^{(p^2-1)∕8}=1$, which is true if and only if

• $p\equiv 1(\mathit{mod}4)$ and $p\equiv 1,7(\mathit{mod}8)$,

  or

• $p\equiv 3(\mathit{mod}4)$ and $p\equiv 3,5(\mathit{mod}8)$,

that is if $p\equiv 1,3(\mathit{mod}8)$.

(d)

Suppose that $p\mid x^4+1$, for some integer $x$. By Theorem 2.37, $-1$ is a fourth power modulo $p$ if and only if $${(-1)}^{(p-1)∕4}=1.$$

Thus $(p-1)∕4$ is even, and $p\equiv 1(\mathit{mod}8)$.

Now we show that there are infinitely many primes of each of the forms $8n+1$, $8n+3$, $8n+5$, $8n+7$.

(a’)

Let $S=\{p_1,p_2,\dots ,p_k\}$ a finite set of prime numbers of the form $8n+1$, and consider $$N={(2p_1{p}_2\cdots p_k)}^4+1.$$

Since $N>1$ is odd, $N$ has an odd prime divisor $p$, which is of the form $8n+1$ by part (d).

Moreover $p\notin S$, otherwise $p\mid 1$. This shows that the set of prime numbers of the form $8k+1$ is not finite.

(b’)

Let $S=\{p_1,p_2,\dots ,p_k\}$ a finite set of prime numbers of the form $8k+3$, and consider $$N={(p_1{p}_2\cdots p_k)}^2+2.$$

Since $N$ is odd, every prime factor of $N$ is odd, so by part (c), every prime factor of $N$ is of the form $8k+1$ or $8k+3$. If all prime divisors of $N$ are of the form $8k+1$, then $N\equiv 1(\mathit{mod}8)$, but $N\equiv 3^{2k}+2\equiv 9^k+2\equiv 3(\mathit{mod}8)$, thus there is some prime divisor $p$ of $N$ of the form $8k+3$.

Moreover $p\notin S$, otherwise $p\mid 2$, and this is impossible since $p$ is odd. This shows that the set of prime numbers of the form $8k+3$ is not finite.

(c’)

Let $S=\{p_1,p_2,\dots ,p_k\}$ a finite set of prime numbers of the form $8n+5$, and consider $$N={(2p_1{p}_2\cdots p_k)}^2+1.$$

Since $N$ is odd, the prime factors of $N$ are of the form $8k+1$ or $8k+5$ by part (a). If all prime divisors of $N$ are of the form $8k+1$, then $N\equiv 1(\mathit{mod}8)$, but $N\equiv 2\cdot 5^{2k}\equiv 2\cdot 25^k\equiv 2(\mathit{mod}8)$, thus there is some prime divisor $p$ of $N$ of the form $8n+5$.

Moreover $p\notin S$, otherwise $p\mid 1$. This shows that the set of prime numbers of the form $8n+5$ is not finite.

(d’)

Let $S=\{p_1,p_2,\dots ,p_k\}$ a finite set of prime numbers of the form $8n+7$, and consider $$N={(p_1{p}_2\cdots p_k)}^2-2.$$

Since $N$ is odd, every prime factor of $N$ is odd, so by part (b), every prime factor of $N$ is of the form $8k+1$ or $8k+7$. If all prime divisors of $N$ are of the form $8k+1$, then $N\equiv 1(\mathit{mod}8)$, but $N\equiv 7^{2k}-2\equiv 49^k-2\equiv -1(\mathit{mod}8)$, thus there is some prime divisor $p$ of $N$ of the form $8k+7$.

Moreover $p\notin S$, otherwise $p\mid 2$, and this is impossible since $p$ is odd. This shows that the set of prime numbers of the form $8n+7$ is not finite.