Elementary Number Theory Problems 3.3 Solution (David M. Burton's 7th Edition) - Q13
Background
All theorems, corollaries, and definitions listed in the book's order:
I will only use theorems or facts that are proved before this question. So you will not see that I quote theorems or facts from the later chapters.
Question
Apply the same method of proof as in Theorem 3.6 to show that there are infinitely many primes of the form $6n + 5$.
Solution
In anticipation of a contradiction, let us assume that there exist only finitely many primes of the form $6n + 5$; call them $q_{1}, q_{2}, ..., q_{s}$. Consider the positive integer
$$ N = 6q_{1}q_{2} \cdots q_{s} - 1 = 6(q_{1}q_{2} \cdots q_{s} - 1) + 5 $$and let $N = r_{1}r_{2} \cdots r_{t}$ be its prime factorization. Because $N$ is an odd integer, we have $r_{i} \neq 2$ for all $i$, so that each $r_{i}$ is either of the form $6n + 1$, $6n + 3$ or $6n + 5$.
$6n + 3$ has a factor $3$, the only prime will be $3$ if $r_{i}$ is of this form. But
$$ \begin{equation} \begin{split} N & = 6(q_{1}q_{2} \cdots q_{s} - 1) + 5 \\ & = 3(2q_{1}q_{2} \cdots q_{s} - 2) + 3 + 2 \\ & = 3(2q_{1}q_{2} \cdots q_{s} - 1) + 2 \end{split} \nonumber \end{equation} $$By Theorem 2.1 Division Algorithm, $3 \not \mid N$. Thus $r_{i}$ can be either of the form $6n + 1$ or $6n + 5$.
For $6n + 1$ and some integer $m$, $(6n + 1)(6m + 1) = 36nm + 12nm + 1 = 6(6nm + 2nm) + 1$. So, the product of two or more integers of the form $6n + 1$ is of the same form.
For $N$ to take the form $6n + 5$, as it clearly does, $N$ must contain at least one prime factor $r_{i}$ of the form $6n + 5$. If $r_{i}$ can be found among the listing $q_{1}, q_{2}, ..., q_{s}$, then $r_{i} \mid 6q_{1}q_{2} \cdots q_{s}$. By Theorem 2.2(g), $r_{i} \mid 6q_{1}q_{2} \cdots q_{s} - N = 1$. But this causes a contradiction. The only possible conclusion is that there are infinitely many primes of the form $6n + 5$.
Read More: All My Solutions for This Book