*Proofs from THE BOOK* by Martin Aigner and Günter Ziegler begins by giving six proofs of the infinity of primes. The first proof is what they call “the oldest Book Proof” attributed to Euclid. Before we go over this proof, lets cover some background.

**Definition 1**Let such that . is called

*prime*, if the only positive divisors of (i.e., such that ) is and .

**Definition 2**Let such that . is called

*composite*, if is not prime.

**Remark 1**In this note, a prime number is a natural number. So, .

Here is a translation of the definition in terms of the GCD.

**Lemma 3**Let such that and . If is prime, then or .

**Proof:**Proof. Let such that and . Assume that is a prime number. Note that divides , and it is positive. Since is prime, we must have either or .

The next theorem is the fundamental connection between prime numbers and the divisibility relation among integers. The theorem is sometimes called Euclid’s First Theorem or Euclid’s Principle. A corollary is the Fundamental Theorem of Arithmetic or the Unique Factorization Theorem (Hardy and Wright 1979).

**Theorem 4**(Euclid’s First Theorem) Let such that . is prime iff, for any such that , we have or .

**Proof:**(Implication) Let such that is prime. Let . Assume that . Note that if , then . Thus, assume further that .

Now, if , then we again have nothing to prove. So, assume that . Then . So, by the previous lemma.

(Converse) Let such that . Assume the condition: for any such that , we have or .

Let such that . Our goal is to show that or .

If , then we have nothing to show; so, assume that . Now, there is such that . Since , . Note that . So, or . If , then implies . This is a contradiction, since . So, . Thus, by the assumption. Thus, there is such that . Note that , since . Since , we have . By the cancellation law, we have ; so, and . Hence, .

**Proposition 5**Let be distinct prime numbers, and . If and , then .

**Proof:**Let be distinct prime numbers, and . Assume that and . Then there is such that . Since , we have . So, or . Since and are distinct primes, . This implies . Thus, there is such that . Hence, . Consequently, .

We now like to present and prove the Unique Factorization Theorem. To do this, we need establish the following technical lemma.

**Lemma 6**Let such that . If are all primes such that , are all primes such that , a sequence of integers , and a sequence of integers such that

then and .

**Proof:**Let such that . Assume that there are two sequence of primes and , and two sequences of natural numbers and ¯ such that

Suppose that there is a prime that shows up in one of the list but not in the other. Say the prime shows up in , but not in (other case is verbatim). Since , we have . Since is prime, must divide one of . But this is a contradiction, since each is a prime different from . Thus, all the primes showing up in one list must show up in the other. Hence, and are the same lists of primes.

We are now ready to prove the Unique Factorization Theorem for natural numbers.

**Theorem 7**(Unique Factorization Theorem) Let such that . There are unique primes such that and unique sequence of positive integers , such that

**Proof:**We will prove this theorem by proving the existence of prime factorization first, then proving the uniqueness of the prime factorization.

**Proof of existence.** Let be the set of all positive integers strictly greater than (i.e., ) that cannot be written as the product of primes (if is prime, then we count it as the “product” of a prime). Suppose is not empty. Then there is the least element in .

Let such that . Suppose . Then for some . Since and are not in (it is smaller than ), and can be written as the product of primes. So, can be written as the product of primes. This is a contradiction. So, is not divisible by any number between and . So, is a prime. This is a contradiction, since . Thus, is empty. Hence, every number can be written as the product of primes.

**Proof of uniqueness.** Let such that . Assume that there are two sequences of primes and , and two sequences of positive integers and such that

By the previous lemma, and are the same lists of primes. Thus, we now have

Suppose is the smallest natural number such that . Suppose . Let . Let . Then

But this contradicts the previous lemma, since does not show up in the list of primes for , but does show up in the list for . Similarly, implies the same contradiction. Hence, there is no such that . Consequently, for all .

We are now ready to prove Euclid’s Second Theorem, also called the Infinitude of Primes Theorem. It was proved by Euclid in Book IX Proposition 20 of the Elements.

**Theorem 8**(Euclid’s Second Theorem) The number of primes is infinite.

**Proof:**(by contradiction) For any finite set of primes, consider the number . This has a prime divisor . But is not one of the : otherwise would be a divisor of and of the product , and thus also of the difference , which is impossible. So a finite set cannot be the collection of all prime numbers.

## Leave a comment

Comments feed for this article