Elementary Number Theory Problems 3.2 Solution (David M. Burton's 7th Edition) - Q7


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)

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

Modify Euclid's proof that there are infinitely many primes by assuming the existence of a largest prime $p$ and using the integer $N = p! + 1$ to arrive at a contradiction.

Solution

Assume there exists a largest prime $p$.

Let $N = p! + 1$. Because $N \gt 1$, by Theorem 3.2 there exists a prime $q$ such that $q \mid N$. Since $p$ is the largest prime, so we know $q \mid p!$. Thus $q \mid N - p! = 1$. The only positive divisor of the integer $1$ is $1$ itself, and because $q \gt 1$ by the Definition 3.1 (Definition of Prime), a contradiction arises.


Read More: All My Solutions for This Book

< Chapter 3.2, Q6 Chapter 3.2, Q8 >