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 ${G}$ be a nonempty set and ${*:G\times G\rightarrow G}$ be a binary operation on ${G.}$ Then the set ${G}$ together with the binary operation ${*}$, denoted${(G,*)}$, is a group, if the following three conditions are satisfied:

i. The binary operation ${*}$ is associative, i.e., ${(a*b)*c=a*(b*c)}$ for all ${a,b,c\in G}$.

ii. There is a ${*}$-identity ${e\in G}$, i.e., ${e*x=x*e=x}$ for all ${x\in G}$.

iii. For each ${a\in G}$, there is a ${*}$-inverse ${a'\in G}$, i.e., ${a*a'=a'*a=e}$, where ${e}$ is the ${*}$-identity.

Further more, a group ${(G,*)}$ 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 ${(\mathbb{Z},+)}$ is a commutative group. Note that ${+}$ is associative and commutative, while ${0}$ is the ${+}$-identity. Also, for ${a\in\mathbb{Z}}$ the ${+}$-inverse is ${{-}a.}$

Example 2 Note that the set of all integers together with the ordinary subtraction ${(\mathbb{Z},{-})}$ is not a group. The binary operation ${{-}}$ is not associative.

Example 3 Note that the set of all integers together with the ordinary multiplication ${(\mathbb{Z},\cdot)}$ is not a group. There are no ${\cdot}$-inverses.

Example 4 Note that the set of all natural numbers together with the ordinary subtraction ${(\mathbb{N},+)}$ is not a group. ${+}$ is associative and commutative, but ${\mathbb{N}}$ does not contain ${+}$-identity.

Example 5 Note that the set of all real numbers together with the ordinary multiplication ${(\mathbb{R},\cdot)}$ is not a group. The multiplication ${\cdot}$ is associative and commutative on ${\mathbb{R}}$, while ${1}$ is the multiplicative idenity. However, ${0}$ has no ${\cdot}$-inverse.

Example 6 Note that the set of all positive real numbers (denoted ${\mathbb{R}^{+}}$) together with the ordinary multiplication ${(\mathbb{R}^{+},\cdot)}$ is a commutative group. The multiplication ${\cdot}$ is associative and commutative on ${\mathbb{R}^{+}}$, while ${1}$ is the multiplicative identity. Note that every element in ${\mathbb{R}^{+}}$ 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 ${R}$ be a nonempty set, and ${+}$ and ${\cdot}$ be two binary operations on ${R.}$ The triple ${(R,+,\cdot)}$ is called a ring, if it satisfies the following three conditions:

i. ${(R,+)}$ is a commutative group.

ii. ${\cdot}$ is associative.

iii. ${a\cdot(b+c)=a\cdot b+a\cdot c}$ and ${(a+b)\cdot c=a\cdot c+b\cdot c}$ for all ${a,b,c\in R.}$

Furthermore, if the operation ${\cdot}$ is commutative, then the ring ${(R,+,\cdot)}$ is called a commutative ring.

Remark 1 If ${(R,+,\cdot)}$ 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 ${(\mathbb{Z},+,\cdot)}$ 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 ${(\mathbb{N},+,\cdot)}$ is not a ring, since ${(\mathbb{N},+)}$ is not a commutative group.

Example 9 Note that the set of all positive real numbers (denoted ${\mathbb{R}^{+}}$) together with the ordinary addition and multiplication ${(\mathbb{R}^{+},+,\cdot)}$ is not a ring, since ${(\mathbb{R}^{+},+)}$ is not a group (it has not ${+}$-identity in ${\mathbb{R}^{+}}$).

Example 10 Note that the set of all rational numbers together with the ordinary addition and ordinary multiplication ${(\mathbb{Q},+,\cdot)}$ 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 ${R}$ be a nonempty set, and ${+}$ and ${\cdot}$ be two binary operations on ${R.}$ The commutative ring ${(R,+,\cdot)}$ is called a field, if it satisfies the following two conditions:

i. ${\cdot}$ has the identity element ${1}$ in ${R.}$

ii. Every nonzero element of ${R}$ has the ${\cdot}$-inverse. [Note: In a ring, the zero element refers to the ${+}$-identity; so, nonzero elements mean non-${+}$-identity elements of ${R.}$]

— 2. The Axioms of Field —

Let us summarize, what we have assumed about the ordinary addition ${+}$ and ordinary multiplication ${\cdot}$ on ${\mathbb{R}.}$ We have and will assume the following Axioms satisfied by ${(R,+,\cdot).}$ The set of all real numbers ${\mathbb{R}}$ together with the ordinary addition ${+}$ and multiplication ${\cdot}$ satisfies the following axioms.

Axiom 1 (Commutativity of ${+}$). ${x+y=y+x}$ for all ${x,y\in\mathbb{R}.}$

Axiom 2 (Associativity of ${+}$). ${(x+y)+z=x+(y+z)}$ for all ${x,y,z\in\mathbb{R}.}$

Axiom 3 (${+}$-Identity). There is an element ${0}$ in ${\mathbb{R}}$ such that ${x+0=x}$ for all ${x\in\mathbb{R}.}$

Axiom 4 (${+}$-Inverse). For any ${x\in\mathbb{R}}$, there is an element ${x'\in\mathbb{R}}$ such that ${x+x'=0}$. [Note: We usually write ${{-}x}$ for ${x'}$.]

Axiom 5 (Commutativity of ${\cdot}$). ${xy=yx}$ for all elements ${x,y\in\mathbb{R}.}$

Axiom 6 (Associativity of ${\cdot}$). ${(xy)z=x(yz)}$ for all ${x,y,z\in\mathbb{R}.}$

Axiom 7 (${\cdot}$-Identity). There is an element ${1\in\mathbb{R}}$ (not equal to ${0}$ in Axiom 3) such that ${1\cdot x=x}$ for all ${x\in\mathbb{R}.}$

Axiom 8 (${\cdot}$-Inverse). For any ${x\in\mathbb{R}}$ such that ${x\neq0}$, there is an element ${x''\in R}$ such that ${x\cdot x''=1}$. [Note: We usually write ${x^{{-}1}}$ for ${x''}$.]

Axiom 9 (Distributivity). ${(x+y)z=xz+yz}$ for all ${x,y,z\in\mathbb{R}.}$

Note that the Axioms of Field satisfied by the set of all real numbers ${\mathbb{R}}$ indeed makes ${(\mathbb{R},+,\cdot)}$ a field. There are more axioms the field of real numbers satisfies, but we will not use them. Note, the set of natural numbers ${\mathbb{N}}$, set of integers ${\mathbb{Z}}$, and the set of all rational numbers ${\mathbb{Q}}$ are subsets of the set of all real numbers ${\mathbb{R}.}$ Specifically, ${\mathbb{N}\subset\mathbb{Z}\subset\mathbb{Q}\subset\mathbb{R}.}$

Example 11 Note that the set of all rational numbers ${\mathbb{Q}}$ indeed makes ${(\mathbb{Q},+,\cdot)}$ a field.

Example 12 Note that the set of all integers together with the ordinary addition and multiplication ${(\mathbb{Z},+,\cdot)}$ 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 ${(\mathbb{N},+,\cdot)}$ is not a field, since ${(\mathbb{N},+,\cdot)}$ 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 ${\mathbb{Z}.}$

Definition 4 Let ${n\in\mathbb{N}.}$ Let ${x,y\in\mathbb{Z}.}$ We say that an integer ${x}$ is congruent to an integer ${y}$ modulo ${n}$, denoted ${x\equiv_{n}y}$ (or, "${x\equiv y\; mod\; n}$"), if ${n|(x{-}y).}$

Remark 3 According to the definition above, showing ${x\equiv_{n}y}$ means showing ${n|(x{-}y)}$ (or, equivalently, showing ${n|(y{-}x)}$).

Notation 1 Let ${n\in\mathbb{N}.}$ When an integer ${x}$ is not congruent to an integer ${y}$ modulo n (i.e., ${n\nmid(x{-}y)}$), we denote this fact by ${x\not\equiv_{n}y}$ (or ${x\nmid y\; mod\; n}$).

The next lemma along with the Division Algorithm tells us that an integer ${a}$ is congruent modulo ${n}$ to the remainder of ${a}$ divided by ${n.}$

Lemma 1 Let ${a\in\mathbb{Z}}$ and ${n\in\mathbb{N}.}$ If ${r\in\mathbb{Z}}$ such that ${a=qn+r}$ for some ${q\in\mathbb{Z}}$, then ${a\equiv_{n}r.}$

Proof: Let ${a\in\mathbb{Z}}$ and ${n\in\mathbb{N}.}$ Assume that ${r\in\mathbb{Z}}$ such that ${a=qn+r}$ for some ${q\in\mathbb{Z}.}$ Note that ${a{-}r=qn.}$ So, ${n|(a{-}r).}$ Thus, ${a\equiv_{n}r.}$ $\Box$

Using the Division Algorithm, we can establish that if ${n\in\mathbb{N}}$, then every integer is congruent (modulo ${n}$) to a unique integer between ${0}$ and ${n{-}1.}$

Proposition 1 Let ${n\in\mathbb{N}.}$ If ${a\in\mathbb{Z},}$ then there is a unique integer ${r\in\mathbb{Z}}$ such that ${0\leq r and ${a\equiv_{n}r.}$

Proof: Let ${n\in\mathbb{N}}$ and ${a\in\mathbb{Z}.}$ Then, by the Division Algorithm, there is a unique pair of integers ${q,r\in\mathbb{Z}}$ such that ${a=qn+r}$ with ${0\leq r So, according to the above lemma, ${a\equiv_{n}r.}$ Suppose there is an integer ${s}$ such that ${0\leq s and ${a\equiv_{n}s.}$ Since ${a\equiv_{n}s,}$ there is ${t\in\mathbb{Z}}$ such that ${a{-}s=nt.}$ So, ${a=nt+s}$ with ${0\leq s However, the pair ${q}$ and ${r}$ is the unique such pair according to the Division Algorithm. So, ${t}$ must equal ${q}$ and ${s}$ must equal ${r.}$ Thus, the integer ${r}$ in the statement of the proposition is unique. $\Box$

— 4. The Congruence Classes Modulo ${n}$: ${\mathbb{Z}_{n}}$

In this section, we introduce the congruence classes modulo ${n}$ of integers, where ${n\in\mathbb{N}.}$ A congruence class (modulo ${n}$) of ${a\in\mathbb{Z}}$ is the collection of all integers congruent to ${a}$ modulo ${n.}$ We then consider the set of all congruence classes, denoted by ${\mathbb{Z}_{n},}$ and define two associative binary operations on ${\mathbb{Z}_{n}.}$

Definition 5 Let ${n\in\mathbb{N}}$ and ${a\in\mathbb{Z}.}$

$\displaystyle [a]_{n}:=\{b\in\mathbb{Z}:b\equiv_{n}a\}=\{b\in\mathbb{Z}:n|(b{-}a)\}.$

We refer to the set ${[a]_{n}}$ as the congruence class of ${a}$ modulo ${n.}$ Also, ${\mathbb{Z}_{n}}$ denote the set of all congruence classes modulo ${n}$, i.e., ${\mathbb{Z}_{n}=\{[a]_{n}:a\in\mathbb{Z}\}.}$

Example 14 Let us find the congruence class of ${0}$ modulo ${5}$ (i.e., ${n=5}$ in the above definition). According to the definition, the congruence class ${[0]_{5}}$ is a set consisting of all those integers congruent to ${0}$ modulo ${5.}$ For example, ${5}$ and ${{-}15}$ belong to ${[0]_{5}}$ (note: ${[0]_{5}}$ is a set), since ${5\equiv_{5}0}$ and ${{-}15\equiv_{5}0.}$ Note that ${a\in[0]_{5}}$(i.e., ${a\equiv_{5}0}$) means ${5|(a{-}0)}$, or ${5|a.}$

Conversely, if ${5|a}$, then ${5|(a{-}0)}$; so, ${a\equiv_{5}0}$ (i.e., ${a\in[0]_{5}}$). Hence, the congruence class ${[0]_{5}}$ is the set of all multiple of ${5}$, i.e.,

$\displaystyle [0]_{5}=\{0,{\pm}5,{\pm}10,{\pm}15,\cdots\}.$

Example 15 Let us find the congruence class of ${2}$ modulo ${7}$ (i.e., ${n=7}$ in the above definition). According to the definition, the congruence class ${[2]_{7}}$ consists of all those integers congruent to ${2}$ modulo ${7.}$ For example, ${9}$ and ${{-}12}$ belong to ${[2]_{7}}$ (note: ${[2]_{7}}$ is a set), since ${9\equiv_{7}2}$ and ${{-}12\equiv_{7}2.}$ Note that ${a\in[2]_{7}}$ (i.e., ${a\equiv_{7}2}$) means ${7|(a{-}2)}$, or ${a{-}2=7k}$ for some integer ${k.}$ Thus, ${a=2+7k}$ for some integer ${k.}$

Conversely, if ${a=2+7k}$ for some integer ${k}$, then ${7|(a{-}2)}$; so, ${a\equiv_{7}2}$ (so, ${a\in[2]_{7}}$). Thus, the congruence class ${[2]_{7}}$ can be represented as the following set

$\displaystyle \begin{array}{rcl} [2]_{7} = \{2,2\pm7,2\pm14,2\pm21,\cdots\}=\{2+7k:k\in\mathbb{Z}\}.\end{array}$

The next lemma characterizes the congruence classes.

Lemma 2 Let ${n\in\mathbb{N}.}$ If ${a\in\mathbb{Z},}$ then

$\displaystyle \begin{array}{rcl} [a]_{n} = \{a+n\cdot k:k\in\mathbb{Z}\}.\end{array}$

Proof: Let ${n\in N}$, and ${a\in\mathbb{Z}.}$

Let ${x\in[k]_{n}}$. Then ${x\equiv_{n}a}$. So, ${n|(x{-}a)}$. Thus, there is ${k\in\mathbb{Z}}$ such that ${x{-}a=nk}$. So, ${x=a+nk}$. Thus, ${x\in\{a+nk:k\in\mathbb{Z}\}}$. Consequently, ${[a]_{n}\subset\{a+nk:k\in\mathbb{Z}\}.}$

Let ${x\in\{a+nk:k\in\mathbb{Z}\}}$. Then there is ${k\in\mathbb{Z}}$ such that ${x=a+nk}$. So, ${x{-}a=nk}$. Thus, ${n|(x{-}a)}$. So, ${x\equiv_{n}a}$. Thus, ${x\in[a]_{n}}$. Consequently, ${\{a+nk:k\in\mathbb{Z}\subset[a]_{n}\}}$. Thus, ${[a]_{n}=\{a+nk:k\in\mathbb{Z}\}.}$$\Box$

Example 16 Note that

$\displaystyle \begin{array}{rcl} [0]_{7} = \{0,\pm7,\pm14,\pm21,\cdot\cdot\cdot\}\end{array}$

and

$\displaystyle \begin{array}{rcl} [4]_{5} = \{4,4\pm5,4\pm10,4\pm15\cdot\cdot\cdot\}.\end{array}$

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

Proposition 2 Let ${n\in\mathbb{N}}$, and ${a,b\in\mathbb{Z}}$. ${[a]_{n}=[b]_{n}}$ iff ${a\equiv_{n}b.}$

Proof: Let ${n\in\mathbb{N}}$, and ${a,b\in\mathbb{Z}}$.

(Implication). Assume that ${[a]_{n}=[b]_{n}}$. Then ${a\in[b]n}$. So, ${a\equiv_{n}b}$.

(Converse). Assume that ${a\equiv_{n}b}$. So, ${b\equiv_{n}a}$ as well. Let ${x\in[a]_{n}}$. Then ${x\equiv_{n}a}$ and ${a\equiv_{n}b}$. So, ${x\equiv_{n}b}$. Thus, ${x\in[b]_{n}}$. Consequently, ${[a]_{n}\subset[b]_{n}}$. Let ${y\in[b]_{n}}$. Then ${y\equiv_{n}b}$ and ${b\equiv_{n}a}$. So, ${y\equiv_{n}a}$. Thus, ${y\in[a]_{n}}$. Consequently, ${[b]_{n}\subset[a]_{n}}$. Hence, ${[a]_{n}=[b]_{n}}$.$\Box$

Remark 4 Replacing "${a\equiv_{n}b}$" by the definition "${n|(a{-}b)}$" in the above proposition, we obtain the restatement "${[a]_{n}=[b]_{n}}$ iff ${n|(a{-}b)}$". Using this restatement, we obtain ${[13]_{5}=[108]_{5}}$, since ${5|(13{-}108)}$. Similarly, using the restatement, we see that ${[12]_{7}\neq[{-}12]_{7}}$, since ${7\nmid(12{-}({-}12))}$.

Example 17 According to the previous proposition, we have ${[12]_{7}=[{-}2]_{7}}$, since ${12\equiv_{7}{-}2}$ (i.e., ${7|({-}2{-}12)}$). Also, ${[7]_{3}=[1]_{3}}$, since ${7\equiv_{3}1}$ (i.e., ${3|1{-}7}$).

As a consequence of the above proposition, we can show that, for a fixed ${n\in\mathbb{N}}$, the set of all congruence classes ${\mathbb{Z}_{n}}$ consists of only ${n}$ distinct congruence classes, namely ${[0]_{n},[1]_{n},\cdots,[n{-}1]_{n}}$.

Proposition 3 If ${n\in\mathbb{N}}$, then

$\displaystyle \begin{array}{rcl} \mathbb{Z}_{n} = \{[0]_{n},[1]_{n},\cdots,[n{-}1]_{n}\}.\end{array}$

Proof: Let ${n\in\mathbb{N}}$. Let ${S=\{[0]_{n},[1]_{n},\cdots,[n{-}1]_{n}\}}$. It is clear that ${S\subset\mathbb{Z}_{n}}$. So, let us show that ${\mathbb{Z}_{n}\subset S}$. Let ${[a]_{n}\in\mathbb{Z}_{n}}$. Then, by the Division Algorithm, there is a unique pair of integers ${q,r\in\mathbb{Z}}$ such that ${a=nq+r}$ with ${0\leq r. Since ${a\equiv_{n}r}$, we have ${[a]_{n}=[r]_{n}}$. Also, ${[r]_{n}\in\{[0]_{n},[1]_{n},\cdots,[n{-}1]_{n}\}=S}$. Thus, ${[a]_{n}\in S}$. Hence, ${\mathbb{Z}_{n}\subset S}$.$\Box$

Remark 5 We can consider ${\mathbb{Z}_{n}}$ as the set of all possible remainders of an integer divided by ${n}$. So, ${\mathbb{Z}_{n}}$ is sometime referred to as the collection of residue classes modulo ${n}$, and refers to the set ${[a]_{n}}$ as the residue class of ${a}$ modulo ${n}$.

Remark 6 We can restate the proposition above as: If ${n\in\mathbb{N}}$ and ${[a]_{n}\in\mathbb{Z}_{n},}$ then there is ${r\in\mathbb{Z}}$ such that ${0\leq r and ${[a]_{n}=[r]_{n}}$. This fact comes from the Division Algorithm. For example, ${[19]_{4}=[3]_{4}}$ and ${[{-}11]_{6}=[1]_{6}}$, since ${19\div4=4\cdots3}$ and ${{-}11\div6={-}2\cdots1}$.

Example 18 ${\mathbb{Z}_{1}=\{[0]_{1}\}}$, ${\mathbb{Z}_{2}=\{[0]_{2},[1]_{2}\}}$ and ${\mathbb{Z}_{6}=\{[0]_{6},[1]_{6},\cdots,[5]_{6}\}.}$

Note that ${\mathbb{Z}_{n}}$ for each ${n\in\mathbb{N}}$, is very closely related to the set of integers ${\mathbb{Z}}$, but they have quite different characters. In particular, ${\mathbb{Z}_{n}}$ contains only ${n}$ elements. So, ${\mathbb{Z}_{n}}$ 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 ${G}$ is a group, then

a. The identity element of ${G}$ is unique.

b. Every ${a\in G}$ has a unique inverse in ${G.}$

c. For every ${a\in G,(a^{-1})^{-1}=a.}$

d. For all ${a,b\in G,(a\cdot b)^{-1}=b^{-1}\cdot a^{-1}.}$

Proof: We start with Part a. We must show that if ${e,f\in G}$ and ${af=fa=a}$ for all ${a\in G}$ and ${ae=ea=a}$ for all ${a\in G,}$ then ${e=f.}$ This is easy, for then ${e=ef}$ and ${f=ef;}$ hence ${e=ef=f.}$

For Part b we will prove a stronger result., which will have Part b as an immediate consequence. We claim that in a group ${G}$ if ${ab=ac,}$ then ${b=c;}$ that is, we can cancel a given element from the same side of an equation. To see this, we have, for ${a\in G,}$ an element ${u\in G}$ such that ${ua=e.}$ Thus from ${ab=ac}$ we have

$\displaystyle u(ab)=u(ac),$

so, by the associative law, ${(ua)b=(ua)c,}$ that is, ${eb=ec.}$ Hence ${b=eb=ec=c.}$ $\Box$

Now to get Part b as an implication of the cancellation result. Suppose that ${b,c\in G}$ act as inverses for ${a;}$ then ${ab=e=ac,}$ so by cancellation ${b=c}$ and we see that the inverse of ${a}$ is unique. We shall always write it as ${a^{-1}.}$

To see Part c, note that by definition ${a^{-1}(a^{-1})^{-1}=e;}$ but ${a^{-1}a=e,}$ so by cancellation in ${a^{-1}(a^{-1})^{-1}=e=a^{-1}a}$ we get ${(a^{-1})^{-1}=a.}$

Finally, for Part d we calculate

$\displaystyle \begin{array}{rcl} (ab)(b^{-1}a^{-1}) & = & ((ab)b^{-1})a^{-1}\\ & = & (a(bb^{-1})a^{-1}\\ & = & (ae)a^{-1}\\ & = & aa^{-1} = e \end{array}$

Similary, ${(b^{-1}a^{-1})(ab)=e.}$ Hence, by definition, ${(ab)^{-1}=b^{-1}a^{-1}.}$

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

Lemma 4 In any group ${G,}$ if ${a,b,c\in G}$ and

a. ${ab=ac,}$ then ${b=c.}$

b. ${ba=ca,}$ then ${b=c.}$

Definition 6 A nonempty subset ${H}$ of a group ${G}$ is said to be a subgroup of ${G}$ if, under the product in ${G}$, ${H}$ itself forms a group.

Lemma 5 A nonempty subset ${H}$ of a the group ${G}$ is a subgroup iff

1. ${a,b\in H}$ implies that ${ab\in H.}$
2. ${a\in H}$ implies that ${a^{-1}\in H.}$

Proof: If ${H}$ is a subgroup of ${G,}$ then it is obvious that 1. and 2. must hold.

Suppose conversely that ${H}$ is subset of ${G}$ for which 1. and 2. hold. In order to establish that ${H}$ is a subgroup, all that is needed is to verify ${e\in H}$ and that the associative law does hold for ${G,}$ it holds all the more so for ${H,}$ which is a subset of ${G.}$ If ${a\in H,}$ by part 2 ${a^{-1}\in H}$ and so by part 1, ${e=aa^{-1}\in H}$. $\Box$

Example 19 Let ${G}$ be any group and let ${a\in G.}$ The set ${A=\{a^{i}|i\in\mathbb{Z}\}}$is a subgroup of ${G.}$ For, by the roles of exponents, if ${a^{i}\in A}$ and ${a^{j}\in A,}$ then ${a^{i}a^{j}=a^{i+j},}$ so is in ${A.}$ Also, ${(a^{i})^{-1}=a^{-i},}$ so ${(a^{i})^{-1}\in A.}$ This makes ${A}$ into a subgroup of ${G.}$

${A}$ is the cyclic subgroup of ${G}$ generated by ${a}$ in the following sense.

Definition 7 The cyclic subgroup of ${G}$ generated by ${a}$ is the set ${\{a^{i}|i\in\mathbb{Z}\}.}$ It is denoted ${(a).}$

Remark 7 If ${e}$ is the identity element of ${G,}$ then ${(e)=\{e\}.}$

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

Lemma 6 If ${H}$ is a nonempty finite subset of a group ${G}$ and ${H}$ is closed under multiplication, then ${H}$ is a subgroup of ${G.}$

Proof: In light of the Lemma 5, we need but show that whenever ${a^{-1}\in H.}$ Suppose that ${a\in H;}$ thus ${a^{2}=aa\in H,}$ ${a^{3}=a^{2}a\in H,\cdots,a^{m}\in H,\cdots}$ since ${H}$ is closed. Thus the infinite collection of elements ${a,a^{2},\cdots,a^{m},\cdots}$ must fit into ${H,}$ which is finite subset of ${G.}$ Thus there must be repetitions in this collection of elements; that is, for some integers ${r,s}$ with ${r>s>0,a^{r}=a^{s}.}$ By the cancellation in ${G,a^{r-s}=e}$ (${e\in H)}$; since ${r-s-1\geq0,a^{r-s-1}\in H}$ and ${a^{-1}=a^{r-s-1}}$since ${aa^{r-s-1}=a^{r-s}=e.}$ Thus ${a^{-1}\in H.}$ $\Box$

An important corollary to Lemma 6 is the

Corollary 1 If ${G}$ is a finite group and ${H}$ a nonempty subset of ${G}$ closed under multiplication, ${H}$ is a subgroup of ${G.}$

— 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 ${aRb}$ about the elements ${a,b\in S.}$ If ${S}$ is the set of integers, ${a=b}$ is a relation on ${S.}$ Similarly, ${a is a relation of ${S,}$ as is ${a\leq b.}$

Definition 8 A relation ${\sim}$ on a set ${S}$ is a called an equivalence relation if it satisfies:

1. ${a\sim a}$ (reflexivity)

2. ${a\sim b}$ implies that ${b\sim a}$ (symmetry)

3. ${a\sim b,b\sim c}$ implies that ${a\sim c}$ (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 ${G}$ be a group, ${H}$ a subgroup of ${G;}$ for ${a,b\in G}$ we say ${a}$ is congruent to ${b}$ mod ${H}$ if ${ab^{-1}\in H.}$

Lemma 7 The relation ${a\equiv_{H}b}$ is an equivalence relation.

Proof: We must verify the following three properties: For all ${a,b,c\in G,}$

1. ${a\equiv_{H}a.}$

2. ${a\equiv_{H}b}$ implies ${b\equiv_{H}a}$.

3. ${a\equiv_{H}b,}$ ${b\equiv_{H}c}$ implies ${a\equiv_{H}c.}$

Let’s go through each one.

1. To show that ${a\equiv_{H}a}$ we must prove, using Definition 9 of congruence mod ${H,}$ that ${aa^{-1}\in H.}$ Since ${H}$ is a subgroup of ${G,}$ ${e\in H,}$ and since ${aa^{-1}=e,aa^{-1}\in H,}$ which is what we were required to demonstrate.

2. Suppose that ${a\equiv_{H}b,}$ that is ${ab^{-1}\in H;}$ we want to get from this ${b\equiv_{H}a,}$ or, equivalently, ${ba^{-1}\in H.}$ Since ${ab^{-1}\in H,}$ which is a subgroup of ${G,}$ ${(ab^{-1})^{-1}\in H;}$ but by Lemma 3, ${(ab^{-1})^{-1}=(b^{-1})^{-1}a^{-1}=ba^{-1},}$ and so ${ba^{-1}\in H}$ and ${b\equiv_{H}a.}$

3. Finally we require that ${a\equiv_{H}b}$ and ${b\equiv_{H}c}$ forces ${a\equiv_{H}c.}$ The first congruence translates into ${ab^{-1}\in H,}$ the second into ${bc^{-1}\in H;}$ using that ${H}$ is a subgroup of ${G,}$ ${(ab^{-1})(bc^{-1})\in H.}$ However, ${ac^{-1}=aec^{-1}=a(b^{-1}b)c^{-1}=(ab^{-1})(bc^{-1});}$ hence ${ac^{-1}\in H,}$ from which it follows that ${a\equiv_{H}c.}$ $\Box$

Note that if ${G=\mathbb{Z},}$ the group of integers under addition ${+,}$ and ${H=H_{n}}$ the subgroup consisting of multiples of ${n,}$ for ${n>1,}$ then in ${G,}$ the relation ${a\equiv_{H}b,}$ that is, ${ab^{-1}\in H}$, translates into ${a\equiv_{n}b}$. So congruence mod ${n}$ is a very special case of the equivalence relation ${a\sim b}$ if ${ab^{-1}\in H}$, or ${a\equiv_{H}b.}$

Definition 10 If ${H}$ is a subgroup of ${G,}$ ${a\in G,}$ then ${Ha=\{ha|h\in h\}.}$ ${Ha}$ is called a right coset of ${H}$ in ${G.}$

Lemma 8 For all ${a\in G,}$

$\displaystyle Ha=\{x\in G|a\equiv_{H}x\}.$

Proof: Let ${[a]=\{x\in G|a\equiv_{h}x\}.}$ We first show that ${Ha\subset[a].}$ For, if ${h\in H,}$ then ${a(ha)^{-1}=a(a^{-1}h^{-1})=h^{-1}\in H}$ since ${H}$ is a subgroup of ${G.}$ By the definition of congruence mod ${H}$ this implies that ${ha\in[a]}$ for every ${h\in H,}$ and so ${Ha\subset[a].}$

Suppose, now, that ${x\in[a].}$ Thus ${ax^{-1}\in H,}$ so ${(ax^{-1})^{-1}=xa^{-1}}$ is also in ${H.}$ That is, ${xa^{-1}=h}$ for some ${h\in H.}$ Multiplying both sides by ${a}$ from the right we come up with ${x=ha,}$ and so ${x\in Ha.}$ Thus ${[a]\subset Ha.}$ Having proved the two inclusions we have ${[a]=Ha.}$$\Box$

Definition 11 If ${\sim}$ is an equivalence relation on ${S,}$ then ${[a],}$ the equivalence class of ${a,}$ is defined by ${[a]=\{b\in S|b\sim a\}.}$

Note that in Lemma 8 ${[a],}$ and thus ${Ha}$, is the equivalence class of ${a}$ in ${G.}$

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 ${\sim}$ is an equivalence relation on ${S,}$ then ${S=\bigcup[a],}$ where this union runs over one element from each equivalence class, and where ${[a]\neq[b]}$ implies that ${[a]\cap[b]=\emptyset.}$ That is ${\sim}$ partitions ${S}$ into equivalence classes.

Proof: Since ${a\in[a],}$ we have ${\cup_{a\in S}[a]=S.}$ The proof of the second assertion is also quite easy. We show that if ${[a]\neq[b],}$ then ${[a]\cap[b]=\emptyset,}$ or, what is equivalent to this, if ${[a]\cap[b]=\emptyset,}$ then ${[a]=[b].}$

Suppose, then, that ${[a]\cap[b]=\emptyset;}$ let ${c\in[a]\cap[b].}$ By definition of class, ${c\sim a}$ since ${c\in[a]}$ and ${c\sim b}$ since ${c\in[b].}$ Therefore, ${a\sim c}$ by property 2 of ${\sim}$, and so, since ${a\sim c}$ and ${c\sim b,}$ we have, ${a\sim b.}$ Thus ${a\in[b];}$ if ${x\in[a],}$ then ${x\sim a,a\sim b}$ gives us ${x\sim b,}$ hence ${x\in[b].}$ Thus ${[a]\subset[b].}$ The argument is obviously symmetric in ${a}$ and ${b,}$ so we have ${[b]\subset[a],}$ whence ${[a]=[b].}$ $\Box$

We can now prove a famous result of Lagrange.

Theorem 2 (Lagrange’s Theorem). If ${G}$ is a finite group and ${H}$ is a subgroup of ${G,}$ then the order of ${H}$ divides the order of ${G.}$

Proof: Recall Definition 10 and Lemma 8 where we established that the relation ${a\sim b}$ if ${ab^{-1}\in H}$ is an equivalence relation and that

$\displaystyle [a]=Ha=\{ha|h\in H\}.$

Let ${k}$ be the number of distinct equivalence classes, ${Ha_{1},\cdots,H_{k}.}$ By Theorem 1, ${G=Ha_{1}\cup Ha_{2}\cup\cdots\cup Ha_{k}}$ and we know that ${Ha_{i}\cap Ha_{j}=\emptyset}$ if ${i\neq j.}$

We assert that any ${Ha_{i}}$ has ${|H|=}$ order of ${H}$ elements. Map ${H\rightarrow Ha_{i}}$ by sending ${h\rightarrow ha_{i.}}$ We claim that this map is ${1-1}$, for if ${ha_{i}=h'a_{i},}$ then by cancellation in ${G}$ we would have ${h=h';}$ thus the map is ${1-1.}$ It is definitely onto by the very definition of ${Ha_{i}.}$ So ${H}$ and ${Ha_{i}}$ have the same the number, ${|H|,}$ of elements.

Since ${G=Ha_{1}\cup\cdots\cup Ha_{k}}$ and the ${Ha_{i}}$ are disjoint and each ${Ha_{i}}$ has ${|H|}$ elements, we have that ${|G|=k|H|.}$ Thus, ${|H|}$ divides ${|G|}$. $\Box$

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

Definition 12 If ${G}$ is finite, then the order of ${a,}$ written ${o(a),}$ is the least positive integer m such that ${a^{m}=e.}$

Theorem 3 If ${G}$ is finite and ${a\in G,}$ then ${o(a)\mid|G|.}$

Proof: With Lagrange’s theorem, it seems natural to prove this by exhibiting a subgroup of ${G}$ whose order is ${o(a).}$ The element ${a}$ itself furnishes us with this subgroup by considering the cyclic subgroup, ${(a),}$ of ${G}$ generated by ${a;}$ ${(a)}$ consists of ${e,a,a^{2},\cdots.}$ How many elements are there in ${(a)?}$ We assert that this number is the order of ${a.}$ Clearly, since ${a^{o(a)}=e,}$ this subgroup has at most ${o(a)}$ elements. If it should actually have fewer than this number of elements, then ${a^{i}=a^{j}}$ for some integers ${0\leq i Then ${a^{j-i}=e,}$ yet ${0 which would contradict the very meaning of ${o(a).}$ Thus the cyclic subgroup generated by ${a}$ has ${o(a)}$ elements. So, by Lagrange’s theorem, ${o(a)\mid|G|.}$$\Box$

Theorem 4 If ${G}$ is a finite group of order ${n=|G|,}$ then ${a^{n}=e}$ for all ${a\in G.}$

Proof: By Theorem 3, ${o(a)\mid|G|;}$ thus ${|G|=mo(a).}$ Therefore, ${a^{|G|}=a^{mo(a)}=(a^{o(a)})^{m}=e^{m}=e.}$$\Box$

Definition 13 The Euler totient or ${\phi}$-function, ${\phi(n)}$, is defined by ${\phi(1)=1}$ and, for ${n>1,\phi(n)=}$ the number if positive integers ${m}$ with ${1\leq m such that ${(m,n)=1}$.

Example 20 ${\phi(8)=4}$ since only ${1,3,5,7}$ are the numbers less than ${8}$ which are relatively prime to ${8.}$

With the Euler ${\phi-}$function defined, let us consider the set ${U_{n}=\{[a]\in\mathbb{Z}_{n}|(a,n)=1\}.}$ ${U_{n}}$ consists of the elements of ${\mathbb{Z}_{n}}$ which are relatively prime to ${n}$ and is called the group of units in the integers mod n or group of invertible elements of ${\mathbb{Z}_{n}}$. Note that ${(\mathbb{Z}_{n},+)}$ is a group, but ${(\mathbb{Z}_{n},\cdot)}$ is not a group since the element ${[0]}$ 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 ${n}$, ${U_{n}}$. Let us prove this fact.

Notation 2 In Definition 13 and Example 20 we referred to the greatest common divisor (GCD), denoted as ${(a,b)}$, which is also denoted as ${gcd(a,b)}$.

Proposition 4 Let ${U_{n}}$ be the set of units in, ${\mathbb{Z}_{n},n\geq1.}$ Then ${U_{n}}$ is a group under multiplication mod ${n}$.

Proof: To show that multiplication mod ${n}$ is a binary operation on ${U_{n}}$, we must show that the product of units is a unit.

Suppose ${[a],[b]\in U_{n}.}$ Then ${[a]}$ has a multiplicative inverse ${[a^{-1}]}$ and ${[b]}$ has a multiplicative inverse ${[b^{-1}]}$. Now

$\displaystyle [b^{-1}a^{-1}][ab]=[b^{-1}][a^{-1}a][b]=[b^{-1}][1][b]=[b^{-1}][b]=[b^{-1}b]=[1],$

$\displaystyle [ab][b^{-1}a^{-1}]=[a][b^{-1}b][a]=[a^{-1}][1][a]=[a^{-1}][a]=[a^{-1}a]=[1].$

Hence, ${[b^{-1}a^{-1}]}$ is the multiplicative inverse of ${[ab]}$, and ${[ab]}$ is a unit. Therefore, multiplication mod ${n}$ is a binary operation on ${U_{n}}$.

We can take it for granted that multiplication mod ${n}$ is associative for ${U_{n}}$ following the associativity of the integers.

The identity element for multiplication mod ${n}$ is ${[1]}$, and ${[1]\in\mathbb{Z}_{n}}$ with multiplicative inverse ${[1]}$.

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

Therefore, ${U_{n}}$ is a group under multiplication mod ${n}$.$\Box$

Remark 8 Note multiplication is commutative in ${U_{n}.}$ Thus, ${U_{n}}$ forms an abelian group.

Remark 9 Note the by definition ${U_{n},|U_{n}|=}$number of integers ${1\leq m such that ${(m,n)=1.}$ Thus, the order of ${U_{n}}$, ${|U_{n}|=\phi(n),}$ where ${\phi(n)}$ is the Euler ${\phi-}$function. Also, if ${n=p,}$ a prime, then ${\phi(p)=p-1.}$

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 ${a}$ is an integer relatively prime to ${n}$, then ${a^{\phi(n)}\equiv_{n}1}$.

Proof: ${U_{n}}$ forms a group of order ${\phi(n),}$ so by Theorem 4, ${g^{\phi(n)}=e}$ for all ${g\in U_{n}.}$ This translates into ${[a^{\phi(n)}]=[a]^{\phi(n)}=[1],}$ which in turn translates into ${n|(a^{\phi(n)}-1).}$ Precisely, this says that ${a^{\phi(n)}\equiv_{n}1.}$ $\Box$

A special case of Theorem 5, where ${n=p}$ is a prime, is due to Fermat and known as Fermat’s Little Theorem.

Corollary 2 (Fermat’s Little Theorem) If ${p}$ is a prime and ${p\nmid a}$, then

$\displaystyle a^{(p-1)}\equiv_{p}1.$

For any integer ${b,b^{p}\equiv_{p}b}$.

Proof: Since ${\phi(p)=p-1,}$if ${(a,p)=1,}$we have, by Theorem 6, that ${a^{p-1}\equiv_{p}1,}$ hence ${a^{1}\cdot a^{p-1}\equiv_{p}a^{1}\cdot1,}$ so that ${a^{p}\equiv_{p}a.}$ If on the other hand, ${b}$ is not relatively prime to ${p,}$ since ${p}$ is a prime number, we must have that ${p\mid b,}$ so that ${b\equiv_{p}0;}$ hence ${0\equiv_{p}b^{p}\equiv_{p}b}$ here also. $\Box$

Recall that a group ${G}$ is said to be cyclic if there is an element ${a\in G}$ such that every element in ${G}$ is a power of ${a.}$

Theorem 6 A group ${G}$ of prime order is cyclic.

Proof: If ${H}$ is a subgroup of ${G}$ then by invoking Lagrange’s Theorem, ${|H|\mid|G|=p,}$ ${p}$ a prime, so ${|H|=1}$ or ${p.}$ So if ${H\neq(e),}$ then ${H=G.}$ If ${a\neq e\in G,}$ then the powers of ${a,\{a^{i}\},}$ form a subgroup of ${G}$ different from ${(e).}$ So this subgroup is all of ${G.}$ This says that any ${x\in G}$ is of the form ${x=a^{i},}$ hence ${G}$ is cyclic by the definition of cyclic group. $\Box$

— 7. Ring Theory —

We now cover some ring theory.

Definition 14 A commutative ring ${R}$ is an integral domain if ${a\cdot b=0}$ in ${R}$ implies that ${a=0}$ or ${b=0.}$

Example 21 The set of integers ${(\mathbb{Z},+,\cdot)}$ is an integral domain.

Definition 15 A ring ${R}$ with unit, is said to be a division ring if for every ${a\neq0}$ in ${R}$ there is an element ${b\in R}$ (usually written ${a^{-1}}$) such that ${a\cdot a^{-1}=a^{-1}\cdot a=1.}$

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 ${R}$ is said to be a field if ${R}$ 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 ${\mathbb{Q}}$ and the set of all rationals ${\mathbb{R}}$ are fields. Also the set of all complex numbers ${\mathbb{C}}$ is a field. Note that ${\mathbb{Q}\subset\mathbb{R}\subset\mathbb{C}}$ is described by saying that ${\mathbb{Q}}$ is a subfield of ${\mathbb{R}}$ (and of ${\mathbb{C}}$) and ${\mathbb{R}}$ is a subfield of ${\mathbb{C}.}$

Let’s consider some examples around ${\mathbb{Z}_{n}.}$

Example 22 Let ${R=\mathbb{Z}_{6}}$, the ring of integers mod ${6}$, with addition and multiplication defined by ${[a]+[b]=[a+b]}$ and ${[a][b]=[ab]}$. Note that ${[0]}$ is the ${0}$ required by the ring axioms and ${[1]}$ is the unit element of ${R}$. Note, however, that ${\mathbb{Z}_{6}}$ is not an integral domain, for ${[2][3]=[6]=[0]}$, yet ${[2]\neq[0]}$ and ${[3]\neq[0]}$. ${R}$ is a commutative ring with unit.

This example suggests the following.

Definition 17 An element ${a\neq0}$ in a ring ${R}$ is a zero-divisor in ${R}$ if ${ab=0}$ for some ${b\neq0}$ in ${R.}$

Note that both ${[2]}$ and ${[3]}$ in ${\mathbb{Z}_{6}}$are zero-divisors.

Example 23 Let ${R=\mathbb{Z}_{5},}$ the ring of integers mod 5. ${R}$ is a commutative ring with unit. But it is more; in fact, it is a field. It’s nonzero elements are ${[1],[2],[3],}$ and ${[4]}$ and we note that ${[2][3]=[6]=[1],}$ and ${[1]}$ and ${[4]}$ are their own inverses. So every, nonzero element in ${\mathbb{Z}_{5}}$ has an inverse in ${\mathbb{Z}_{5}.}$

We now generalize Example 23 for any prime ${p}$.

Example 24 Let ${\mathbb{Z}_{p}}$ be the integers mod ${p,}$ where ${p}$ is a prime. Again ${\mathbb{Z}_{p}}$ is a commutative ring with unit. We claim that ${\mathbb{Z}_{p}}$ is a field. To see this, note that if ${a\neq0,}$ then ${p\nmid a.}$ Therefore, by Fermat’s Theorem (Corollary 6), ${a^{p-1}\equiv_{p}1.}$ For classes ${[\cdot]}$ this says that ${[a^{p-1}]=[1].}$ But ${[a]^{p-1},}$ so ${[a]^{p-1}=[1];}$ therefore, ${[a]^{p-2}}$ is the required inverse for ${[a]}$ in ${\mathbb{Z}_{p},}$ hence ${\mathbb{Z}_{p}}$ is a field. Because ${\mathbb{Z}_{p}}$ 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 ${19^{th}}$ century.

Notation 3 The integers mod ${p}$ is often denoted by ${\mathbb{F}_{p}}$. Other notations are ${\mathbb{Z}/p\mathbb{Z},}$ and ${\mathbb{Z}/p.}$ Yet another notation is ${GF(p),}$ in honor of Galois. And, of course, there is the notation that we use, ${\mathbb{Z}_{p},}$ since it is being used in Proofs from THE BOOK, although in number theory the notation ${\mathbb{Z}_{p}}$ is more commonly reserved for the ring of ${p}$-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 ${n\geq1,}$ then ${\sum\phi(d)=n,}$ where this sum runs over all divisors ${d}$ of ${n.}$

Proof: Let ${G}$ be a cyclic group of order ${n}$ generated by the element ${a.}$ If ${d|n,}$ how many elements of ${G}$ have order ${d?}$ If ${b=a^{n/d},}$ then all the solutions in ${G}$ of ${x^{d}=e}$ are the powers ${e,b,b^{2},\cdots,b^{d-1}}$ of ${b.}$ How many of these have order ${d?}$ We claim that ${b^{r}}$ has order ${d}$ if and only if ${r}$ is relatively prime to ${d.}$ So the number of elements of order ${d}$ in ${G,}$ for every divisor ${d}$ of ${n,}$ is ${\phi(d).}$ Every element in ${G}$ has order some divisor of ${n,}$ so if we sum up the number of elements of order ${d}$, namely ${\phi(d),}$ over all ${d}$ dividing ${n,}$ we account for each element of ${G}$ once and only once. Hence ${\sum\phi(d)=n}$ if we run over all the divisors ${d}$ of ${n.}$ $\Box$

Example 25 Let ${n=12;}$ then ${\phi(12)=4,}$ for ${1,5,7,}$ and ${11}$ are less than ${12}$ and relatively prime to ${12.}$ We compute ${\phi(d)}$ for all the divisors of ${12.}$ We have: ${\phi(1)=1,\phi(2)=1,\phi(3)=2,\phi(4)=2,\phi(6)=2,}$ and ${\phi(12)=4.}$ Note the sum of all ${\phi(d)}$ over all the divisors of ${12}$ is ${12}$.

Theorem 8 Let ${G}$ be a finite group of order ${n}$ with the property that for every ${d}$ that divides ${n}$ there are at most ${d}$ solutions of ${x^{d}=e}$ in ${G.}$ Then ${G}$ is a cyclic group.

Proof: Let ${\psi(d)}$ be the number of elements of ${G}$ of order ${d.}$ By hypothesis, if ${a\in G}$ is order ${d,}$ then all the solutions of ${x^{d}=e}$ are the distinct powers ${e,a,a^{2},\cdots,a^{d-1},}$ of which number, ${\phi(d)}$ are of order ${d.}$ So if there is an element of order ${d}$ in ${G,}$ then ${\psi(d)=\phi(d).}$ On the other hand, of there is no element in ${G}$ of order ${d,}$ then ${\psi(d)=0.}$ So for all ${d|n}$ we have that ${\psi(d)\leq\phi(d).}$ However, since every element of ${G}$ has some order ${d}$ that divides ${n}$ we have that we have that ${\sum\psi(d)=n,}$ where this sum runs over all divisors ${d}$ of ${n.}$ But

$\displaystyle n=\sum\psi(d)\leq\sum\phi(d)=n$

since each ${\psi(d)\leq\phi(d).}$ This gives us that ${\sum\psi(d)=\sum\phi(d),}$ which, together with ${\psi(d)\leq\phi(d),}$ forces ${\psi(d)=\phi(d)}$ for every ${d}$ that divides ${n.}$ Thus, in particular, ${\psi(n)=\phi(n)\geq1.}$ This tells us that after all, ${\psi(n)}$ is the number of elements in ${G}$ of order ${n,}$ and since ${\psi(n)\geq1}$ there must be an element ${a}$ in ${G}$ of order ${n.}$ Therefore, the elements ${e,a,a^{2},\cdots,a^{n-1}}$ are distinct and are ${n}$ in number, so they must give all of ${G.}$ Thus ${G}$ is cyclic with ${a}$ as generator.$\Box$

Theorem 9 If ${K}$ is a field and ${K\backslash\{0\}}$ is the group of nonzero elements of ${K}$ under multiplication, then any finite subgroup of ${K\backslash\{0\}}$ is cyclic.

Proof: If ${K\backslash\{0\}}$ is the group of nonzero elements of a field under multiplication, then the polynomial ${x^{n}-1}$ has at most ${n}$ roots in ${K\backslash\{0\}}$. So, if ${G\subset K\backslash\{0\}}$ is a finite multiplicative subgroup of ${K\backslash\{0\},}$ then the number of solutions of ${x^{d}=1}$ in ${G}$ is at most ${d}$ for any positive integer ${d,}$ so certainly for all ${d}$ that divide the order of ${G.}$ By Theorem 8, ${G}$ must be a cyclic group. $\Box$

A very special case of Theorem 9 is

Theorem 10 If ${K}$ is a finite field, then ${K\backslash\{0\}}$ is a cyclic.

Proof: ${K\backslash\{0\}}$ is a finite subgroup of itself, so, by Theorem 9, ${K\backslash\{0\}}$ is a cyclic group. $\Box$

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

Theorem 11 If ${p}$ is a prime, then ${\mathbb{Z}_{p}\backslash\{0\}}$ 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 ${\mathbb{P}}$ is finite and ${p}$ is the largest prime. We consider the so-called Mersenne number ${2^{p}-1}$ and show that any prime factor ${q}$ of ${2^{p}-1}$ is bigger than ${p}$, which will yield the desired conclusion. Let ${q}$ be a prime dividing ${2^{p}-1}$, so we have ${2^{p}\equiv_{q}1.}$ Since ${p}$ is prime, this means that the element ${2}$ has order ${p}$ in the multiplicative group ${\mathbb{Z}_{q}\backslash\{0\}}$ of the field ${\mathbb{Z}_{q}}$. This group has ${q-1}$ elements. By Lagrange’s theorem we know that the order of every element divides the size of the group, that is, we have ${p\mid q-1}$, and hence ${p $\Box$