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 {+:\mathbb{Z}\times\mathbb{Z}\rightarrow\mathbb{Z}} and product {\cdot:\mathbb{Z}\times\mathbb{Z}\rightarrow\mathbb{Z}} on {\mathbb{Z}} satisfying the following associative, commutative and distributive laws:

1. Associative Laws: For all {a,b,c\in\mathbb{Z}}, we have {a+(b+c)=(a+b)+c} and {a\cdot(b\cdot c)=(a\cdot b)\cdot c}.

2. Commutative Laws: For all {a,b\in\mathbb{Z}}, we have {a+b=b+a} and {a\cdot b=b\cdot a}.

3. Distributive Law: For all {a,b,c\in\mathbb{Z}}, we have {a\cdot(b+c)=a\cdot b+a\cdot c} and {(a+b)\cdot c=a\cdot c+b\cdot c}.

Remark 1 Let {a,b,c\in\mathbb{Z}}. Since the addition {+} and multiplication {\cdot} are well-defined functions, the equality {b=c} gives us two equalities {a+b=a+c} and {a\cdot b=a\cdot c.}

Axiom 2 Existence of the Identities: There are unique integers {0} and {1} {(0\neq1)} having the properties that

1. {a+0=a} and {0+a=a} for all integers {a}, and

2. {1\cdot a=a} and {a\cdot1=a} for all integers {a}.

Remark 2 The assumption {0\neq1} is a part of Axiom 2.

Axiom 3 Existence and uniqueness of the additive inverse: For each integer {a}, there is a unique integer {a'} such that {a+a'=0} and {a'+a=0}; we refer to the integer {a'} by {-a} (the "negative of {a}").

In most cases, we cannot divide one integer by another integer to obtain an integer (for example, {1\div2} is not an integer but a rational number {1/2}). But when {2a=2b} for some integers {a} and {b}, we can "cancel" the integer {2} from the both sides of the equation, then claim {a=b}. The Axiom 4 ensures us that this cancellation is legal.

Lemma 1 (The Cancellation Law for the Sum) Let {a,b,c\in\mathbb{Z}}. If {a+b=a+c}, then {b=c}.

Proof: Let {a,b,c\in\mathbb{Z}}. Assume that {a+b=a+c}. Then {-a+(a+b)=-a+(a+c);(-a+a)+b=(-a+a)+c;0+b=0+c;} so, {b=c}.\Box

Axiom 4 Cancellation Law (for the product): For any {a,b,c\in\mathbb{Z}}, if {a\neq0} and {a\cdot b=a\cdot c}, then {b=c}.

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

Proposition 1 Let {a,b\in\mathbb{Z}}. If {a\cdot b=0}, then {a=0} or {b=0}.

Proof: (proof by contradiction) Let {a,b\in\mathbb{Z}}. Assume that {a\cdot b=0}. Suppose further that {a\neq0} and {b\neq0}. Then {a\cdot b=0} implies {a\cdot b=a\cdot0}. Since {a\neq0} by the supposition, {b=0} by the cancellation law; this is a contradiction to the supposition. Thus, {a=0} or {b=0}.\Box

Axiom 5 There is a subset {\mathbb{N}} of the set of all integers {\mathbb{Z}}, whose members will be called positive integers (or, natural numbers), with the following properties:

1. (The Closure of {\mathbb{N}} under {+} and {\cdot}) For any {a,b\in\mathbb{N}}, we have {a+b\in\mathbb{N}} and {a\cdot b\in\mathbb{N}}.

2. (The Trichotomy Law) For each {a\in\mathbb{Z}}, exactly one of the following conditions holds:

    i. {a\in\mathbb{N}}.

    ii. {a=0}.

    iii. {-a\in N}.

Remark 3 As we may expect, we call an integer {a\in\mathbb{Z}} a negative integer, if {-a\in\mathbb{N}}.

Remark 4 The closure of {\mathbb{N}} under {+} means: If {a,b\in\mathbb{N}}, then {a+b\in\mathbb{N}}. Similarly, the closure of {\mathbb{N}} under {\cdot} means: If {a,b\in\mathbb{N}}, then {a\cdot b\in\mathbb{N}}. In general, the closure of a subset set under a binary operation can be defined as below.

Definition 1 Let {X} be a set and {*:X\times X\rightarrow X} be a binary operation on {X}. Let {S\subset X}. We say that the subset {S} is closed under the binary operation {*}, if {a*b\in S} for any {a,b\in S}.

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

Definition 2 We say that {a} is less (or smaller) than {b}, denoted by {a<b} (or, sometimes, {b>a}), if {b-a} is a positive integer (i.e., {b-a\in\mathbb{N}}). We say that {a} is less than or equal to {b}, denoted {a\leq b}, if {b-a} is a positive integer or {a=b}.

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

Definition 3 We define the absolute value of an integer {a} to be

\displaystyle  |a|\begin{cases} 0 & if\: a=0\\ a & if\: a\in\mathbb{N}\\ -a & if\:-a\in\mathbb{N}\end{cases}.

Remark 5 Note that, if {a\in\mathbb{Z}}, then {|a|=0} or {|a|\in\mathbb{N}}.

We can also define a notion of the betweenness.

Definition 4 Let {a,b,c\in\mathbb{Z}}. We say that the integer {b} is between {a} and {c}, if {a<b} and {b<c}. When this is the case, we write {a<b<c}.

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 {0} and {1}. Recall that the set of all natural numbers {\mathbb{N}} is defined in the Axiom 5: Axiom of Order.

Axiom 6 The Well-Ordering Principle: If {S} is a nonempty subset of {\mathbb{N}}, then there is a positive integer {a\in S} such that {a\leq b} for every element {b\in S}.

— 2. Divisibility —

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

Definition 5 Let {a,b\in\mathbb{Z}} such that {a\neq0}. We say that {a} divides {b} (or, {b} is divisible by {a}), denoted {a|b}, if there is an integer {q\in\mathbb{Z}} such that {b=aq}. If {a} does not divide {b}, then we denote this fact by {a\nmid b}.

Theorem 1 (The Division Algorithm for Integers) If {a,b\in\mathbb{Z}} such that {a\neq0}, then there is a unique pair of integers {q} and {r} such that {b=a\cdot q+r} and {0\leq r<|a|}.

Recall that {q} is called the quotient and r is called the remainder.

Remark 6 According to the above theorem, the remainder {r} is the nonnegative integer between {0} and {|a|} (including {0} but not {|a|}).

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

Proposition 2 Let {a,b\in\mathbb{Z}} such that {a\neq0}. {a\nmid b} iff there are integers {q,r\in\mathbb{Z}} such that {b=aq+r} and {0<r<|a|}.

Proof: (Implication) Let {a,b\in\mathbb{Z}} such that {a\neq0}. Assume that {a\nmid b}. Then we know that we cannot write {b} as the product of {a} and another integer. Now, by the Division Algorithm, there is a unique pair of integers {q,r\in\mathbb{Z}} such that {b=aq+r} and {0\leq r<|a|}. Since {a\nmid b}, we must have {r\neq0}. So, {b=aq+r} and {0<r<|a|}.

(Converse) Let {a,b\in\mathbb{Z}} such that {a\neq0}. Assume that there are integers {q,r\in\mathbb{Z}} such that {b=aq+r} and {0<r<|a|}. Suppose that {a|b}. Then, there is an integer {x} such that {b=ax+0}. Thus, we have two distinct pairs of integers {s,t\in\mathbb{Z}} such that {b=as+t} and {0\leq t<|a|}. This is a contradiction, since the Division Algorithm states that there is a unique pair of integers {s,t\in\mathbb{Z}} such that {b=as+t} and {0\le t<|a|}. So, {a\nmid b}. \Box

— 3. Primes —

Definition 6 Let {p\in\mathbb{N}} such that {p\neq1}. {p} is called prime, if the only positive divisors of {p} (i.e., {m\in\mathbb{N}} such that {m|p}) is {1} and {p}. Let {n\in N} such that {n\neq1}.

Definition 7 Let {n\in\mathbb{N}} such that {n\neq1}. {n} is called composite, if {n} is not prime.

Remark 7 In this note, a prime number is a natural number. So, {p>1}.

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

Definition 8 Let {a,b\in\mathbb{Z}} such that {a\neq0} and {b\neq0}. Then the greatest common divisor (GCD) of {a} and {b}, denoted by {gcd(a,b)}, is the positive integer {d\in\mathbb{N}} satisfying the following two conditions:

1. {d|a} and {d|b}.

2. If {k\in\mathbb{Z}} such that {k\ne0}, {k|a} and {k|b}, then {k|d}.

Note that the condition {1} says {gcd(a,b)} is a common divisor of {a} and {b}, while the condition {2} tells us that if {k} is a common divisor of {a} and {b}, then {k} divides {gcd(a,b)}; this will yield that {gcd(a,b)} is the largest common divisor of {a} and {b}. It is clear that {gcd(a,b)=gcd(b,a)}.

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

Lemma 2 Let {n\in\mathbb{Z}} such that {n\neq0} and {p\in\mathbb{N}}. If {p} is prime, then {gcd(n,p)=1} or {gcd(n,p)=p}.

Proof: Let {n\in\mathbb{Z}} such that {n\neq0} and {p\in\mathbb{N}}. Assume that {p} is a prime number. Note that {gcd(n,p)} divides {p}, and it is positive. Since {p} is prime, we must have either {gcd(n,p)=1} or {gcd(n,p)=p}. \Box

Let us establish the well-known fact: Every natural number, except {1}, is divisible by a prime number. The proof below demonstrates the use of Well-Ordering Principle.

Proposition 3 If {n\in N} such that {n\neq1}, then there is a prime {p\in N} such that {p|n}.

Proof: Let {n\in\mathbb{N}} such that {n\neq1}. Let {D=\{d\in\mathbb{N}:d\neq1\; and\; d|n\}}. Note that {D} is not the empty set, since {n} is a natural number not equal to {1} and {n|n}. So, by the Well-Ordering Principle, {D} contains the least element; let us use {p} to denote the least element of {D}. We now like to show that {p} is prime. Since {p} is an element of {D}, {p} is a natural number, and {p\neq1}. Now, suppose {p} is not a prime. Then, since {p\neq1}, it must be a composite number. So, there is {s,t\in\mathbb{N}} such that {s,t\neq1} and {st=p}. So, {s|p}. Thus, {s|n}. Thus, {s\in D}. Note that, since {st=p} and {s,t\neq1}, we have {s<p} (note: {s=1\cdot s<2\cdot s\leq t\cdot s=p}). This is a contradiction, since {p} is the smallest element in {D}. Thus, {p} cannot be composite. Since {p\neq1}, it must be prime. \Box

— 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 {1}, is a product of primes, is a corollary (Hardy and Wright 1979).

Theorem 2 (Euclid’s First Theorem) Let {p\in\mathbb{N}} such that {p\neq1}. {p} is prime iff, for any {a,b\in Z} such that {p|ab}, we have {p|a} or {p|b}.

Proof: (Implication) Let {p\in\mathbb{N}} such that {p} is prime. Let {a,b\in\mathbb{Z}}. Assume that {p|ab}. Note that if {a=0}, then {p|a}. Thus, assume further that {a\neq0}. Now, if {p|a}, then we again have nothing to prove. So, assume that {p\nmid a}. Then {gcd(p,a)=1}. So {p|b} by the previous lemma.

(Converse) Let{p\in\mathbb{N}} such that {p\neq1}. Assume the condition: for any {a,b\in\mathbb{Z}} such that {p|ab}, we have {p|a} or {p|b}. Let {n\in\mathbb{N}} such that {n|p}. Our goal is to show that {n=1} or {n=p}. If {n=1}, then we have nothing to show; so, assume that {n\neq1}. Now, there is {s\in\mathbb{Z}} such that {p=ns}. Since {n,p\in\mathbb{N}}, {s\in\mathbb{Z}}. Note that {p|ns}. So, {p|n} or {p|s}. If {p|s}, then {1<n} implies {s<ns=p}. This is a contradiction, since {p|s}. So, {p\nmid s}. Thus, {p|n} by the assumption. Thus, there is {t\in\mathbb{Z}} such that {n=pt}. Note that {t\in\mathbb{N}}, since {n,p\in\mathbb{N}}. Since {p=ns}, we have {n=nst}. By the cancellation law, we have {1=st}; so, {s=1} and {t=1}. Hence, {n=p}.\Box

Proposition 4 Let {p,q\in\mathbb{N}} be distinct prime numbers, and {x\in\mathbb{Z}}. If {p|x} and {q|x}, then {pq|x}.

Proof: Let {p,q\in\mathbb{N}} be distinct prime numbers, and {x\in\mathbb{Z}}. Assume that {p|x} and {q|x}. Then there is {n\in\mathbb{Z}} such that {x=pn}. Since {q|x}, we have {q|pn}. So, {q|p} or {q|n}. Since {p} and {q} are distinct primes, {q\nmid p}. This implies {q|n}. Thus, there is {m\in\mathbb{Z}} such that {n=qm}. Hence, {x=pn=p(qm)}. Consequently, {pq|x}. \Box

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

Lemma 3 Let {n\in\mathbb{N}} such that {n\neq1}. If {p_{1},\cdots,p_{s}\in\mathbb{N}} are all primes such that {p_{1}<p_{2}<\cdot\cdot\cdot<p_{s}}, {q_{1},\cdots,q_{t}\in\mathbb{N}} are all primes such that {q_{1}<q_{2}<\cdots<q_{t}}, a sequence of integers {\alpha_{1},\cdots,\alpha_{s}\in\mathbb{N}}, and a sequence of integers {\beta_{1},\cdots,\beta_{t}\in\mathbb{N}} such that

\displaystyle  n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{s}^{\alpha_{s}}=q_{1}^{\beta_{1}}q_{2}^{\beta_{2}}\cdots q_{t}^{\beta_{t}},

then {s=t} and {p_{i}=q_{i}}.

Proof: Let {n\in\mathbb{N}} such that {n\neq1}. Assume that there are two sequence of primes {p_{1}<p_{2}<\cdot\cdot\cdot<p_{s}} and {q_{1}<q_{2}<\cdots<q_{t}}, and two sequences of natural numbers {\alpha_{1},\cdots,\alpha_{s}} and {\beta_{1},\cdots,\beta_{t}} such that

\displaystyle  n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{s}^{\alpha_{s}}=q_{1}^{\beta_{1}}q_{2}^{\beta_{2}}\cdots q_{t}^{\beta_{t}}.

Suppose that there is a prime that shows up in one of the list but not in the other. Say the prime {p} shows up in {p_{1}<p_{2}<\cdot\cdot\cdot<p_{s}}, but not in {q_{1}<q_{2}<\cdots<q_{t}} (other case is verbatim). Since {p|n}, we have {p|(q_{1}^{\beta_{1}}q_{2}^{\beta_{2}}\cdots q_{t}^{\beta_{t}})}. Since {p} is prime, {p} must divide one of {q_{i}}. But this is a contradiction, since each {q_{i}} is a prime different from {p}. Thus, all the primes showing up in one list must show up in the other. Hence, {p_{1}<p_{2}<\cdot\cdot\cdot<p_{s}} and {q_{1}<q_{2}<\cdots<q_{t}} are the same lists of primes. \Box

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

Theorem 3 (Unique Factorization Theorem) Let {n\in\mathbb{N}} such that {n\neq1}. There are unique primes {p_{1},\cdots,p_{s}\in\mathbb{Z}} such that {p_{1}<p_{2}<\cdot\cdot\cdot<p_{s}} and unique sequence of positive integers {\alpha_{1},\cdots,\alpha_{s}\in\mathbb{N}}, such that

\displaystyle  n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{s}^{\alpha_{s}}.

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 {F} be the set of all positive integers strictly greater than {1} (i.e., {>1}) that cannot be written as the product of primes (if {p} is prime, then we count it as the "product" of a prime). Suppose {F} is not empty. Then there is the least element {l} in {F}.

Let {n\in\mathbb{N}} such that {n<l}. Suppose {n|l}. Then {l=nm} for some {m\in\mathbb{N}}. Since {n} and {m} are not in {F} (it is smaller than {l}), {n} and {m} can be written as the product of primes. So, {l} can be written as the product of primes. This is a contradiction. So, {l} is not divisible by any number between {1} and {l}. So, {l} is a prime. This is a contradiction, since {l\in F}. Thus, {F} is empty. Hence, every number can be written as the product of primes.

Proof of uniqueness. Let {n\in N} such that {n\neq1}. Assume that there are two sequences of primes {p_{1}<p_{2}<\cdot\cdot\cdot<p_{s}} and {q_{1}<q_{2}<\cdots<q_{t}}, and two sequences of positive integers {\alpha_{1},\cdots,\alpha_{s}\in\mathbb{N}} and {\beta_{1},\cdots,\beta_{t}\in\mathbb{N}} such that

\displaystyle  n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{s}^{\alpha_{s}}=q_{1}^{\beta_{1}}q_{2}^{\beta_{2}}\cdots q_{t}^{\beta_{t}}.

By the previous lemma, {p_{1}<p_{2}<\cdot\cdot\cdot<p_{s}} and {q_{1}<q_{2}<\cdots<q_{t}} are the same lists of primes. Thus, we now have

\displaystyle  n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{s}^{\alpha_{s}}=p_{1}^{\beta_{1}}p_{2}^{\beta_{2}}\cdots p_{s}^{\beta_{s}}.

Suppose {i} is the smallest natural number such that {\alpha_{i}\neq\beta_{i}}. Suppose {\alpha_{i}<\beta_{i}}. Let {k=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{i}^{\alpha_{i}}}. Let {m=\frac{n}{k}}. Then

\displaystyle  m=p_{i+1}^{\alpha_{i+1}}p_{i+2}^{\alpha_{i+2}}\cdots p_{s}^{\alpha_{s}}=p_{i}^{\beta_{i}-\alpha_{i}}p_{i+1}^{\beta_{i+1}}\cdots p_{s}^{\beta_{s}}.

But this contradicts the previous lemma, since {p_{i}} does not show up in the list of primes {p_{i+1}<\cdots<p_{s}} for {m}, but does show up in the list {p_{i}<\cdots<p_{s}} for {m}. Similarly, {\beta_{i}<\alpha_{i}} implies the same contradiction. Hence, there is no {i} such that {\alpha_{i}\neq\beta_{i}}. Consequently, {\alpha_{i}=\beta_{i}} for all {1\leq i\leq s}. \Box

— 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 {\{p_{1},\cdots,p_{r}\}} of primes, consider the number {n=p_{1}p_{2\cdots}p_{r}+1}. This {n} has a prime divisor {p}. But {p} is not one of the {p_{i}}: otherwise {p} would be a divisor of {n} and of the product {p_{1}p_{2}\cdots p_{r}}, and thus also of the difference {n-p_{1}p_{2}\cdots p_{r}=1}, which is impossible. So a finite set {\{p_{1},\cdots,p_{r}\}} cannot be the collection of all prime numbers. \Box

Advertisements