I have re-posted this to test my changes to the latex2wp.py and terrystyle.py programs, compiled with Python Software Foundation’s Python 2.7.2 64 bit version, to add support for LyX 1.6.9. The code change incorporates some additional theorem-like environments, macros, font styles, and the numbering has been change so that the different theorem-like types each have a separate counter (e.g., theorem 1, theorem 2, lemma 1, proposition 1, theorem 3, lemma 2, …, as opposed to theorem 1, theorem 2, lemma 3, proposition 4, …). Furthermore, I have provided more background information which will benefit those without a background in abstract algebra.
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.
— 1. Axioms of Integers —
We begin with the Axioms of Integers to define the set of all integers as we know it. The Axioms of Integers come in six Axioms, grouped as Algebraic Axioms (Axiom 1 through Axiom 4), Order Axiom (Axiom 5) and Well-Ordering Principle (Axiom 6). We have seen most of these statements introduced in Elementary School through High School, but some of them may be assumed, but never have been stated explicitly.
In most cases, we cannot divide one integer by another integer to obtain an integer (for example, is not an integer but a rational number ). But when for some integers and , we can "cancel" the integer from the both sides of the equation, then claim . The Axiom 4 ensures us that this cancellation is legal.
Now, the Cancellation Law implies the following very important fact.
Using the Axiom 5, we can introduce the order relation among the integers.
Using the Axiom 5, we can also define the absolute value of an integer.
We can also define a notion of the betweenness.
Next we introduce the Well-Ordering Principle. It implies very important facts: The Division Algorithm and Principle of Induction. Also, without this axiom, we can not ensure such a basic fact as there is no integer between and . Recall that the set of all natural numbers is defined in the Axiom 5: Axiom of Order.
— 2. Divisibility —
Next we consider the divisibility relations among integers. First, let us recall the definition of the divisibility.
Recall that is called the quotient and r is called the remainder.
Using the Division Algorithm, we can characterize the nondivisibility more practically as follows.
(Converse) Let such that . Assume that there are integers such that and . Suppose that . Then, there is an integer such that . Thus, we have two distinct pairs of integers such that and . This is a contradiction, since the Division Algorithm states that there is a unique pair of integers such that and . So, .
— 3. Primes —
Let us recall the definition of the greatest common divisor of a pair of nonzero integers.
Note that the condition says is a common divisor of and , while the condition tells us that if is a common divisor of and , then divides ; this will yield that is the largest common divisor of and . It is clear that .
Here is a translation of the definition of a prime number in terms of the GCD.
Let us establish the well-known fact: Every natural number, except , is divisible by a prime number. The proof below demonstrates the use of Well-Ordering Principle.
— 4. Unique Factorization Theorem —
The next theorem is the fundamental connection between prime numbers and the divisibility relation. The theorem is sometimes called Euclid’s First Theorem or Euclid’s Principle. The Fundamental Theorem of Arithmetic or the Unique Factorization Theorem, which establishes the fact that every natural number, except , is a product of primes, is a corollary (Hardy and Wright 1979).
(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 .
— 5. Infinitude of Primes Theorem —
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.