Exercise 1.3.26 (There are infinitely many primes of the form $4n+3$; of the form $6n+5$)

Proof.

Let $p_1,p_2,\dots ,p_r$ be prime numbers of the form $4n+3$. Consider

$$N=4p_1{p}_2\cdots p_r-1.$$ $N$ is odd, so $2\nmid N$. Every prime factor of $N$ is of the form $4k+1$ or $4k+3$, and these two cases are mutually exclusive. If all the prime factors of $N$ are of the form $4k+1$, then $N$ itself is of the form $4k+1$ (see Problem 10). But $N$ is of the form $4k+3$. This is impossible, therefore it exists some prime factor $p$ of $N$ of the form $p=4k+3$. Moreover $p\notin \{p_1,p_2,\dots ,p_r\}$, otherwise $p\mid 4p_1{p}_2\cdots p_r-N=1$. Thus a finite set $\{p_1,p_2,\dots ,p_r\}$ of primes of the form $4k+3$ cannot contain all such primes. There are infinitely many primes of the form $4n+3$. Very similarly, let $p_1,p_2,\dots ,p_r$ be prime numbers of the form $6n+5$. Consider $$N=6p_1{p}_2\cdots p_r-1.$$ Then $2\nmid N$, and $3\nmid N$. Therefore every prime factor of $N$ is of the form $6k+1$ or $6k+5$, and these two cases are mutually exclusive. If all the prime factors of $N$ are of the form $6k+1$, then $N$ itself is of the form $6k+1$(see Problem 10). But $N$ is of the form $6k+5$. This is impossible, therefore it exists some prime factor $p$ of $N$ of the form $p=6k+5$. Moreover $p\notin \{p_1,p_2,\dots ,p_r\}$, otherwise $p\mid 6p_1{p}_2\cdots p_r-N=1$. Thus a finite set $\{p_1,p_2,\dots ,p_r\}$ of primes of the form $6k+5$ cannot contain all such primes. There are infinitely many primes of the form $6n+5$. □