*Proofs from THE BOOK* by Martin Aigner and Günter Ziegler begins by giving six proofs of the infinity of primes. We will go over the second proof. Before we go over this proof, lets cover some background.

** — 1. Algebraic Structures — **

One of the themes of modern algebra is to compare algebraic structures. An algebraic structure refers to a nonempty set equipped with a binary operation or several binary operations (usually two). Also, we shall refer to a nonempty set equipped with two binary operations satisfying certain properties as a number system. First, we shall define algebraic structures called group, ring and field. A group consists of nonempty set with one binary operation satisfying several conditions. It is the simplest of the three.

**Definition 1**Let be a nonempty set and be a binary operation on Then the set together with the binary operation , denoted, is a

**group**, if the following three conditions are satisfied:

i. The binary operation is associative, i.e., for all .

ii. There is a -identity , i.e., for all .

iii. For each , there is a -inverse , i.e., , where is the -identity.

Further more, a group is said to be **commutative** (or **abelian**), if the binary operation is commutative.

**Example 1**Note that the set of all integers together with the ordinary addition is a commutative group. Note that is associative and commutative, while is the -identity. Also, for the -inverse is

**Example 2**Note that the set of all integers together with the ordinary subtraction is not a group. The binary operation is not associative.

**Example 3**Note that the set of all integers together with the ordinary multiplication is not a group. There are no -inverses.

**Example 4**Note that the set of all natural numbers together with the ordinary subtraction is not a group. is associative and commutative, but does not contain -identity.

**Example 5**Note that the set of all real numbers together with the ordinary multiplication is not a group. The multiplication is associative and commutative on , while is the multiplicative idenity. However, has no -inverse.

**Example 6**Note that the set of all positive real numbers (denoted ) together with the ordinary multiplication is a commutative group. The multiplication is associative and commutative on , while is the multiplicative identity. Note that every element in has the multiplicative inverse.

Most binary operations fail to form a group structure on a set. Now, the ring and field are nonempty sets equipped with two binary operations. They contain the structure of commuative group as a part of their structures.

**Definition 2**Let be a nonempty set, and and be two binary operations on The triple is called a

**ring**, if it satisfies the following three conditions:

i. is a commutative group.

ii. is associative.

iii. and for all

Furthermore, if the operation is commutative, then the ring is called a **commutative** **ring**.

**Remark 1**If is a ring, then the -identity, which exists by condition i, is referred to as the additive identity or zero of the ring.

**Remark 2**The condition iii is often referred to by the statement: "the multiplication distributes over the addition from the left, and from the right."

**Example 7**Note that the set of all integers together with the ordinary addition and ordinary multiplication is a commutative ring. As we will see , it satisfies more "axioms".

**Example 8**Note that the set of all natural numbers together with the ordinary addition and ordinary multiplication is not a ring, since is not a commutative group.

**Example 9**Note that the set of all positive real numbers (denoted ) together with the ordinary addition and multiplication is not a ring, since is not a group (it has not -identity in ).

**Example 10**Note that the set of all rational numbers together with the ordinary addition and ordinary multiplication is a commutative ring.

A field is a special form of a commutative ring. One distinguishing feature of the field is that we are allowed to divide by nonzero elements, i.e., every nonzero element has the multiplicative inverse.

**Definition 3**Let be a nonempty set, and and be two binary operations on The commutative ring is called a

**field**, if it satisfies the following two conditions:

i. has the identity element in

ii. Every nonzero element of has the -inverse. [Note: In a ring, the zero element refers to the -identity; so, nonzero elements mean non--identity elements of ]

** — 2. The Axioms of Field — **

Let us summarize, what we have assumed about the ordinary addition and ordinary multiplication on We have and will assume the following Axioms satisfied by The set of all real numbers together with the ordinary addition and multiplication satisfies the following axioms.

**Axiom 1**(Commutativity of ). for all

**Axiom 2**(Associativity of ). for all

**Axiom 3**(-Identity). There is an element in such that for all

**Axiom 4**(-Inverse). For any , there is an element such that . [Note: We usually write for .]

**Axiom 5**(Commutativity of ). for all elements

**Axiom 6**(Associativity of ). for all

**Axiom 7**(-Identity). There is an element (not equal to in

**Axiom 3**) such that for all

**Axiom 8**(-Inverse). For any such that , there is an element such that . [Note: We usually write for .]

**Axiom 9**(Distributivity). for all

Note that the Axioms of Field satisfied by the set of all real numbers indeed makes a field. There are more axioms the field of real numbers satisfies, but we will not use them. Note, the set of natural numbers , set of integers , and the set of all rational numbers are subsets of the set of all real numbers Specifically,

**Example 11**Note that the set of all rational numbers indeed makes a field.

**Example 12**Note that the set of all integers together with the ordinary addition and multiplication is not a field. It has no ·-inverse.

**Example 13**Note that the set of all natural numbers together with the ordinary addition and ordinary multiplication is not a field, since is not a commutative ring.

** — 3. Modulo Arithmetic — **

Now, we shall introduce very useful relations among integers called the congruence relations. They possess essential properties of the equality among integers (we will talk more about this in Section 6 under equivalence relation), and they are very useful computational tools. Here is the definition of the congruence relations on

**Definition 4**Let Let We say that an integer is

**congruent**to an integer modulo , denoted (or, ""), if

**Remark 3**According to the definition above, showing means showing (or, equivalently, showing ).

**Notation 1**Let When an integer is not congruent to an integer modulo n (i.e., ), we denote this fact by (or ).

The next lemma along with the Division Algorithm tells us that an integer is congruent modulo to the remainder of divided by

**Lemma 1**Let and If such that for some , then

**Proof:**Let and Assume that such that for some Note that So, Thus,

Using the Division Algorithm, we can establish that if , then every integer is congruent (modulo ) to a unique integer between and

**Proposition 1**Let If then there is a unique integer such that and

**Proof:**Let and Then, by the Division Algorithm, there is a unique pair of integers such that with So, according to the above lemma, Suppose there is an integer such that and Since there is such that So, with However, the pair and is the unique such pair according to the Division Algorithm. So, must equal and must equal Thus, the integer in the statement of the proposition is unique.

** — 4. The Congruence Classes Modulo : — **

In this section, we introduce the congruence classes modulo of integers, where A congruence class (modulo ) of is the collection of all integers congruent to modulo We then consider the set of all congruence classes, denoted by and define two associative binary operations on

**Definition 5**Let and

We refer to the set as the **congruence class** of modulo Also, denote the set of all congruence classes modulo , i.e.,

**Example 14**Let us find the congruence class of modulo (i.e., in the above definition). According to the definition, the congruence class is a set consisting of all those integers congruent to modulo For example, and belong to (note: is a set), since and Note that (i.e., ) means , or

Conversely, if , then ; so, (i.e., ). Hence, the congruence class is the set of all multiple of , i.e.,

**Example 15**Let us find the congruence class of modulo (i.e., in the above definition). According to the definition, the congruence class consists of all those integers congruent to modulo For example, and belong to (note: is a set), since and Note that (i.e., ) means , or for some integer Thus, for some integer

Conversely, if for some integer , then ; so, (so, ). Thus, the congruence class can be represented as the following set

The next lemma characterizes the congruence classes.

**Lemma 2**Let If then

**Proof:**Let , and

Let . Then . So, . Thus, there is such that . So, . Thus, . Consequently,

Let . Then there is such that . So, . Thus, . So, . Thus, . Consequently, . Thus,

**Example 16**Note that

and

The next proposition tells us that the equality of congruence classes (modulo fixed natural number ) means representatives of each congruent classes are congruent (modulo ) to each other, and vise versa. So, there are multiple ways to represent the same congruence class.

**Proposition 2**Let , and . iff

**Proof:**Let , and .

(Implication). Assume that . Then . So, .

(Converse). Assume that . So, as well. Let . Then and . So, . Thus, . Consequently, . Let . Then and . So, . Thus, . Consequently, . Hence, .

**Remark 4**Replacing "" by the definition "" in the above proposition, we obtain the restatement " iff ". Using this restatement, we obtain , since . Similarly, using the restatement, we see that , since .

**Example 17**According to the previous proposition, we have , since (i.e., ). Also, , since (i.e., ).

As a consequence of the above proposition, we can show that, for a fixed , the set of all congruence classes consists of only distinct congruence classes, namely .

**Proposition 3**If , then

**Proof:**Let . Let . It is clear that . So, let us show that . Let . Then, by the Division Algorithm, there is a unique pair of integers such that with . Since , we have . Also, . Thus, . Hence, .

**Remark 5**We can consider as the set of all possible remainders of an integer divided by . So, is sometime referred to as the collection of

*residue classes*modulo , and refers to the set as the residue class of modulo .

**Remark 6**We can restate the proposition above as: If and then there is such that and . This fact comes from the Division Algorithm. For example, and , since and .

**Example 18**, and

Note that for each , is very closely related to the set of integers , but they have quite different characters. In particular, contains only elements. So, is a finite number system. We will have more to say about this, but let us look at subgroups first.

** — 5. Subgroups — **

Before we cover subgroups, let us cover an extremely usesful preliminary lemma.

**Lemma 3**If is a group, then

a. The identity element of is unique.

b. Every has a unique inverse in

c. For every

d. For all

**Proof:**We start with Part a. We must show that if and for all and for all then This is easy, for then and hence

For Part b we will prove a stronger result., which will have Part b as an immediate consequence. We claim that in a group if then that is, we can cancel a given element from the same side of an equation. To see this, we have, for an element such that Thus from we have

so, by the associative law, that is, Hence

Now to get Part b as an implication of the cancellation result. Suppose that act as inverses for then so by cancellation and we see that the inverse of is unique. We shall always write it as

To see Part c, note that by definition but so by cancellation in we get

Finally, for Part d we calculate

Similary, Hence, by definition,

Note the stronger result proved for Part b above is the following lemma.

**Lemma 4**In any group if and

a. then

b. then

**Definition 6**A nonempty subset of a group is said to be a

**subgroup**of if, under the product in , itself forms a group.

**Lemma 5**A nonempty subset of a the group is a subgroup iff

- implies that
- implies that

**Proof:**If is a subgroup of then it is obvious that 1. and 2. must hold.

Suppose conversely that is subset of for which 1. and 2. hold. In order to establish that is a subgroup, all that is needed is to verify and that the associative law does hold for it holds all the more so for which is a subset of If by part 2 and so by part 1, .

**Example 19**Let be any group and let The set is a subgroup of For, by the roles of exponents, if and then so is in Also, so This makes into a subgroup of

is the *cyclic subgroup* of generated by in the following sense.

**Definition 7**The

**cyclic subgroup**of generated by is the set It is denoted

**Remark 7**If is the identity element of then

In the special case of a finite group we can dispense with part 2 of Lemma 5.

**Lemma 6**If is a nonempty finite subset of a group and is closed under multiplication, then is a subgroup of

**Proof:**In light of the Lemma 5, we need but show that whenever Suppose that thus since is closed. Thus the infinite collection of elements must fit into which is finite subset of Thus there must be repetitions in this collection of elements; that is, for some integers with By the cancellation in (; since and since Thus

An important corollary to Lemma 6 is the

**Corollary 1**If is a finite group and a nonempty subset of closed under multiplication, is a subgroup of

** — 6. Lagrange’s Theorem — **

We are about to derive the first real group-theoretic result of importance. This theorem is the ABC’s for finite groups and has interesting implications in number theory. First, however, let us cover some basics in set theory.

Just as the concept of "function" runs throughout most phases of mathematics, so also does the concept of "relation". A **relation** is a statement about the elements If is the set of integers, is a relation on Similarly, is a relation of as is

**Definition 8**A relation on a set is a called an

**equivalence**

**relation**if it satisfies:

1. (reflexivity)

2. implies that (symmetry)

3. implies that (transitivity)

Of course, equality, is an equivalence relation, so the general notion of equivalence relation is a generalization of that equality.

These are the three properties of the congruence relations that mimics the properties of the equality among integers. They tell us that the congruence relations have the essential features of the equality relation and are an equivalence relation. Let us translate Definition 4 of congruence relations in terms of groups and subgroups.

**Definition 9**Let be a group, a subgroup of for we say is

**congruent**to mod if

**Lemma 7**The relation is an equivalence relation.

**Proof:**We must verify the following three properties: For all

1.

2. implies .

3. implies

Let’s go through each one.

1. To show that we must prove, using Definition 9 of congruence mod that Since is a subgroup of and since which is what we were required to demonstrate.

2. Suppose that that is we want to get from this or, equivalently, Since which is a subgroup of but by Lemma 3, and so and

3. Finally we require that and forces The first congruence translates into the second into using that is a subgroup of However, hence from which it follows that

Note that if the group of integers under addition and the subgroup consisting of multiples of for then in the relation that is, , translates into . So congruence mod is a very special case of the equivalence relation if , or

**Definition 10**If is a subgroup of then is called a

**right coset**of in

**Lemma 8**For all

**Proof:**Let We first show that For, if then since is a subgroup of By the definition of congruence mod this implies that for every and so

Suppose, now, that Thus so is also in That is, for some Multiplying both sides by from the right we come up with and so Thus Having proved the two inclusions we have

**Definition 11**If is an equivalence relation on then the

**equivalence class**of is defined by

Note that in Lemma 8 and thus , is the equivalence class of in

The important influence that an equivalence relation has on a set is to break it up and *partition* it into disjoint pieces (i.e., equivalences classes).

**Theorem 1**If is an equivalence relation on then where this union runs over one element from each equivalence class, and where implies that That is partitions into equivalence classes.

**Proof:**Since we have The proof of the second assertion is also quite easy. We show that if then or, what is equivalent to this, if then

Suppose, then, that let By definition of class, since and since Therefore, by property 2 of , and so, since and we have, Thus if then gives us hence Thus The argument is obviously symmetric in and so we have whence

We can now prove a famous result of Lagrange.

**Theorem 2**(Lagrange’s Theorem). If is a finite group and is a subgroup of then the order of divides the order of

**Proof:**Recall Definition 10 and Lemma 8 where we established that the relation if is an equivalence relation and that

Let be the number of distinct equivalence classes, By Theorem 1, and we know that if

We assert that any has order of elements. Map by sending We claim that this map is , for if then by cancellation in we would have thus the map is It is definitely onto by the very definition of So and have the same the number, of elements.

Since and the are disjoint and each has elements, we have that Thus, divides .

Lagrange’s theorem has some very important corollaries. First we present the following definition.

**Definition 12**If is finite, then the

**order**of written is the

*least positive integer m*such that

**Theorem 3**If is finite and then

**Proof:**With Lagrange’s theorem, it seems natural to prove this by exhibiting a subgroup of whose order is The element itself furnishes us with this subgroup by considering the cyclic subgroup, of generated by consists of How many elements are there in We assert that this number is the order of Clearly, since this subgroup has at most elements. If it should actually have fewer than this number of elements, then for some integers Then yet which would contradict the very meaning of Thus the cyclic subgroup generated by has elements. So, by Lagrange’s theorem,

**Theorem 4**If is a finite group of order then for all

**Proof:**By Theorem 3, thus Therefore,

**Definition 13**The Euler totient or -function, , is defined by and, for the number if positive integers with such that .

**Example 20**since only are the numbers less than which are relatively prime to

With the Euler function defined, let us consider the set consists of the elements of which are relatively prime to and is called the *group of units in the integers mod n* or *group of invertible elements of *. Note that is a group, but is not a group since the element does not have a multiplicative inverse. However, if we consider the units, elements which have multiplicative inverses, we do get a group under multiplication mod , . Let us prove this fact.

**Notation 2**In Definition 13 and Example 20 we referred to the greatest common divisor (GCD), denoted as , which is also denoted as .

**Proposition 4**Let be the set of units in, Then is a group under multiplication mod .

**Proof:**To show that multiplication mod is a binary operation on , we must show that the product of units is a unit.

Suppose Then has a multiplicative inverse and has a multiplicative inverse . Now

Hence, is the multiplicative inverse of , and is a unit. Therefore, multiplication mod is a binary operation on .

We can take it for granted that multiplication mod is associative for following the associativity of the integers.

The identity element for multiplication mod is , and with multiplicative inverse .

Finally, every element of has a multiplicative inverse, by definition.

Therefore, is a group under multiplication mod .

**Remark 8**Note multiplication is commutative in Thus, forms an abelian group.

**Remark 9**Note the by definition number of integers such that Thus, the order of , where is the Euler function. Also, if a prime, then

An immediate consequence to Theorem 4, Proposition 4, and Remarks 8 and 9 is the following famous result in number theory.

**Theorem 5**(Euler) If is an integer relatively prime to , then .

**Proof:**forms a group of order so by Theorem 4, for all This translates into which in turn translates into Precisely, this says that

A special case of Theorem 5, where is a prime, is due to Fermat and known as Fermat’s Little Theorem.

**Corollary 2**(Fermat’s Little Theorem) If is a prime and , then

For any integer .

**Proof:**Since if we have, by Theorem 6, that hence so that If on the other hand, is not relatively prime to since is a prime number, we must have that so that hence here also.

Recall that a group is said to be *cyclic* if there is an element such that every element in is a power of

**Theorem 6**A group of prime order is cyclic.

**Proof:**If is a subgroup of then by invoking Lagrange’s Theorem, a prime, so or So if then If then the powers of form a subgroup of different from So this subgroup is all of This says that any is of the form hence is cyclic by the definition of cyclic group.

** — 7. Ring Theory — **

We now cover some ring theory.

**Definition 14**A commutative ring is an

**integral domain**if in implies that or

**Example 21**The set of integers is an integral domain.

**Definition 15**A ring with unit, is said to be a

**division ring**if for every in there is an element (usually written ) such that

The reason for call such a ring a division ring is we can divide keeping in mind noncommutative division rings exist.

**Definition 16**A ring is said to be a

**field**if is a commutative division ring.

In other words, a field is a commutative ring in which we can divide freely by nonzero elements. As stated before, the set of all rational numbers and the set of all rationals are fields. Also the set of all complex numbers is a field. Note that is described by saying that is a **subfield** of (and of ) and is a subfield of

Let’s consider some examples around

**Example 22**Let , the ring of integers mod , with addition and multiplication defined by and . Note that is the required by the ring axioms and is the unit element of . Note, however, that is not an integral domain, for , yet and . is a commutative ring with unit.

This example suggests the following.

**Definition 17**An element in a ring is a

**zero-divisor**in if for some in

Note that both and in are zero-divisors.

**Example 23**Let the ring of integers mod 5. is a commutative ring with unit. But it is more; in fact, it is a field. It’s nonzero elements are and and we note that and and are their own inverses. So every, nonzero element in has an inverse in

We now generalize Example 23 for any prime .

**Example 24**Let be the integers mod where is a prime. Again is a commutative ring with unit. We claim that is a field. To see this, note that if then Therefore, by Fermat’s Theorem (Corollary 6), For classes this says that But so therefore, is the required inverse for in hence is a field. Because has only a finite number of elements, it is called a

**finite field**.

**Remark 10**Finite fields are also sometimes called

*Galois fields*, after Évariste Galois, who studied them in the century.

**Notation 3**The integers mod is often denoted by . Other notations are and Yet another notation is in honor of Galois. And, of course, there is the notation that we use, since it is being used in

*Proofs from THE BOOK*, although in number theory the notation is more commonly reserved for the ring of -adic integers.

** — 8. Finite Fields — **

Using ring theory we were able to introduce fields and, in Example 24, introduce finite fields. In this section we will we shall show that the multiplicative group of nonzero elements of a finite field is a cyclic group.

**Theorem 7**If then where this sum runs over all divisors of

**Proof:**Let be a cyclic group of order generated by the element If how many elements of have order If then all the solutions in of are the powers of How many of these have order We claim that has order if and only if is relatively prime to So the number of elements of order in for every divisor of is Every element in has order some divisor of so if we sum up the number of elements of order , namely over all dividing we account for each element of once and only once. Hence if we run over all the divisors of

**Example 25**Let then for and are less than and relatively prime to We compute for all the divisors of We have: and Note the sum of all over all the divisors of is .

**Theorem 8**Let be a finite group of order with the property that for every that divides there are at most solutions of in Then is a cyclic group.

**Proof:**Let be the number of elements of of order By hypothesis, if is order then all the solutions of are the distinct powers of which number, are of order So if there is an element of order in then On the other hand, of there is no element in of order then So for all we have that However, since every element of has some order that divides we have that we have that where this sum runs over all divisors of But

since each This gives us that which, together with forces for every that divides Thus, in particular, This tells us that after all, is the number of elements in of order and since there must be an element in of order Therefore, the elements are distinct and are in number, so they must give all of Thus is cyclic with as generator.

**Theorem 9**If is a field and is the group of nonzero elements of under multiplication, then any finite subgroup of is cyclic.

**Proof:**If is the group of nonzero elements of a field under multiplication, then the polynomial has at most roots in . So, if is a finite multiplicative subgroup of then the number of solutions of in is at most for any positive integer so certainly for all that divide the order of By Theorem 8, must be a cyclic group.

A very special case of Theorem 9 is

**Theorem 10**If is a finite field, then is a cyclic.

**Proof:**is a finite subgroup of itself, so, by Theorem 9, is a cyclic group.

A particular instance of Theorem 10 is of great importance in number theory, where it is known as the *existence of primitive roots mod * for a prime.

**Theorem 11**If is a prime, then is a cyclic group.

** — 9. Infinitude of Primes Theorem — **

We are now ready to prove Euclid’s Second Theorem, also called the Infinitude of Primes Theorem using the second proof in *Proofs from THE BOOK.*

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

**Proof:**Suppose is finite and is the largest prime. We consider the so-called

*Mersenne number*and show that any prime factor of is bigger than , which will yield the desired conclusion. Let be a prime dividing , so we have Since is prime, this means that the element has order in the multiplicative group of the field . This group has elements. By Lagrange’s theorem we know that the order of every element divides the size of the group, that is, we have , and hence

## Leave a comment

Comments feed for this article