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.

**Axiom 1**There are two binary operations the sum and product on satisfying the following associative, commutative and distributive laws:

1. Associative Laws: For all , we have and .

2. Commutative Laws: For all , we have and .

3. Distributive Law: For all , we have and .

**Remark 1**Let . Since the addition and multiplication are well-defined functions, the equality gives us two equalities and

**Axiom 2**Existence of the Identities: There are unique integers and having the properties that

1. and for all integers , and

2. and for all integers .

**Remark 2**The assumption is a part of Axiom 2.

**Axiom 3**Existence and uniqueness of the additive inverse: For each integer , there is a unique integer such that and ; we refer to the integer by (the "negative of ").

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.

**Lemma 1**(The Cancellation Law for the Sum) Let . If , then .

**Proof:**Let . Assume that . Then so, .

**Axiom 4**Cancellation Law (for the product): For any , if and , then .

Now, the Cancellation Law implies the following very important fact.

**Proposition 1**Let . If , then or .

**Proof:**(proof by contradiction) Let . Assume that . Suppose further that and . Then implies . Since by the supposition, by the cancellation law; this is a contradiction to the supposition. Thus, or .

**Axiom 5**There is a subset of the set of all integers , whose members will be called

**positive**integers (or,

**natural**

**numbers**), with the following properties:

1. (The Closure of under and ) For any , we have and .

2. (The Trichotomy Law) For each , exactly one of the following conditions holds:

i. .

ii. .

iii. .

**Remark 3**As we may expect, we call an integer a

**negative**integer, if .

**Remark 4**The closure of under means: If , then . Similarly, the closure of under means: If , then . In general, the closure of a subset set under a binary operation can be defined as below.

**Definition 1**Let be a set and be a binary operation on . Let . We say that the subset is

**closed**under the binary operation , if for any .

Using the Axiom 5, we can introduce the order relation among the integers.

**Definition 2**We say that is

**less**(or

**smaller**) than , denoted by (or, sometimes, ), if is a positive integer (i.e., ). We say that is

**less than**

**or equal**to , denoted , if is a positive integer or .

Using the Axiom 5, we can also define the absolute value of an integer.

**Definition 3**We define the

**absolute value**of an integer to be

**Remark 5**Note that, if , then or .

We can also define a notion of the betweenness.

**Definition 4**Let . We say that the integer is

**between**and , if and . When this is the case, we write .

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.

**Axiom 6**The Well-Ordering Principle: If is a nonempty subset of , then there is a positive integer such that for every element .

** — 2. Divisibility — **

Next we consider the divisibility relations among integers. First, let us recall the definition of the divisibility.

**Definition 5**Let such that . We say that divides (or, is divisible by ), denoted , if there is an integer such that . If does not divide , then we denote this fact by .

**Theorem 1**(The Division Algorithm for Integers) If such that , then there is a unique pair of integers and such that and .

Recall that is called the **quotient** and r is called the **remainder**.

**Remark 6**According to the above theorem, the remainder is the nonnegative integer between and (including but not ).

Using the Division Algorithm, we can characterize the nondivisibility more practically as follows.

**Proposition 2**Let such that . iff there are integers such that and .

**Proof:**(Implication) Let such that . Assume that . Then we know that we cannot write as the product of and another integer. Now, by the Division Algorithm, there is a unique pair of integers such that and . Since , we must have . So, and .

(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 — **

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

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

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

**composite**, if is not prime.

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

Let us recall the definition of the greatest common divisor of a pair of nonzero integers.

**Definition 8**Let such that and . Then the greatest common divisor (GCD) of and , denoted by , is the positive integer satisfying the following two conditions:

1. and .

2. If such that , and , then .

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.

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

**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 .

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.

**Proposition 3**If such that , then there is a prime such that .

**Proof:**Let such that . Let . Note that is not the empty set, since is a natural number not equal to and . So, by the Well-Ordering Principle, contains the least element; let us use to denote the least element of . We now like to show that is prime. Since is an element of , is a natural number, and . Now, suppose is not a prime. Then, since , it must be a composite number. So, there is such that and . So, . Thus, . Thus, . Note that, since and , we have (note: ). This is a contradiction, since is the smallest element in . Thus, cannot be composite. Since , it must be prime.

** — 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).

**Theorem 2**(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 4**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 3**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 3**(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 .

** — 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.

**Theorem 4**(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