# Elementary Number Theory Problems 3.3 Solution (David M. Burton's 7th Edition) - Q13

My Solution for "Apply the same method of proof as in Theorem 3.6 to show that there are infinitely many primes of the form $6n + 5$."

## 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

MathNumber TheorySolution