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:

Theorems and Corollaries in Elementary Number Theory (Ch 1 - 3)

All theorems and corollaries mentioned in David M. Burton’s Elementary Number Theory are listed by following the book’s order. (7th Edition) (Currently Ch 1 - 3)

RanblogRan

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

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

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

Related Pages

< Chapter 3.3, Q12 Chapter 3.3, Q14 >