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.
Here is a translation of the definition in terms of the GCD.
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).
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, .
We now like to present and prove the Unique Factorization Theorem. To do this, we need establish the following technical lemma.
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.
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 .