Math Guide Mathematical foundations for Halo 2 and Zcash Orchard 2 The integers and modular arithmetic 4 Rings and fields

3 Groups

Two parties who have never met wish to agree on a secret value while every message they exchange is read by an eavesdropper. One solution begins with a public set carrying a single public operation and a public starting element $g$ . Each party privately chooses a count of repetitions—say $a$ and $b$ —combines $g$ with itself that many times, and publishes the result. Each then takes the other’s published element and applies their own secret count of repetitions to it. If repetition is well behaved, both arrive at the element produced by $a b$ repetitions of $g$ , and so share a secret, while the eavesdropper has seen only $g$ and the two published values. Three demands on the operation are implicit. It must compose: “ $a$ repetitions, then $b$ more” must be unambiguous however the intermediate steps are bracketed. It must invert: repetition counts should obey an arithmetic, with an identity and the possibility of undoing a step, not a mere accumulation. And it must hide repetition: recovering the secret count from the published value must be hard. The third demand is a computational matter taken up in later volumes; the first two are algebra, and this section isolates exactly the structure that supplies them.

That structure is the group, the foundational abstraction of modern algebra. A group axiomatises the bare minimum needed to discuss symmetry and invertible composition: one associative operation with an identity and inverses. Almost every object met later in this series is a group—the integers modulo a prime under addition, the nonzero residues under multiplication, the points of an elliptic curve, the symmetries of a finite field. This section develops group theory from first principles and proves its central structural results in full: Lagrange’s theorem, the classification of cyclic groups, the quotient of an abelian group by a subgroup, and the basic theory of homomorphisms and isomorphisms. The payoff for the opening problem is the cyclic-group theory together with Lagrange’s theorem: in any finite group, the arithmetic of repetition counts is precisely the modular arithmetic of 2, the modulus being the order of the repeated element—a divisor of the group’s order.

3.1 The group axioms

The first task is to make “combining two elements” precise.

Definition 3.1 (Binary operation).

Let $S$ be a set. A binary operation on $S$ is a function

\ast\colon S\times S\to S,\qquad(a,b)\mapsto a\ast b.

Closure—that $a\ast b$ again lies in $S$ —is built into the very statement that $\ast$ maps into $S$ . We name it explicitly nonetheless, because for a subset $H\subseteq S$ the question of whether $\ast$ restricts to a binary operation on $H$ is exactly the question of whether $H$ is closed under $\ast$ ; this question drives the theory of subgroups below (§3.4).

Definition 3.2 (Group).

A group is a pair $(G,\ast)$ consisting of a set $G$ and a binary operation $\ast$ on $G$ satisfying three axioms.

(G1)

Associativity. For all $a,b,c\in G$ , $(a\ast b)\ast c=a\ast(b\ast c)$ .
(G2)

Identity. There exists $e\in G$ such that $e\ast a=a\ast e=a$ for all $a\in G$ .
(G3)

Inverses. For each $a\in G$ there exists $b\in G$ such that $a\ast b=b\ast a=e$ , where $e$ is an identity as in (G2).

A set with an operation satisfying only (G1) is a semigroup; if it also satisfies (G2) it is a monoid. A group is thus a monoid in which every element is invertible.

The number of elements of $G$ , written $\lvert G\rvert$ , is the order of the group; if $\lvert G\rvert$ is finite, $G$ is a finite group, and otherwise an infinite group. We frequently say “the group $G$ ”, leaving the operation understood.

The axioms assert the existence of an identity and of inverses, but not, on their face, uniqueness. Uniqueness is a theorem—and a useful one, since it is what licenses the notations $e$ and $a^{-1}$ .

Proposition 3.3.

Let $(G,\ast)$ be a group.

1.

The identity element is unique.
2.

Each $a\in G$ has a unique inverse, denoted $a^{-1}$ .
3.

(Cancellation.) For all $a,x,y\in G$ : if $a\ast x=a\ast y$ then $x=y$ , and if $x\ast a=y\ast a$ then $x=y$ .
4.

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

Proof.

(1) Suppose $e$ and $e^{\prime}$ both satisfy (G2). Using that $e^{\prime}$ is an identity, $e=e\ast e^{\prime}$ ; using that $e$ is an identity, $e\ast e^{\prime}=e^{\prime}$ . Hence $e=e^{\prime}$ .

(2) Suppose $b$ and $b^{\prime}$ are both inverses of $a$ . Then

b=b\ast e=b\ast(a\ast b^{\prime})=(b\ast a)\ast b^{\prime}=e\ast b^{\prime}=b^% {\prime},

using (G2), the inverse property of $b^{\prime}$ , associativity, and the inverse property of $b$ .

(3) Suppose $a\ast x=a\ast y$ . Multiplying on the left by $a^{-1}$ and reassociating,

x=(a^{-1}\ast a)\ast x=a^{-1}\ast(a\ast x)=a^{-1}\ast(a\ast y)=(a^{-1}\ast a)% \ast y=y.

The right-cancellation law is proved symmetrically, multiplying on the right by $a^{-1}$ .

(4) Since $a\ast a^{-1}=a^{-1}\ast a=e$ , the element $a$ is an inverse of $a^{-1}$ ; by (2) it is the inverse, so $(a^{-1})^{-1}=a$ . For the product formula, compute

(a\ast b)\ast(b^{-1}\ast a^{-1})=a\ast(b\ast b^{-1})\ast a^{-1}=a\ast a^{-1}=e,

and symmetrically $(b^{-1}\ast a^{-1})\ast(a\ast b)=e$ ; by (2), $(a\ast b)^{-1}=b^{-1}\ast a^{-1}$ . The order reversal is the “socks–shoes” rule: the inverse of putting on socks, then shoes, is removing shoes, then socks. □

Two notational conventions dominate. Multiplicative notation writes the operation as juxtaposition $a b$ (or $a\cdot b$ ), the identity as $1$ , the inverse as $a^{-1}$ , and powers as $a^{n}=\underbrace{a\cdots a}_{n\ \text{factors}}$ for $n\geq 1$ , with $a^{0}=1$ and $a^{-n}=(a^{-1})^{n}$ . Additive notation, reserved almost exclusively for commutative groups, writes $a+b$ , the identity as $0$ , the inverse as $-a$ , and $n a$ for the $n$ -fold sum. The exponent laws

a^{m}a^{n}=a^{m+n},\qquad(a^{m})^{n}=a^{mn}

hold for all integers $m, n$ , proved by induction together with Proposition 3.3. Henceforth $a b$ denotes $a\ast b$ , and we drop the symbol $\ast$ unless clarity demands it.

The power notation presumes something the axioms do not literally grant: that an $n$ -fold product needs no brackets at all. Axiom (G1) speaks only of three factors. The gap is closed once and for all by the next proposition, and thereafter products are written without brackets and powers without comment.

Proposition 3.4 (Generalised associativity).

Let $a_{1},\dots,a_{n}$ , $n\geq 1$ , be elements of a group—or of any set with an associative operation. Every way of bracketing the product $a_{1}a_{2}\cdots a_{n}$ yields the same element, namely the left-normed product $L_{n}=(\cdots((a_{1}a_{2})a_{3})\cdots)a_{n}$ . In particular $a^{n}$ is a single well-defined element, however the $n$ factors are combined.

Proof.

By strong induction on $n$ . For $n\leq 2$ there is only one bracketing, and for $n=3$ the two bracketings agree by (G1). Let $n\geq 3$ and assume the claim for all shorter products. Any bracketed product $P$ of $a_{1},\dots,a_{n}$ has an outermost multiplication, splitting it as $P=QR$ with $Q$ a bracketed product of $a_{1},\dots,a_{k}$ and $R$ one of $a_{k+1},\dots,a_{n}$ , for some $1\leq k<n$ . The induction hypothesis evaluates both halves: $Q=L_{k}$ , and $R$ is the left-normed product of $a_{k+1},\dots,a_{n}$ . If $k=n-1$ , then $R=a_{n}$ and $P=L_{n-1}a_{n}=L_{n}$ directly. If $k<n-1$ , write $R=R^{\prime}a_{n}$ with $R^{\prime}$ the left-normed product of $a_{k+1},\dots,a_{n-1}$ ; then (G1) and the induction hypothesis, applied to the bracketed product $L_{k}R^{\prime}$ of the $n-1$ elements $a_{1},\dots,a_{n-1}$ , give

P=L_{k}(R^{\prime}a_{n})=(L_{k}R^{\prime})\,a_{n}=L_{n-1}\,a_{n}=L_{n}.

Every bracketing therefore equals $L_{n}$ . □

Definition 3.5 (Abelian group).

A group $(G,\ast)$ is abelian (or commutative) if $a\ast b=b\ast a$ for all $a,b\in G$ ; otherwise it is non-abelian.

The term honours Niels Henrik Abel. In an abelian group products may be freely reordered, and the socks–shoes formula $(ab)^{-1}=b^{-1}a^{-1}=a^{-1}b^{-1}$ loses its order-sensitivity. Convention reserves additive notation for abelian groups precisely because $+$ connotes commutativity.

3.2 First examples

Example 3.6.

The pair $(\mathbb{Z},+)$ is an infinite abelian group: addition is associative and commutative, the identity is $0$ , and the inverse of $n$ is $-n$ . Likewise $(\mathbb{Q},+)$ , $(\mathbb{R},+)$ , and $(\mathbb{C},+)$ are abelian groups. By contrast $(\mathbb{Z},\cdot)$ is not a group: the integer $2$ has no multiplicative inverse in $\mathbb{Z}$ .

Example 3.7.

The nonzero rationals $\mathbb{Q}^{\times}=\mathbb{Q}\setminus\{0\}$ form an abelian group under multiplication, with identity $1$ and inverse $1/a$ ; likewise $\mathbb{R}^{\times}$ and $\mathbb{C}^{\times}$ . Zero must be excluded because it has no multiplicative inverse. The pattern is general: for any field $F$ —the reader has met $\mathbb{Q}$ , $\mathbb{R}$ , $\mathbb{C}$ ; the abstract notion is defined in 4—the nonzero elements $F^{\times}=F\setminus\{0\}$ form an abelian group under multiplication. Indeed, this is part of the very definition of a field.

Congruence classes furnish the central finite examples. Recall from 2 the set $\mathbb{Z}/n\mathbb{Z}$ of residue classes $[a]_{n}$ and define operations on classes through representatives,

[a]_{n}+[b]_{n}=[a+b]_{n},\qquad[a]_{n}\,[b]_{n}=[ab]_{n}.

By Proposition 2.21 the right-hand sides do not depend on the representatives chosen, so both operations are well defined, and each law of integer arithmetic—associativity, commutativity, the identities $[0]_{n}$ and $[1]_{n}$ , negatives—passes to classes by computing on representatives. (The full structural statement, that these operations make $\mathbb{Z}/n\mathbb{Z}$ a commutative ring, is Theorem 4.6 in 4; the present section uses only the fragments just listed.) Addition makes all of $\mathbb{Z}/n\mathbb{Z}$ a group, as Example 3.9 below records. For $n>1$ , multiplication does not— $[0]_{n}$ has no inverse—but 2 identified exactly which classes are invertible: the units, the classes $[a]_{n}$ with $\gcd(a,n)=1$ (Theorem 2.24). The units form a group.

Proposition 3.8.

Under multiplication of classes, the set $(\mathbb{Z}/n\mathbb{Z})^{\times}$ of units of $\mathbb{Z}/n\mathbb{Z}$ is an abelian group. Its order is $\lvert(\mathbb{Z}/n\mathbb{Z})^{\times}\rvert=\varphi(n)$ , Euler’s totient of Definition 2.26: the number of integers $a$ with $1\leq a\leq n$ and $\gcd(a,n)=1$ .

Proof.

Multiplication of classes is associative and commutative with identity $[1]_{n}$ , as derived above from Proposition 2.21 by computing on representatives, and $[1]_{n}$ is a unit (it is its own inverse). The operation is closed on units: if $[a]_{n}$ and $[b]_{n}$ are units with inverses $[a]_{n}^{-1}$ and $[b]_{n}^{-1}$ , then $[ab]_{n}$ has inverse $[b]_{n}^{-1}[a]_{n}^{-1}$ , since $(ab)(b^{-1}a^{-1})\equiv 1\pmod{n}$ for any representatives of the inverse classes. Every unit has an inverse by definition, and that inverse is itself a unit (it is invertible, with inverse the original class). Hence $(\mathbb{Z}/n\mathbb{Z})^{\times}$ is an abelian group. By Theorem 2.24 its elements are exactly the classes $[a]_{n}$ with $\gcd(a,n)=1$ and $1\leq a\leq n$ , of which there are $\varphi(n)$ by Definition 2.26. □

Example 3.9.

The pair $(\mathbb{Z}/n\mathbb{Z},+)$ is an abelian group of order $n$ : the discussion above derived associativity, commutativity, the identity $[0]_{n}$ , and negatives from Proposition 2.21, and the classes number exactly $n$ (the least nonnegative residues, Definition 2.22). The invertible classes form the abelian group $(\mathbb{Z}/n\mathbb{Z})^{\times}$ of order $\varphi(n)$ under multiplication (Theorem 2.24 and Proposition 3.8). When $n=p$ is prime, every nonzero class is a unit (Example 2.27), so $(\mathbb{Z}/p\mathbb{Z})^{\times}$ has order $p-1$ —this is Example 3.7 specialised to $\mathbb{Z}/p\mathbb{Z}$ , which 4 shows to be a field and denotes $\mathbb{F}_{p}$ .

Example 3.10.

The one-element set $\{e\}$ , with its only possible operation $e\ast e=e$ , is the trivial group. The group $\mathbb{Z}/2\mathbb{Z}=\{0,1\}$ is the smallest nontrivial group. A subtler small example is the Klein four-group $V=\{e,a,b,c\}$ , in which every element composed with itself gives $e$ and the product of any two distinct nonidentity elements is the third; the verification that this table satisfies the axioms is routine. The group $V$ is abelian of order $4$ .

Although $V$ and $\mathbb{Z}/4\mathbb{Z}$ both have order $4$ , they are structurally different: in $V$ every element combined with itself returns the identity, while in $\mathbb{Z}/4\mathbb{Z}$ the class $1$ must be added to itself four times to reach $0$ . The language that makes “structurally different” precise is that of isomorphism (§3.8); in its terms, $V$ is not isomorphic to $\mathbb{Z}/4\mathbb{Z}$ , because $V$ has no element of order $4$ in the sense defined next.

3.3 The order of an element

Definition 3.11 (Order of an element).

Let $G$ be a group and $a\in G$ . The order of $a$ , written $\operatorname{ord}(a)$ , is the least positive integer $n$ with $a^{n}=e$ , if such an $n$ exists; $a$ then has finite order. If no positive power of $a$ equals $e$ , then $a$ has infinite order and one writes $\operatorname{ord}(a)=\infty$ .

The word “order” now has two meanings—the order $\lvert G\rvert$ of a group and the order $\operatorname{ord}(a)$ of an element. The clash is deliberate and is reconciled by the cyclic-group theory below: $\operatorname{ord}(a)$ equals the order of the smallest subgroup of $G$ containing $a$ (Proposition 3.21).

Proposition 3.12.

Let $a$ have finite order $d=\operatorname{ord}(a)$ , and let $m,k\in\mathbb{Z}$ .

1.

$a^{m}=e$ if and only if $d\mid m$ .
2.

$a^{m}=a^{k}$ if and only if $m\equiv k\pmod{d}$ .
3.

The distinct powers of $a$ are exactly $e=a^{0},a^{1},\dots,a^{d-1}$ .

Proof.

(1) If $d\mid m$ , write $m=dq$ ; then $a^{m}=(a^{d})^{q}=e^{q}=e$ . Conversely, suppose $a^{m}=e$ and divide with remainder (Theorem 2.4): $m=dq+r$ with $0\leq r<d$ . Then

e=a^{m}=(a^{d})^{q}\,a^{r}=a^{r},

so $r$ is a nonnegative integer smaller than $d$ with $a^{r}=e$ . Minimality of $d$ among positive exponents forces $r=0$ , whence $d\mid m$ .

(2) We have $a^{m}=a^{k}$ if and only if $a^{m-k}=e$ (multiply by $a^{-k}$ and use the exponent laws), which by (1) holds if and only if $d\mid(m-k)$ , i.e. $m\equiv k\pmod{d}$ (Definition 2.20).

(3) By (2) the powers $a^{0},a^{1},\dots,a^{d-1}$ are pairwise distinct, their exponents being pairwise incongruent modulo $d$ ; and every power $a^{m}$ equals $a^{m\bmod d}$ , again by (2). □

The final step of part (1) deserves to be isolated, because it is the recurring device of this section: to show that every witness of some property is a multiple of the least positive witness $m$ , take an arbitrary witness $t$ , divide $t=mq+r$ with $0\leq r<m$ , show that the remainder $r$ is itself a witness, and conclude $r=0$ by minimality. It is the same shape as the proof of Bézout’s identity (Theorem 2.11), transplanted from the integers into a group, and it reappears twice below: for the least positive power of $g$ lying in a subgroup (Theorem 3.24) and for the least positive element of a subgroup of $\mathbb{Z}$ (Proposition 3.26).

Example 3.13.

In $(\mathbb{Z}/n\mathbb{Z},+)$ , read the powers of Definition 3.11 additively: the $k$ -fold sum of the class $1$ is the class $k$ , which is $0$ exactly when $n\mid k$ , so $\operatorname{ord}(1)=n$ . More generally $\operatorname{ord}(a)=n/\gcd(a,n)$ for any class $a$ , by Corollary 3.23 below read additively. In $\mathbb{C}^{\times}$ the element $i$ has order $4$ : its successive powers are

i^{1}=i,\qquad i^{2}=-1,\qquad i^{3}=-i,\qquad i^{4}=1.

In $(\mathbb{Z},+)$ every nonzero element has infinite order: no nonzero multiple of a nonzero integer is $0$ .

3.4 Subgroups

Definition 3.14 (Subgroup).

A subset $H\subseteq G$ of a group $(G,\ast)$ is a subgroup, written $H\leq G$ , if $H$ is itself a group under the restriction of $\ast$ to $H\times H$ : explicitly, $H$ is nonempty, closed under $\ast$ , contains the identity $e$ of $G$ , and contains $a^{-1}$ whenever it contains $a$ . Every group has the trivial subgroup $\{e\}$ and $G$ itself; a subgroup other than $G$ is proper.

Two small points keep this definition honest. First, the identity of a subgroup necessarily coincides with the identity of $G$ : if $e_{H}\in H$ satisfies $e_{H}\ast e_{H}=e_{H}$ , then cancelling $e_{H}$ in $G$ against $e_{H}\ast e=e_{H}$ (Proposition 3.3(3)) gives $e_{H}=e$ . Second, inverses computed in $H$ agree with those computed in $G$ , by uniqueness of inverses in $G$ . Nothing about $H$ , in other words, depends on whether we regard it as a group in its own right or as a subset of $G$ .

Checking all the group axioms for a subset would be wasteful, since associativity is inherited for free. A single condition suffices.

Proposition 3.15 (One-step subgroup test).

Let $G$ be a group and $H\subseteq G$ . Then $H\leq G$ if and only if

1.

$H$ is nonempty, and
2.

for all $a,b\in H$ , the element $ab^{-1}$ lies in $H$ .

Proof.

If $H\leq G$ , then $H$ is nonempty and, for $a,b\in H$ , it contains $b^{-1}$ and hence $ab^{-1}$ ; both conditions hold.

Conversely, suppose (1) and (2) hold. Pick $a\in H$ by (1); taking $b=a$ in (2) gives $e=aa^{-1}\in H$ . For any $b\in H$ , taking the pair $(e,b)$ in (2) gives $b^{-1}=eb^{-1}\in H$ , so $H$ is closed under inverses. Finally, for $a,b\in H$ we now know $b^{-1}\in H$ , and applying (2) to the pair $(a,b^{-1})$ gives $a(b^{-1})^{-1}=ab\in H$ , so $H$ is closed under the operation. Associativity is inherited from $G$ , so $H$ is a group. □

Remark 3.16.

For a finite nonempty subset $H$ , closure under the operation alone forces $H\leq G$ . Indeed, given $a\in H$ , closure puts all the powers $a,a^{2},a^{3},\dots$ in $H$ ; since $H$ is finite they cannot all be distinct, so $a^{i}=a^{j}$ for some $i<j$ , giving $a^{j-i}=e\in H$ . Then $a^{-1}=a^{j-i-1}\in H$ : this is a positive power of $a$ when $j-i\geq 2$ , and when $j-i=1$ we have $a=e$ , whose inverse $e$ already lies in $H$ . Thus for finite subsets, closure under multiplication is the only condition to verify.

Example 3.17.

The even integers $2\mathbb{Z}=\{2k:k\in\mathbb{Z}\}$ form a subgroup of $(\mathbb{Z},+)$ : the set is nonempty, and $2k-2l=2(k-l)$ is again even (the subgroup test, written additively). More generally $n\mathbb{Z}=\{nk:k\in\mathbb{Z}\}\leq\mathbb{Z}$ for every $n\geq 0$ , by the same computation—and these are all the subgroups of $\mathbb{Z}$ , as Proposition 3.26 will show.

Proposition 3.18.

The intersection $\bigcap_{i\in I}H_{i}$ of any family of subgroups $H_{i}\leq G$ is a subgroup of $G$ .

Proof.

The identity $e$ lies in every $H_{i}$ , so the intersection is nonempty. If $a$ and $b$ lie in the intersection, then for each $i$ both lie in $H_{i}$ , so $ab^{-1}\in H_{i}$ by Proposition 3.15; hence $ab^{-1}$ lies in the intersection, and the one-step test applies. □

Proposition 3.18 is what makes “the smallest subgroup containing a given set” well defined: the intersection of all subgroups containing the set is itself a subgroup containing the set, and it is contained in every other one.

Definition 3.19 (Generated subgroup).

For a subset $S\subseteq G$ , the subgroup generated by $S$ , written $\langle S\rangle$ , is the intersection of all subgroups of $G$ containing $S$ . By Proposition 3.18 it is a subgroup, and by construction it is the smallest subgroup of $G$ containing $S$ .

Concretely, $\langle S\rangle$ consists of all finite products $s_{1}^{\varepsilon_{1}}s_{2}^{\varepsilon_{2}}\cdots s_{k}^{\varepsilon_{k}}$ with $s_{i}\in S$ and $\varepsilon_{i}\in\{+1,-1\}$ , the empty product being $e$ . Indeed, the set of such products contains $S$ , contains $e$ , and is closed under multiplication (concatenate) and under inversion (reverse the factors and negate the exponents, by the socks–shoes rule), so it is a subgroup containing $S$ ; conversely, every subgroup containing $S$ is closed under these operations and so contains every such product. Hence the two descriptions coincide.

3.5 Cyclic groups

Definition 3.20 (Cyclic group).

A group $G$ is cyclic if there exists $g\in G$ with

G=\langle g\rangle=\{\,g^{k}:k\in\mathbb{Z}\,\};

such an element $g$ is a generator of $G$ .

The displayed description matches Definition 3.19: the set $\{g^{k}:k\in\mathbb{Z}\}$ contains $g$ , and it is closed under products and inverses by the exponent laws, so it is a subgroup containing $g$ ; conversely any subgroup containing $g$ must contain all its powers. Hence $\langle g\rangle=\{g^{k}:k\in\mathbb{Z}\}$ : for a single element $g$ , the general generated-subgroup construction and the naive one agree. Every cyclic group is abelian, since $g^{m}g^{n}=g^{m+n}=g^{n}g^{m}$ .

Proposition 3.21.

Let $G=\langle g\rangle$ be cyclic.

1.

If $g$ has infinite order, the powers $g^{k}$ $(k\in\mathbb{Z})$ are pairwise distinct, so $G$ is infinite.
2.

If $g$ has finite order $d$ , then $G=\{e,g,g^{2},\dots,g^{d-1}\}$ has exactly $d$ elements.

In both cases $\lvert\langle g\rangle\rvert=\operatorname{ord}(g)$ .

Proof.

(1) Suppose $g^{i}=g^{j}$ with $i\neq j$ ; without loss of generality $i>j$ . Then $g^{i-j}=e$ with $i-j>0$ , contradicting infinite order. So the powers are pairwise distinct and $G$ is infinite.

(2) This is Proposition 3.12(3): the distinct powers of $g$ are exactly $g^{0},g^{1},\dots,g^{d-1}$ , and these exhaust $G=\{g^{k}:k\in\mathbb{Z}\}$ . □

Example 3.22.

The group $(\mathbb{Z},+)$ is infinite cyclic, generated by $1$ and also by $-1$ . The group $(\mathbb{Z}/n\mathbb{Z},+)$ is cyclic of order $n$ , generated by $1$ (Example 3.13). The unit group $(\mathbb{Z}/8\mathbb{Z})^{\times}=\{1,3,5,7\}$ is not cyclic: each of its four elements squares to $1$ ( $3^{2}=9\equiv 1$ , $5^{2}=25\equiv 1$ , $7^{2}=49\equiv 1\pmod{8}$ ), so no element has order $4$ . By contrast $(\mathbb{Z}/5\mathbb{Z})^{\times}=\{1,2,3,4\}$ is cyclic, generated by $2$ : its powers run

2^{1}\equiv 2,\qquad 2^{2}\equiv 4,\qquad 2^{3}\equiv 3,\qquad 2^{4}\equiv 1% \pmod{5},

exhausting the group.

The order of a power of $g$ is determined by a gcd, and the formula tells us exactly which powers are again generators.

Corollary 3.23.

Let $g$ have finite order $n$ and let $k\in\mathbb{Z}$ . Then

\operatorname{ord}(g^{k})=\frac{n}{\gcd(n,k)}.

In particular $g^{k}$ generates $\langle g\rangle$ if and only if $\gcd(n,k)=1$ , so a cyclic group of order $n$ has exactly $\varphi(n)$ generators.

Proof.

Set $d=\gcd(n,k)$ and write $k=dk^{\prime}$ , $n=dn^{\prime}$ with $\gcd(n^{\prime},k^{\prime})=1$ . For $m\geq 1$ ,

(g^{k})^{m}=g^{km}=e\iff n\mid km\iff dn^{\prime}\mid dk^{\prime}m\iff n^{% \prime}\mid k^{\prime}m\iff n^{\prime}\mid m,

using Proposition 3.12(1) for the first equivalence and Euclid’s lemma (Proposition 2.15(1), with $\gcd(n^{\prime},k^{\prime})=1$ ) for the last. The least positive such $m$ is $n^{\prime}=n/d$ , which is therefore $\operatorname{ord}(g^{k})$ .

For the second claim, $\langle g^{k}\rangle\subseteq\langle g\rangle$ always, and by Proposition 3.21 the subgroup $\langle g^{k}\rangle$ has $\operatorname{ord}(g^{k})=n/\gcd(n,k)$ elements; it equals the $n$ -element set $\langle g\rangle$ exactly when $\gcd(n,k)=1$ . Since the powers $g^{1},g^{2},\dots,g^{n}$ run through each element of $\langle g\rangle$ exactly once (Proposition 3.12(3)), the generators correspond to the $k\in\{1,\dots,n\}$ with $\gcd(n,k)=1$ , of which there are $\varphi(n)$ by Definition 2.26. □

The subgroups of a cyclic group can be classified completely. The theorem below is used constantly in the sequel; its part (3) is the origin of the “one subgroup per divisor” picture of $\mathbb{Z}/n\mathbb{Z}$ .

Theorem 3.24 (Subgroups of cyclic groups).

Let $G=\langle g\rangle$ be a cyclic group.

1.

Every subgroup of $G$ is cyclic.
2.

If $G$ is infinite, its subgroups are exactly $\langle g^{m}\rangle$ for $m\geq 0$ ; distinct $m\geq 0$ give distinct subgroups, and for $m\geq 1$ the subgroup $\langle g^{m}\rangle$ is isomorphic to $(\mathbb{Z},+)$ .
3.

If $\lvert G\rvert=n$ , then for each positive divisor $d\mid n$ there is exactly one subgroup of $G$ of order $d$ , namely $\langle g^{n/d}\rangle$ , and these are all the subgroups of $G$ . Subgroups of $G$ thus correspond bijectively to positive divisors of $n$ .

Proof.

(1) Let $H\leq G$ . If $H=\{e\}$ , then $H=\langle e\rangle$ is cyclic. Otherwise $H$ contains some $g^{t}\neq e$ , so $t\neq 0$ ; since $H$ also contains $(g^{t})^{-1}=g^{-t}$ , it contains a power of $g$ with positive exponent. Let $m$ be the least positive integer with $g^{m}\in H$ (well-ordering, Theorem 2.1). We claim $H=\langle g^{m}\rangle$ . The inclusion $\supseteq$ holds by closure. For $\subseteq$ , take any element of $H$ ; it is some $g^{t}$ , since $H\subseteq G=\langle g\rangle$ . Divide $t=mq+r$ with $0\leq r<m$ ; then

g^{r}=g^{t-mq}=g^{t}\,(g^{m})^{-q}\in H,

and minimality of $m$ forces $r=0$ —the division-minimality device again. Hence $g^{t}=(g^{m})^{q}\in\langle g^{m}\rangle$ .

(2) Let $G$ be infinite. Then $g$ has infinite order, for otherwise $G$ would be finite by Proposition 3.21(2). By part (1) every subgroup is $\{e\}=\langle g^{0}\rangle$ or $\langle g^{m}\rangle$ with $m\geq 1$ least positive, and conversely each $\langle g^{m}\rangle$ is a subgroup. For distinctness, note that for $m\geq 1$ the positive exponents $t$ with $g^{t}\in\langle g^{m}\rangle$ are exactly the positive multiples of $m$ : the elements of $\langle g^{m}\rangle$ are the powers $g^{mk}$ , and $g^{t}=g^{mk}$ forces $t=mk$ because distinct exponents give distinct powers (Proposition 3.21(1)). The least such exponent recovers $m$ , so distinct $m\geq 1$ give distinct subgroups, and each differs from $\{e\}$ because $g^{m}\neq e$ . Finally, for $m\geq 1$ the element $g^{m}$ has infinite order (if $(g^{m})^{t}=g^{mt}=e$ then $mt=0$ , so $t=0$ ), so $\langle g^{m}\rangle$ is an infinite cyclic group and is therefore isomorphic to $(\mathbb{Z},+)$ by Theorem 3.43(1) below. No circularity arises: the proof of that theorem uses only Propositions 3.12 and 3.21.

(3) Let $\lvert G\rvert=n$ , so $\operatorname{ord}(g)=n$ by Proposition 3.21.

Existence. Let $d\mid n$ be a positive divisor. Since $n/d$ divides $n$ , we have $\gcd(n,n/d)=n/d$ , so Corollary 3.23 gives

\operatorname{ord}\bigl{(}g^{n/d}\bigr{)}=\frac{n}{\gcd(n,\,n/d)}=\frac{n}{n/d% }=d,

and $\langle g^{n/d}\rangle$ is a subgroup of order $d$ by Proposition 3.21.

Uniqueness. Let $H\leq G$ with $\lvert H\rvert=d$ . If $d=1$ then $H=\{e\}=\langle g^{n}\rangle=\langle g^{n/1}\rangle$ , since $g^{n}=e$ . Otherwise, as in part (1), $H=\langle g^{m}\rangle$ for the least positive $m$ with $g^{m}\in H$ , and Propositions 3.12 and 3.21 together with Corollary 3.23 give

d=\lvert H\rvert=\operatorname{ord}(g^{m})=\frac{n}{\gcd(n,m)},\qquad\text{so}% \qquad\gcd(n,m)=\frac{n}{d}.

In particular $n/d$ divides $m$ , say $m=(n/d)\,m^{\prime}$ ; then $g^{m}=(g^{n/d})^{m^{\prime}}$ , so $H=\langle g^{m}\rangle\subseteq\langle g^{n/d}\rangle$ . Both sides have exactly $d$ elements, so $H=\langle g^{n/d}\rangle$ .

All subgroups arise. Any $H\leq G$ equals some $\langle g^{m}\rangle$ (or $\{e\}$ ), whose order $n/\gcd(n,m)$ is a positive divisor $d$ of $n$ ; by uniqueness $H=\langle g^{n/d}\rangle$ . The assignment $d\mapsto\langle g^{n/d}\rangle$ is therefore surjective onto the set of subgroups, and it is injective because subgroups of different orders are distinct. This is the asserted bijection. □

Remark 3.25.

Specialised to $G=\mathbb{Z}/n\mathbb{Z}$ with generator $1$ (written additively), Theorem 3.24(3) reads: for each divisor $d\mid n$ there is exactly one subgroup of order $d$ , namely

\langle n/d\rangle=\{\,0,\ n/d,\ 2n/d,\ \dots,\ (d-1)\,n/d\,\},

itself cyclic of order $d$ , hence isomorphic to $\mathbb{Z}/d\mathbb{Z}$ by the classification below. For $n=12$ the six subgroups correspond to the divisors $1,2,3,4,6,12$ , and inclusion between subgroups mirrors divisibility between the corresponding divisors: the subgroup lattice of $\mathbb{Z}/12\mathbb{Z}$ is the divisor lattice of $12$ , with chains such as $1\mid 2\mid 4$ , $1\mid 2\mid 6$ , and $3\mid 6$ .

The classification promised in Example 3.17 now follows; it is Theorem 3.24(2) read additively for $G=(\mathbb{Z},+)=\langle 1\rangle$ , but the direct argument is short enough to give in full.

Proposition 3.26.

Every subgroup of $(\mathbb{Z},+)$ has the form $n\mathbb{Z}$ for a unique integer $n\geq 0$ .

Proof.

Let $H\leq\mathbb{Z}$ . If $H=\{0\}$ , then $H=0\mathbb{Z}$ . Otherwise $H$ contains a nonzero integer and, being closed under negation, contains a positive one; let $n$ be its least positive element (Theorem 2.1). Closure under addition and negation gives $n\mathbb{Z}\subseteq H$ . Conversely, for any $h\in H$ , divide $h=nq+r$ with $0\leq r<n$ ; then $r=h-nq\in H$ , and minimality of $n$ forces $r=0$ , so $h\in n\mathbb{Z}$ . Hence $H=n\mathbb{Z}$ . For uniqueness, note $n$ is recovered from $H$ as its least positive element (and $n=0$ exactly for $H=\{0\}$ ), so distinct $n\geq 0$ give distinct subgroups. □

3.6 Cosets and Lagrange’s theorem

A subgroup $H\leq G$ slices $G$ into translated copies of itself, and counting the slices is the mechanism underlying Lagrange’s theorem: partition the group into blocks, exhibit a bijection between each block and $H$ , and multiply the block count by the block size. The blocks are the cosets.

Definition 3.27 (Cosets and index).

Let $H\leq G$ and $a\in G$ . The left coset of $H$ by $a$ is

aH=\{\,ah:h\in H\,\},

and the right coset is $Ha=\{ha:h\in H\}$ . In additive notation one writes $a+H=\{a+h:h\in H\}$ . The set of left cosets is denoted $G/H$ , and the index of $H$ in $G$ is $[G:H]=\lvert G/H\rvert$ , the number of left cosets.

Lemma 3.28 (Cosets partition the group).

Let $H\leq G$ .

1.

Each $a\in G$ lies in $a H$ ; the left cosets cover $G$ .
2.

Two left cosets are either equal or disjoint: $aH=bH$ if and only if $a^{-1}b\in H$ , and otherwise $aH\cap bH=\varnothing$ .
3.

Every left coset has the same cardinality as $H$ : the map $h\mapsto ah$ is a bijection from $H$ onto $a H$ .

The same statements hold for right cosets, with $ba^{-1}\in H$ as the criterion in (2).

Proof.

(1) Since $e\in H$ , we have $a=ae\in aH$ .

(2) First suppose the cosets meet: $ah_{1}=bh_{2}$ for some $h_{1},h_{2}\in H$ . Then $a^{-1}b=h_{1}h_{2}^{-1}\in H$ . Conversely, suppose $a^{-1}b=h\in H$ , so $b=ah$ . Then every element $bh^{\prime}\in bH$ equals $a(hh^{\prime})\in aH$ , giving $bH\subseteq aH$ ; and since $b^{-1}a=h^{-1}\in H$ , the same argument with the roles of $a$ and $b$ exchanged gives $aH\subseteq bH$ . Hence $aH=bH$ . Combining the two directions: if two cosets share even one element they coincide, so distinct cosets are disjoint.

(3) The map $\lambda_{a}\colon H\to aH$ , $h\mapsto ah$ , is surjective by the definition of $a H$ and injective by left cancellation (Proposition 3.3(3)): $ah=ah^{\prime}$ implies $h=h^{\prime}$ . Hence $\lvert aH\rvert=\lvert H\rvert$ .

For right cosets, the same three arguments apply with sides exchanged; in (2) the criterion becomes $ba^{-1}\in H$ . □

Theorem 3.29 (Lagrange’s theorem).

Let $G$ be a finite group and $H\leq G$ . Then $\lvert H\rvert$ divides $\lvert G\rvert$ , and

\lvert G\rvert=[G:H]\,\lvert H\rvert.

Proof.

By Lemma 3.28, the distinct left cosets of $H$ partition $G$ : they cover $G$ by part (1) and are pairwise disjoint by part (2). Since $G$ is finite there are finitely many of them, say $[G:H]=k$ , and each has exactly $\lvert H\rvert$ elements by part (3). Summing the sizes of the blocks of the partition,

\lvert G\rvert=\sum_{\text{distinct cosets }aH}\lvert aH\rvert=k\,\lvert H% \rvert=[G:H]\,\lvert H\rvert.\qed

Three corollaries follow in quick succession; the third is the theorem this section owes to the rest of the volume.

Corollary 3.30.

In a finite group $G$ , the order of every element divides $\lvert G\rvert$ .

Proof.

For $a\in G$ , the cyclic subgroup $\langle a\rangle$ has order $\operatorname{ord}(a)$ by Proposition 3.21 (the order is finite, since $\langle a\rangle\subseteq G$ is finite), and Theorem 3.29 makes $\lvert\langle a\rangle\rvert$ a divisor of $\lvert G\rvert$ . □

Corollary 3.31.

If $G$ is a finite group of order $N$ , then $a^{N}=e$ for every $a\in G$ .

Proof.

Let $d=\operatorname{ord}(a)$ . By Corollary 3.30, $d\mid N$ , say $N=dm$ ; then $a^{N}=(a^{d})^{m}=e^{m}=e$ . □

Corollary 3.32 (Euler’s theorem; Fermat’s little theorem).

Let $n\geq 1$ and $a\in\mathbb{Z}$ with $\gcd(a,n)=1$ . Then

a^{\varphi(n)}\equiv 1\pmod{n}.

In particular, for a prime $p$ and $a$ not divisible by $p$ ,

a^{p-1}\equiv 1\pmod{p},

and $a^{p}\equiv a\pmod{p}$ holds for all integers $a$ .

Proof.

Apply Corollary 3.31 to the group $(\mathbb{Z}/n\mathbb{Z})^{\times}$ , which has order $\varphi(n)$ (Proposition 3.8). For $\gcd(a,n)=1$ the class $[a]_{n}$ is a unit (Theorem 2.24), so $[a]_{n}^{\varphi(n)}=[1]_{n}$ , which is the first congruence. For $n=p$ prime, $\varphi(p)=p-1$ (Example 2.27), and $p\nmid a$ gives $\gcd(a,p)=1$ , yielding the second congruence. Multiplying it by $a$ gives $a^{p}\equiv a\pmod{p}$ ; and when $p\mid a$ both sides are congruent to $0$ , so the last congruence holds for all $a$ . □

Remark 3.33.

The congruences of Corollary 3.32 are proved here, once; 7 restates them under the heading Fermat’s little theorem and Euler’s theorem and develops their cryptographic role there, citing this proof rather than repeating it.

Corollary 3.34.

Every group $G$ of prime order $p$ is cyclic, hence isomorphic to $\mathbb{Z}/p\mathbb{Z}$ , and has no proper nontrivial subgroups.

Proof.

Pick $a\in G$ with $a\neq e$ (possible since $p\geq 2$ ). The subgroup $\langle a\rangle$ has at least two elements, and by Theorem 3.29 its order divides $p$ ; a divisor of $p$ exceeding $1$ equals $p$ , so $\langle a\rangle=G$ and $G$ is cyclic. The isomorphism with $\mathbb{Z}/p\mathbb{Z}$ is Theorem 3.43 below. Finally, any subgroup has order $1$ or $p$ by Lagrange, i.e. is $\{e\}$ or $G$ . □

3.7 Quotients of abelian groups

Cosets do more than count: for an abelian group they themselves form a group. This single construction underlies the quotient rings of 4 and, through them, $\mathbb{Z}/n\mathbb{Z}$ and the polynomial quotients used throughout the series; it is all of quotient theory the volume requires.

Proposition 3.35 (Quotient of an abelian group).

Let $A$ be an abelian group, written additively, and let $H\leq A$ . The operation

(a+H)+(b+H)=(a+b)+H

on the coset set $A/H$ is well defined and makes $A/H$ an abelian group—the quotient group of $A$ by $H$ —with identity $H=0+H$ and inverse $-(a+H)=(-a)+H$ . If $A$ is finite, then

\lvert A/H\rvert=[A:H]=\frac{\lvert A\rvert}{\lvert H\rvert}.

Proof.

The only point of substance is that the operation is well defined: its output is stated in terms of chosen representatives $a$ and $b$ , and we must check that replacing them by other representatives of the same cosets leaves the result unchanged. Suppose then that $a+H=a^{\prime}+H$ and $b+H=b^{\prime}+H$ . By Lemma 3.28(2), written additively, this means $a^{\prime}-a\in H$ and $b^{\prime}-b\in H$ . Then

(a^{\prime}+b^{\prime})-(a+b)=(a^{\prime}-a)+(b^{\prime}-b)\in H,

since $H$ is closed under addition; applying Lemma 3.28(2) once more, $(a^{\prime}+b^{\prime})+H=(a+b)+H$ . The operation is well defined. This representative-independence check is the template for every coset-wise construction in the volume; it recurs, in the same words, for quotient-ring multiplication in 4.

The axioms now pass coset-wise from $A$ : for associativity,

\bigl{(}(a+H)+(b+H)\bigr{)}+(c+H)=\bigl{(}(a+b)+c\bigr{)}+H=\bigl{(}a+(b+c)% \bigr{)}+H=(a+H)+\bigl{(}(b+H)+(c+H)\bigr{)};

commutativity follows the same way from commutativity in $A$ ; the coset $0+H=H$ is an identity; and $(-a)+H$ is an inverse of $a+H$ . Hence $A/H$ is an abelian group. When $A$ is finite, the number of cosets is $[A:H]=\lvert A\rvert/\lvert H\rvert$ by Theorem 3.29—the same partition-into-equal-blocks count as before. □

The construction is not new to this volume in disguise: for $A=(\mathbb{Z},+)$ and $H=n\mathbb{Z}$ , Definition 2.22 exhibits each residue class as $[a]_{n}=a+n\mathbb{Z}$ , a coset of $n\mathbb{Z}\leq\mathbb{Z}$ , and the coset addition above is exactly addition of classes. The notation $\mathbb{Z}/n\mathbb{Z}$ , introduced in 2 as a bare name for the set of classes, is thus an instance of the general quotient notation $A/H$ , and $(\mathbb{Z}/n\mathbb{Z},+)$ is the quotient group $\mathbb{Z}/n\mathbb{Z}$ in the sense just constructed.

Remark 3.36.

For a non-abelian group $G$ the same construction succeeds exactly for those subgroups $N\leq G$ whose left and right cosets coincide, $gN=Ng$ for all $g\in G$ ; these are the normal subgroups. Commutativity makes every subgroup of an abelian group normal, which is why no extra hypothesis was needed in Proposition 3.35. The present volume deliberately needs only the abelian case, and we do not develop the general theory.

3.8 Homomorphisms and isomorphisms

Groups are compared through the maps that respect their operations.

Definition 3.37 (Group homomorphism).

Let $(G,\ast)$ and $(G^{\prime},\circ)$ be groups. A function $\phi\colon G\to G^{\prime}$ is a group homomorphism if

\phi(a\ast b)=\phi(a)\circ\phi(b)\qquad\text{for all }a,b\in G.

The set of all homomorphisms from $G$ to $G^{\prime}$ is denoted $\operatorname{Hom}(G,G^{\prime})$ .

Proposition 3.38.

Let $\phi\colon G\to G^{\prime}$ be a homomorphism, and write $e,e^{\prime}$ for the identities of $G$ and $G^{\prime}$ .

1.

$\phi(e)=e^{\prime}$ .
2.

$\phi(a^{-1})=\phi(a)^{-1}$ for all $a\in G$ .
3.

$\phi(a^{n})=\phi(a)^{n}$ for all $a\in G$ and $n\in\mathbb{Z}$ .
4.

The image $\phi(G)$ is a subgroup of $G^{\prime}$ .

Proof.

(1) From $e=e\ast e$ we get $\phi(e)=\phi(e)\circ\phi(e)$ ; cancelling $\phi(e)$ in $G^{\prime}$ (Proposition 3.3(3)) gives $e^{\prime}=\phi(e)$ .

(2) Applying $\phi$ to $a\ast a^{-1}=e=a^{-1}\ast a$ and using (1),

\phi(a)\circ\phi(a^{-1})=e^{\prime}=\phi(a^{-1})\circ\phi(a),

so $\phi(a^{-1})$ is an inverse of $\phi(a)$ ; by uniqueness of inverses, $\phi(a^{-1})=\phi(a)^{-1}$ .

(3) For $n\geq 0$ , induct: the case $n=0$ is (1), and $\phi(a^{n+1})=\phi(a^{n}\ast a)=\phi(a)^{n}\circ\phi(a)=\phi(a)^{n+1}$ . For $n<0$ , write $n=-m$ with $m>0$ and combine with (2): $\phi(a^{-m})=\phi((a^{-1})^{m})=\phi(a^{-1})^{m}=(\phi(a)^{-1})^{m}=\phi(a)^{-m}$ .

(4) The image is nonempty, containing $e^{\prime}=\phi(e)$ . For $x=\phi(a)$ and $y=\phi(b)$ in $\phi(G)$ ,

x\circ y^{-1}=\phi(a)\circ\phi(b)^{-1}=\phi(a\ast b^{-1})\in\phi(G),

using (2); the one-step subgroup test (Proposition 3.15) concludes. □

Definition 3.39 (Kernel and image).

The kernel and image of a homomorphism $\phi\colon G\to G^{\prime}$ are

\ker(\phi)=\{\,a\in G:\phi(a)=e^{\prime}\,\}=\phi^{-1}(\{e^{\prime}\}),\qquad% \operatorname{im}(\phi)=\phi(G)=\{\,\phi(a):a\in G\,\}.

Proposition 3.40.

For any homomorphism $\phi\colon G\to G^{\prime}$ , the kernel is a subgroup, $\ker(\phi)\leq G$ , and $\phi$ is injective if and only if $\ker(\phi)=\{e\}$ .

Proof.

The kernel contains $e$ by Proposition 3.38(1), so it is nonempty; and for $a,b\in\ker(\phi)$ ,

\phi(ab^{-1})=\phi(a)\circ\phi(b)^{-1}=e^{\prime}\circ(e^{\prime})^{-1}=e^{% \prime},

so $ab^{-1}\in\ker(\phi)$ ; the one-step test gives $\ker(\phi)\leq G$ .

If $\phi$ is injective and $\phi(a)=e^{\prime}=\phi(e)$ , then $a=e$ ; the kernel is trivial. Conversely, suppose $\ker(\phi)=\{e\}$ and $\phi(a)=\phi(b)$ . Then $\phi(ab^{-1})=\phi(a)\circ\phi(b)^{-1}=e^{\prime}$ , so $ab^{-1}\in\ker(\phi)=\{e\}$ , forcing $ab^{-1}=e$ , i.e. $a=b$ . □

Kernels are exactly the subgroups by which one may quotient: for abelian $G$ , Proposition 3.35 forms $G/\ker(\phi)$ directly, and in general the kernel satisfies the normality condition of Remark 3.36—for $n\in\ker(\phi)$ and $g\in G$ , one computes $\phi(gng^{-1})=\phi(g)\circ e^{\prime}\circ\phi(g)^{-1}=e^{\prime}$ , so conjugating the kernel by $g$ lands back in the kernel, whence $g\ker(\phi)=\ker(\phi)\,g$ .

Definition 3.41 (Isomorphism).

An isomorphism is a bijective homomorphism $\phi\colon G\to G^{\prime}$ ; when one exists, the groups are isomorphic, written $G\cong G^{\prime}$ . An isomorphism from $G$ to itself is an automorphism. An injective homomorphism is a monomorphism; a surjective one is an epimorphism.

Proposition 3.42.

The set-theoretic inverse of an isomorphism is an isomorphism, and $\cong$ is an equivalence relation on any collection of groups.

Proof.

Let $\phi\colon G\to G^{\prime}$ be an isomorphism, with inverse function $\phi^{-1}$ (which exists since $\phi$ is a bijection, Theorem 1.1). For $x,y\in G^{\prime}$ , write $x=\phi(a)$ and $y=\phi(b)$ ; then

\phi^{-1}(x\circ y)=\phi^{-1}\bigl{(}\phi(a\ast b)\bigr{)}=a\ast b=\phi^{-1}(x% )\ast\phi^{-1}(y),

so $\phi^{-1}$ is a homomorphism, and it is a bijection; hence an isomorphism. For the equivalence relation: reflexivity is witnessed by the identity automorphism $\operatorname{id}_{G}$ ; symmetry by the inverse just constructed; and transitivity because a composite of homomorphisms is a homomorphism (apply the defining property twice) and a composite of bijections is a bijection. □

Isomorphic groups are “the same group” for every group-theoretic purpose: any property expressible in terms of the operation alone— orders of elements, the lattice of subgroups, commutativity—transfers across an isomorphism. One therefore classifies groups up to isomorphism, and the classification of cyclic groups is the model result of this kind: up to isomorphism there is exactly one cyclic group of each order.

Theorem 3.43 (Classification of cyclic groups).

Every cyclic group is isomorphic to exactly one of the following:

1.

the infinite cyclic group $(\mathbb{Z},+)$ , if it is infinite;
2.

the finite cyclic group $(\mathbb{Z}/n\mathbb{Z},+)$ , if it has order $n$ .

In particular, two cyclic groups are isomorphic if and only if they have the same order.

Proof.

Let $G=\langle g\rangle$ and define

\phi\colon\mathbb{Z}\to G,\qquad\phi(k)=g^{k}.

The exponent law $g^{k+l}=g^{k}g^{l}$ says exactly that $\phi$ is a homomorphism from $(\mathbb{Z},+)$ to $G$ , and $\phi$ is surjective because every element of $G$ is a power of $g$ .

Case 1: $g$ has infinite order. Distinct exponents give distinct powers (Proposition 3.21(1)), so $\phi$ is injective, hence a bijective homomorphism, and $\mathbb{Z}\cong G$ .

Case 2: $\operatorname{ord}(g)=n$ . By Proposition 3.12(1),

\ker(\phi)=\{\,k\in\mathbb{Z}:g^{k}=e\,\}=n\mathbb{Z}.

Define the induced map

\bar{\phi}\colon\mathbb{Z}/n\mathbb{Z}\to G,\qquad\bar{\phi}([k]_{n})=g^{k}.

It is well defined: if $[k]_{n}=[l]_{n}$ then $n\mid(k-l)$ , so $g^{k}=g^{l}$ by Proposition 3.12(2). It is a homomorphism: $\bar{\phi}([k]_{n}+[l]_{n})=\bar{\phi}([k+l]_{n})=g^{k+l}=\bar{\phi}([k]_{n})% \,\bar{\phi}([l]_{n})$ . It is surjective because $\phi$ is. And it is injective by Proposition 3.40: if $\bar{\phi}([k]_{n})=g^{k}=e$ , then $n\mid k$ (Proposition 3.12(1)), so $[k]_{n}=[0]_{n}$ ; the kernel of $\bar{\phi}$ is trivial. Hence $\mathbb{Z}/n\mathbb{Z}\cong G$ .

Distinctness. Isomorphic groups have equal order, an isomorphism being in particular a bijection. The group $\mathbb{Z}$ is infinite and the groups $\mathbb{Z}/n\mathbb{Z}$ for $n=1,2,3,\dots$ have the pairwise distinct finite orders $n$ , so no two of the listed groups are isomorphic, and a cyclic group is isomorphic to exactly one of them—the one matching its order. The final claim follows: cyclic groups of equal order are isomorphic to the same listed group, hence to each other (Proposition 3.42), and isomorphic groups have equal order. □

The cheque presented at the head of the section can now be cashed. Fix any finite group $G$ and a public element $g\in G$ , and let $n=\operatorname{ord}(g)$ . Associativity makes “ $a$ repetitions of $g$ ” unambiguous—the element $g^{a}$ , however bracketed, by generalised associativity (Proposition 3.4)—and the exponent laws give

\bigl{(}g^{a}\bigr{)}^{b}=g^{ab}=\bigl{(}g^{b}\bigr{)}^{a},

so the two parties of the opening protocol, each applying a secret repetition count to the other’s published value, really do arrive at a common secret element. Repetition counts obey an arithmetic, not a mere accumulation: by the classification theorem the subgroup $\langle g\rangle$ is a copy of $\mathbb{Z}/n\mathbb{Z}$ , so exponents add, negate, and matter only modulo $n$ (Proposition 3.12)—the modular arithmetic of 2, transplanted into the exponent. Lagrange’s theorem locates the modulus: $n$ divides $\lvert G\rvert$ , and $a^{\lvert G\rvert}=e$ for every $a\in G$ (Corollary 3.31); in the unit groups $(\mathbb{Z}/n\mathbb{Z})^{\times}$ this specialises to Euler’s congruence $a^{\varphi(n)}\equiv 1\pmod{n}$ (Corollary 3.32). Composition and inversion, the first two demands of the opening problem, are thereby supplied in full generality. The third demand—that publishing $g^{a}$ should hide $a$ —is not a theorem of algebra at all: it is a statement about computation, and it fails in some groups (in $(\mathbb{Z}/n\mathbb{Z},+)$ , recovering $a$ from $a g$ is a single modular division) while appearing to hold in others. Making the demand precise, and building the groups for which it is credible, occupies the sections that follow and the volumes above them.