The Zcash ArboretumI–IX The Complete Arboretum
Contents
PDF
Theme

3 Groups

This section defines the group, a set with one associative operation that has an identity and inverses, and proves the results on groups that the series uses: Lagrange’s theorem (Theorem 3.29), with the corollary on which the rest of the volume relies, Euler’s theorem and Fermat’s little theorem (Corollary 3.32); the subgroups and the classification of cyclic groups (Theorems 3.24 and 3.43); the quotient of an abelian group by a subgroup; and the basic theory of homomorphisms and isomorphisms. 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. Key agreement over a public channel needs this structure: associativity makes repeated combination of a public element with itself independent of bracketing, and identity and inverses make repetition counts obey an arithmetic.

3.1 The group axioms

Definition 3.1 (Binary operation).

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

∗:S×S→S,(a,b)↦a∗b.

Closure, the property that a∗b lies in S, is part of the statement that ∗ maps into S. It is named separately because ∗ restricts to a binary operation on a subset H⊆S exactly when H is closed under ∗, the condition on which subgroups (§3.4) rest.

Definition 3.2 (Group).

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

  1. (G1)

    Associativity. For all a,b,c∈G, (a∗b)∗c=a∗(b∗c).

  2. (G2)

    Identity. There exists e∈G such that e∗a=a∗e=a for all a∈G.

  3. (G3)

    Inverses. For each a∈G there exists b∈G such that a∗b=b∗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 |G|, is the order of the group; if |G| is finite, G is a finite group, and otherwise an infinite group. When the operation is understood, one writes “the group G”.

The axioms assert only the existence of an identity and of inverses; their uniqueness, proved next, justifies the notations e and a−1.

Proposition 3.3.

Let (G,∗) be a group.

  1. 1.

    The identity element is unique.

  2. 2.

    Each a∈G has a unique inverse, denoted a−1.

  3. 3.

    (Cancellation.) For all a,x,y∈G: if a∗x=a∗y then x=y, and if x∗a=y∗a then x=y.

  4. 4.

    For all a,b∈G, (a−1)−1=a and (a∗b)−1=b−1∗a−1.

Proof.

(1) Suppose e and e′ both satisfy (G2). Using that e′ is an identity, e=e∗e′; using that e is an identity, e∗e′=e′. Hence e=e′.

(2) Suppose b and b′ are both inverses of a. Then

b=b∗e=b∗(a∗b′)=(b∗a)∗b′=e∗b′=b′,

using (G2), the inverse property of b′, associativity, and the inverse property of b.

(3) Suppose a∗x=a∗y. Multiplying on the left by a−1 and reassociating,

x=(a−1∗a)∗x=a−1∗(a∗x)=a−1∗(a∗y)=(a−1∗a)∗y=y.

The right-cancellation law is proved symmetrically, multiplying on the right by a−1.

(4) Since a∗a−1=a−1∗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∗b)∗(b−1∗a−1)=a∗(b∗b−1)∗a−1=a∗a−1=e,

and symmetrically (b−1∗a−1)∗(a∗b)=e; by (2), (a∗b)−1=b−1∗a−1. The reversal of order is known as the “socks–shoes” rule. □

Two notational conventions are standard. Multiplicative notation writes the operation as juxtaposition ab (or a⋅b), the identity as 1, the inverse as a−1, and powers as an=a⁢⋯⁢a⏟n⁢factors for n≥1, with a0=1 and a−n=(a−1)n. Additive notation, reserved almost exclusively for commutative groups because the symbol + connotes commutativity, writes a+b, the identity as 0, the inverse as −a, and na for the n-fold sum. The exponent laws

am⁢an=am+n,(am)n=am⁢n

hold for all integers m,n, proved by induction together with Proposition 3.3. Henceforth ab denotes a∗b, and the symbol ∗ is omitted unless needed for clarity.

The power notation presupposes that an n-fold product does not depend on its bracketing, whereas axiom (G1) concerns only three factors. The next proposition proves this; thereafter products and powers are written without brackets.

Proposition 3.4 (Generalised associativity).

Let a1,…,an, n≥1, be elements of a group—or of any set with an associative operation. Every way of bracketing the product a1a2⋯an yields the same element, namely the left-normed product Ln=(⋯((a1a2)a3)⋯)an. In particular an is a single well-defined element, however the n factors are combined.

Proof.

By strong induction on n. For n≤2 there is only one bracketing, and for n=3 the two bracketings agree by (G1). Let n≥3 and assume the claim for all shorter products. Any bracketed product P of a1,…,an has an outermost multiplication, splitting it as P=QR with Q a bracketed product of a1,…,ak and R one of ak+1,…,an, for some 1≤k<n. The induction hypothesis evaluates both halves: Q=Lk, and R is the left-normed product of ak+1,…,an. If k=n−1, then R=an and P=Ln−1an=Ln directly. If k<n−1, write R=R′an with R′ the left-normed product of ak+1,…,an−1; then (G1) and the induction hypothesis, applied to the bracketed product LkR′ of the n−1 elements a1,…,an−1, give

P=Lk⁢(R′⁢an)=(Lk⁢R′)⁢an=Ln−1⁢an=Ln.

Every bracketing therefore equals Ln. □

Definition 3.5 (Abelian group).

A group (G,∗) is abelian (or commutative) if a∗b=b∗a for all a,b∈G; otherwise it is non-abelian.

The term honours Niels Henrik Abel. In an abelian group the factors of a product may be reordered arbitrarily, and the socks–shoes formula becomes (a⁢b)−1=b−1a−1=a−1b−1.

3.2 First examples

Example 3.6.

The pair (ℤ,+) is an infinite abelian group: addition is associative and commutative, the identity is 0, and the inverse of n is −n. Likewise (ℚ,+), (ℝ,+), and (ℂ,+) are abelian groups. By contrast (ℤ,⋅) is not a group: the integer 2 has no multiplicative inverse in ℤ.

Example 3.7.

The nonzero rationals ℚ×=ℚ∖{0} form an abelian group under multiplication, with identity 1 and inverse 1/a; likewise ℝ× and ℂ×. Zero must be excluded because it has no multiplicative inverse. More generally, for any field F (for example ℚ, ℝ, ℂ; the abstract notion is defined in 4) the nonzero elements F×=F∖{0} form an abelian group under multiplication. This property is part of the definition of a field.

Most finite examples below are built from congruence classes. On the set ℤ/nℤ of residue classes [a]n of 2, define operations through representatives,

[a]n+[b]n=[a+b]n,[a]n⁢[b]n=[a⁢b]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 ℤ/nℤ a commutative ring, is Theorem 4.6 in 4; the present section uses only the laws listed above.) Under addition, all of ℤ/nℤ is a group, as Example 3.9 below records. For n>1, multiplication does not make it a group, since [0]n has no inverse; 2 identified the invertible classes as 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 (ℤ/n⁢ℤ)× of units of ℤ/nℤ is an abelian group. Its order is |(ℤ/n⁢ℤ)×|=φ(n), Euler’s totient of Definition 2.26: the number of integers a with 1≤a≤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 [a⁢b]n has inverse [b]n−1[a]n−1, since (ab)(b−1a−1)≡1(modn) 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 (ℤ/n⁢ℤ)× is an abelian group. By Theorem 2.24 its elements are exactly the classes [a]n with gcd(a,n)=1 and 1≤a≤n, of which there are φ(n) by Definition 2.26. □

Example 3.9.

The pair (ℤ/nℤ,+) 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 (ℤ/n⁢ℤ)× of order φ(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 (ℤ/p⁢ℤ)× has order p−1—this is Example 3.7 specialised to ℤ/pℤ, which 4 shows to be a field and denotes 𝔽p.

Example 3.10.

The one-element set {e}, with its only possible operation e∗e=e, is the trivial group. The group ℤ/2ℤ={0,1} is the smallest nontrivial group. A further example of small order 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.

The groups V and ℤ/4ℤ both have order 4 but are not isomorphic, that is, structurally different (§3.8): in V every element combined with itself gives the identity, so V has no element of order 4 in the sense defined next, whereas in ℤ/4ℤ the class 1 must be added to itself four times to give 0.

3.3 The order of an element

Definition 3.11 (Order of an element).

Let G be a group and a∈G. The order of a, written ord(a), is the least positive integer n with an=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 ord(a)=∞.

The order ord(a) of an element shares its name with the order |G| of a group because it equals the order of the smallest subgroup of G containing a (Proposition 3.21).

Proposition 3.12.

Let a have finite order d=ord(a), and let m,k∈ℤ.

  1. 1.

    am=e if and only if d∣m.

  2. 2.

    am=ak if and only if m≡k(modd).

  3. 3.

    The distinct powers of a are exactly e=a0,a1,…,ad−1.

Proof.

(1) If d∣m, write m=dq; then am=(ad)q=eq=e. Conversely, suppose am=e and divide with remainder (Theorem 2.4): m=dq+r with 0≤r<d. Then

e=am=(ad)q⁢ar=ar,

so r is a nonnegative integer smaller than d with ar=e. Minimality of d among positive exponents forces r=0, whence d∣m.

(2) We have am=ak if and only if am−k=e (multiply by a−k and use the exponent laws), which by (1) holds if and only if d∣(m−k), i.e. m≡k(modd) (Definition 2.20).

(3) By (2) the powers a0,a1,…,ad−1 are pairwise distinct, their exponents being pairwise incongruent modulo d; and every power am equals ammodd, again by (2). □

The final step of part (1) is the division-minimality argument: to show that every witness of some property is a multiple of the least positive witness m, divide an arbitrary witness t=mq+r with 0≤r<m, show that r is itself a witness, and conclude r=0 by minimality. It has the form of the proof of Bézout’s identity (Theorem 2.11), carried over to a group, and recurs for the least positive power of g lying in a subgroup (Theorem 3.24) and for the least positive element of a subgroup of ℤ (Proposition 3.26).

Example 3.13.

In (ℤ/nℤ,+), with the powers of Definition 3.11 read additively, the k-fold sum of the class 1 is the class k, which is 0 exactly when n∣k, so ord(1)=n. More generally ord(a)=n/gcd(a,n) for any class a, by Corollary 3.23 below read additively. In ℂ× the element i has order 4: its successive powers are

i1=i,i2=−1,i3=−i,i4=1.

In (ℤ,+) 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⊆G of a group (G,∗) is a subgroup, written H≤G, if H is itself a group under the restriction of ∗ to H×H: explicitly, H is nonempty, closed under ∗, 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.

The definition is unambiguous. The identity of a subgroup coincides with the identity of G: if eH∈H satisfies eH∗eH=eH, then cancelling eH in G against eH∗e=eH (Proposition 3.3(3)) gives eH=e. Inverses computed in H agree with those computed in G, by uniqueness of inverses in G.

Since a subset inherits associativity from G, a single condition suffices.

Proposition 3.15 (One-step subgroup test).

Let G be a group and H⊆G. Then H≤G if and only if

  1. 1.

    H is nonempty, and

  2. 2.

    for all a,b∈H, the element ab−1 lies in H.

Proof.

If H≤G, then H is nonempty and, for a,b∈H, it contains b−1 and hence ab−1; both conditions hold.

Conversely, suppose (1) and (2) hold. Pick a∈H by (1); taking b=a in (2) gives e=aa−1∈H. For any b∈H, taking the pair (e,b) in (2) gives b−1=eb−1∈H, so H is closed under inverses. Finally, for a,b∈H the previous step gives b−1∈H, and applying (2) to the pair (a,b−1) gives a(b−1)−1=ab∈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≤G. Given a∈H, closure puts all the powers a,a2,a3,… in H; since H is finite they cannot all be distinct, so ai=aj for some i<j, giving aj−i=e∈H. Then a−1=aj−i−1∈H: this is a positive power of a when j−i≥2, and when j−i=1 we have a=e, whose inverse e already lies in H.

Example 3.17.

The even integers 2ℤ={2k:k∈ℤ} form a subgroup of (ℤ,+): the set is nonempty, and 2k−2l=2(k−l) is again even (the subgroup test, written additively). More generally nℤ={nk:k∈ℤ}≤ℤ for every n≥0, by the same computation—and these are all the subgroups of ℤ, as Proposition 3.26 will show.

Proposition 3.18.

The intersection ⋂i∈IHi of any family of subgroups Hi≤G is a subgroup of G.

Proof.

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

Definition 3.19 (Generated subgroup).

For a subset S⊆G, the subgroup generated by S, written ⟨S⟩, 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, ⟨S⟩ consists of all finite products s1ε1s2ε2⋯skεk with si∈S and εi∈{+1,−1}, the empty product being e. 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∈G with

G=⟨g⟩={gk:k∈ℤ};

such an element g is a generator of G.

The displayed equality agrees with Definition 3.19: the set {gk:k∈ℤ} contains g and is closed under products and inverses by the exponent laws, so it is a subgroup containing g; conversely, any subgroup containing g contains all its powers. Every cyclic group is abelian, since gmgn=gm+n=gngm.

Proposition 3.21.

Let G=⟨g⟩ be cyclic.

  1. 1.

    If g has infinite order, the powers gk (k∈ℤ) are pairwise distinct, so G is infinite.

  2. 2.

    If g has finite order d, then G={e,g,g2,…,gd−1} has exactly d elements.

In both cases |⟨g⟩|=ord(g).

Proof.

(1) Suppose gi=gj with i≠j; without loss of generality i>j. Then gi−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 g0,g1,…,gd−1, and these exhaust G={gk:k∈ℤ}. □

Example 3.22.

The group (ℤ,+) is infinite cyclic, generated by 1 and also by −1. The group (ℤ/nℤ,+) is cyclic of order n, generated by 1 (Example 3.13). The unit group (ℤ/8⁢ℤ)×={1,3,5,7} is not cyclic: each of its four elements squares to 1 (32=9≡1, 52=25≡1, 72=49≡1(mod8)), so no element has order 4. By contrast (ℤ/5⁢ℤ)×={1,2,3,4} is cyclic, generated by 2: its powers run

21≡2,22≡4,23≡3,24≡1(mod5),

exhausting the group.

Corollary 3.23.

Let g have finite order n and let k∈ℤ. Then

ord⁡(gk)=ngcd⁡(n,k).

In particular gk generates ⟨g⟩ if and only if gcd(n,k)=1, so a cyclic group of order n has exactly φ(n) generators.

Proof.

Set d=gcd(n,k) and write k=dk′, n=dn′ with gcd(n′,k′)=1. For m≥1,

(gk)m=gk⁢m=e⇔n∣k⁢m⇔d⁢n′∣d⁢k′⁢m⇔n′∣k′⁢m⇔n′∣m,

using Proposition 3.12(1) for the first equivalence and Euclid’s lemma (Proposition 2.15(1), with gcd(n′,k′)=1) for the last. The least positive such m is n′=n/d, which is therefore ord(gk).

For the second claim, ⟨gk⟩⊆⟨g⟩ always, and by Proposition 3.21 the subgroup ⟨gk⟩ has ord(gk)=n/gcd(n,k) elements; it equals the n-element set ⟨g⟩ exactly when gcd(n,k)=1. Since the powers g1,g2,…,gn run through each element of ⟨g⟩ exactly once (Proposition 3.12(3)), the generators correspond to the k∈{1,…,n} with gcd(n,k)=1, of which there are φ(n) by Definition 2.26. □

Theorem 3.24 (Subgroups of cyclic groups).

Let G=⟨g⟩ be a cyclic group.

  1. 1.

    Every subgroup of G is cyclic.

  2. 2.

    If G is infinite, its subgroups are exactly ⟨gm⟩ for m≥0; distinct m≥0 give distinct subgroups, and for m≥1 the subgroup ⟨gm⟩ is isomorphic to (ℤ,+).

  3. 3.

    If |G|=n, then for each positive divisor d∣n there is exactly one subgroup of G of order d, namely ⟨gn/d⟩, and these are all the subgroups of G. Subgroups of G thus correspond bijectively to positive divisors of n.

Proof.

(1) Let H≤G. If H={e}, then H=⟨e⟩ is cyclic. Otherwise H contains some gt≠e, so t≠0; since H also contains (gt)−1=g−t, it contains a power of g with positive exponent. Let m be the least positive integer with gm∈H (well-ordering, Theorem 2.1). We claim H=⟨gm⟩. The inclusion ⊇ holds by closure. For ⊆, take any element of H; it is some gt, since H⊆G=⟨g⟩. Divide t=mq+r with 0≤r<m; then

gr=gt−m⁢q=gt⁢(gm)−q∈H,

and minimality of m forces r=0, by the division-minimality argument. Hence gt=(gm)q∈⟨gm⟩.

(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}=⟨g0⟩ or ⟨gm⟩ with m≥1 least positive, and conversely each ⟨gm⟩ is a subgroup. For distinctness, observe that for m≥1 the positive exponents t with gt∈⟨gm⟩ are exactly the positive multiples of m: the elements of ⟨gm⟩ are the powers gm⁢k, and gt=gm⁢k forces t=mk because distinct exponents give distinct powers (Proposition 3.21(1)). The least such exponent recovers m, so distinct m≥1 give distinct subgroups, and each differs from {e} because gm≠e. Finally, for m≥1 the element gm has infinite order (if (gm)t=gm⁢t=e then mt=0, so t=0), so ⟨gm⟩ is an infinite cyclic group and is therefore isomorphic to (ℤ,+) by Theorem 3.43(1) below. No circularity arises: the proof of that theorem uses only Propositions 3.12 and 3.21.

(3) Let |G|=n, so ord(g)=n by Proposition 3.21.

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

ord⁡(gn/d)=ngcd⁡(n,n/d)=nn/d=d,

and ⟨gn/d⟩ is a subgroup of order d by Proposition 3.21.

Uniqueness. Let H≤G with |H|=d. If d=1 then H={e}=⟨gn⟩=⟨gn/1⟩, since gn=e. Otherwise, as in part (1), H=⟨gm⟩ for the least positive m with gm∈H, and Propositions 3.12 and 3.21 together with Corollary 3.23 give

d=|H|=ord⁡(gm)=ngcd⁡(n,m),sogcd⁡(n,m)=nd.

In particular n/d divides m, say m=(n/d)m′; then gm=(gn/d)m′, so H=⟨gm⟩⊆⟨gn/d⟩. Both sides have exactly d elements, so H=⟨gn/d⟩.

All subgroups arise. Any H≤G equals some ⟨gm⟩ (or {e}), whose order n/gcd(n,m) is a positive divisor d of n; by uniqueness H=⟨gn/d⟩. The assignment d↦⟨gn/d⟩ 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=ℤ/nℤ with generator 1 (written additively), Theorem 3.24(3) reads: for each divisor d∣n there is exactly one subgroup of order d, namely

⟨n/d⟩={ 0,n/d, 2⁢n/d,…,(d−1)⁢n/d},

itself cyclic of order d, hence isomorphic to ℤ/dℤ 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 ℤ/12ℤ is the divisor lattice of 12, with chains such as 1∣2∣4, 1∣2∣6, and 3∣6. 1 draws this lattice.

Refer to caption
Figure 1: The subgroup lattice of ℤ/12ℤ. By Theorem 3.24(3) there is one subgroup ⟨12/d⟩ for each divisor d of 12, of order d. An edge joins two subgroups when the lower is contained in the upper with no subgroup between them, which happens exactly when the quotient of their orders is prime: blue edges double the order, orange edges triple it. Inclusion of subgroups matches divisibility of their orders, so the diagram is also the divisor lattice of 12.

The classification of the subgroups of ℤ announced in Example 3.17 is Theorem 3.24(2) read additively for G=(ℤ,+)=⟨1⟩; a direct proof follows.

Proposition 3.26.

Every subgroup of (ℤ,+) has the form nℤ for a unique integer n≥0.

Proof.

Let H≤ℤ. If H={0}, then H=0ℤ. 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ℤ⊆H. Conversely, for any h∈H, divide h=nq+r with 0≤r<n; then r=h−nq∈H, and minimality of n forces r=0, so h∈nℤ. Hence H=nℤ. For uniqueness, the integer n is recovered from H as its least positive element (and n=0 exactly for H={0}), so distinct n≥0 give distinct subgroups. □

3.6 Cosets and Lagrange’s theorem

The cosets of a subgroup H≤G, defined next, partition G into blocks of size |H|; counting the blocks gives Lagrange’s theorem.

Definition 3.27 (Cosets and index).

Let H≤G and a∈G. The left coset of H by a is

a⁢H={a⁢h:h∈H},

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

Lemma 3.28 (Cosets partition the group).

Let H≤G.

  1. 1.

    Each a∈G lies in aH; the left cosets cover G.

  2. 2.

    Two left cosets are either equal or disjoint: aH=bH if and only if a−1b∈H, and otherwise aH∩bH=∅.

  3. 3.

    Every left coset has the same cardinality as H: the map h↦ah is a bijection from H onto aH.

The same statements hold for right cosets, with ba−1∈H as the criterion in (2).

Proof.

(1) Since e∈H, we have a=ae∈aH.

(2) First suppose the cosets meet: ah1=bh2 for some h1,h2∈H. Then a−1b=h1h2−1∈H. Conversely, suppose a−1b=h∈H, so b=ah. Then every element bh′∈bH equals a(hh′)∈aH, giving bH⊆aH; and since b−1a=h−1∈H, the same argument with the roles of a and b exchanged gives aH⊆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 λa:H→aH, h↦ah, is surjective by the definition of aH and injective by left cancellation (Proposition 3.3(3)): ah=ah′ implies h=h′. Hence |aH|=|H|.

For right cosets, the same three arguments apply with sides exchanged; in (2) the criterion becomes ba−1∈H. □

Theorem 3.29 (Lagrange’s theorem).

Let G be a finite group and H≤G. Then |H| divides |G|, and

|G|=[G:H]|H|.
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 |H| elements by part (3). Summing the sizes of the blocks of the partition,

|G|=∑distinct cosets ⁢a⁢H|aH|=k|H|=[G:H]|H|.∎
Corollary 3.30.

In a finite group G, the order of every element divides |G|.

Proof.

For a∈G, the cyclic subgroup ⟨a⟩ has order ord(a) by Proposition 3.21 (the order is finite, since ⟨a⟩⊆G is finite), and Theorem 3.29 makes |⟨a⟩| a divisor of |G|. □

Corollary 3.31.

If G is a finite group of order N, then aN=e for every a∈G.

Proof.

Let d=ord(a). By Corollary 3.30, d∣N, say N=dm; then aN=(ad)m=em=e. □

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

Let n≥1 and a∈ℤ with gcd(a,n)=1. Then

aφ⁢(n)≡1(modn).

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

ap−1≡1(modp),

and ap≡a(modp) holds for all integers a.

Proof.

Apply Corollary 3.31 to the group (ℤ/n⁢ℤ)×, which has order φ(n) (Proposition 3.8). For gcd(a,n)=1 the class [a]n is a unit (Theorem 2.24), so [a]nφ⁢(n)=[1]n, which is the first congruence. For n=p prime, φ(p)=p−1 (Example 2.27), and p∤a gives gcd(a,p)=1, yielding the second congruence. Multiplying it by a gives ap≡a(modp); and when p∣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 only here; 7 restates them under the heading Fermat’s little theorem and Euler’s theorem, cites this proof, and develops their cryptographic role.

Corollary 3.34.

Every group G of prime order p is cyclic, hence isomorphic to ℤ/pℤ, and has no proper nontrivial subgroups.

Proof.

Pick a∈G with a≠e (possible since p≥2). The subgroup ⟨a⟩ has at least two elements, and by Theorem 3.29 its order divides p; a divisor of p exceeding 1 equals p, so ⟨a⟩=G and G is cyclic. The isomorphism with ℤ/pℤ 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

The quotient of an abelian group by a subgroup underlies the quotient rings of 4 and, through them, ℤ/nℤ and the polynomial quotients used throughout the series.

Proposition 3.35 (Quotient of an abelian group).

Let A be an abelian group, written additively, and let H≤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

|A/H|=[A:H]=|A||H|.
Proof.

The substantive claim is that the operation is well defined: its output is stated in terms of chosen representatives a and b, and replacing them by other representatives of the same cosets must leave the result unchanged. Suppose then that a+H=a′+H and b+H=b′+H. By Lemma 3.28(2), written additively, this means a′−a∈H and b′−b∈H. Then

(a′+b′)−(a+b)=(a′−a)+(b′−b)∈H,

since H is closed under addition; applying Lemma 3.28(2) once more, (a′+b′)+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 then pass coset-wise from A: for associativity,

((a+H)+(b+H))+(c+H) =((a+b)+c)+H=(a+(b+c))+H
=(a+H)+((b+H)+(c+H));

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]=|A|/|H| by Theorem 3.29—the same partition-into-equal-blocks count as before. □

For A=(ℤ,+) and H=nℤ, the cosets are the residue classes [a]n=a+nℤ of Definition 2.22 and coset addition is addition of classes. The notation ℤ/nℤ, introduced in 2 as a name for the set of classes, is thus an instance of the quotient notation A/H, and (ℤ/nℤ,+) is the quotient group of ℤ by nℤ.

Remark 3.36.

For a non-abelian group G the same construction succeeds exactly for those subgroups N≤G whose left and right cosets coincide, gN=Ng for all g∈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 needs only the abelian case and does 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,∗) and (G′,∘) be groups. A function ϕ:G→G′ is a group homomorphism if

ϕ⁢(a∗b)=ϕ⁢(a)∘ϕ⁢(b)for all ⁢a,b∈G.

The set of all homomorphisms from G to G′ is denoted Hom(G,G′).

Proposition 3.38.

Let ϕ:G→G′ be a homomorphism, and write e,e′ for the identities of G and G′.

  1. 1.

    ϕ(e)=e′.

  2. 2.

    ϕ(a−1)=ϕ(a)−1 for all a∈G.

  3. 3.

    ϕ(an)=ϕ(a)n for all a∈G and n∈ℤ.

  4. 4.

    The image ϕ(G) is a subgroup of G′.

Proof.

(1) From e=e∗e we get ϕ(e)=ϕ(e)∘ϕ(e); cancelling ϕ(e) in G′ (Proposition 3.3(3)) gives e′=ϕ(e).

(2) Applying ϕ to a∗a−1=e=a−1∗a and using (1),

ϕ⁢(a)∘ϕ⁢(a−1)=e′=ϕ⁢(a−1)∘ϕ⁢(a),

so ϕ(a−1) is an inverse of ϕ(a); by uniqueness of inverses, ϕ(a−1)=ϕ(a)−1.

(3) For n≥0, induct: the case n=0 is (1), and ϕ(an+1)=ϕ(an∗a)=ϕ(a)n∘ϕ(a)=ϕ(a)n+1. For n<0, write n=−m with m>0 and combine with (2): ϕ(a−m)=ϕ((a−1)m)=ϕ(a−1)m=(ϕ⁢(a)−1)m=ϕ(a)−m.

(4) The image is nonempty, containing e′=ϕ(e). For x=ϕ(a) and y=ϕ(b) in ϕ(G),

x∘y−1=ϕ⁢(a)∘ϕ⁢(b)−1=ϕ⁢(a∗b−1)∈ϕ⁢(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 ϕ:G→G′ are

ker⁡(ϕ)={a∈G:ϕ⁢(a)=e′}=ϕ−1⁢({e′}),im⁡(ϕ)=ϕ⁢(G)={ϕ⁢(a):a∈G}.
Proposition 3.40.

For any homomorphism ϕ:G→G′, the kernel is a subgroup, ker(ϕ)≤G, and ϕ is injective if and only if ker(ϕ)={e}.

Proof.

The kernel contains e by Proposition 3.38(1), so it is nonempty; and for a,b∈ker(ϕ),

ϕ⁢(a⁢b−1)=ϕ⁢(a)∘ϕ⁢(b)−1=e′∘(e′)−1=e′,

so ab−1∈ker(ϕ); the one-step test gives ker(ϕ)≤G.

If ϕ is injective and ϕ(a)=e′=ϕ(e), then a=e; the kernel is trivial. Conversely, suppose ker(ϕ)={e} and ϕ(a)=ϕ(b). Then ϕ(ab−1)=ϕ(a)∘ϕ(b)−1=e′, so ab−1∈ker(ϕ)={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(ϕ) directly, and in general the kernel satisfies the normality condition of Remark 3.36—for n∈ker(ϕ) and g∈G, one computes ϕ(gng−1)=ϕ(g)∘e′∘ϕ(g)−1=e′, so conjugating the kernel by g lands back in the kernel, whence gker(ϕ)=ker(ϕ)g.

Definition 3.41 (Isomorphism).

An isomorphism is a bijective homomorphism ϕ:G→G′; when one exists, the groups are isomorphic, written G≅G′. 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 ≅ is an equivalence relation on any collection of groups.

Proof.

Let ϕ:G→G′ be an isomorphism, with inverse function ϕ−1 (which exists since ϕ is a bijection, Theorem 1.1). For x,y∈G′, write x=ϕ(a) and y=ϕ(b); then

ϕ−1⁢(x∘y)=ϕ−1⁢(ϕ⁢(a∗b))=a∗b=ϕ−1⁢(x)∗ϕ−1⁢(y),

so ϕ−1 is a homomorphism, and it is a bijection; hence an isomorphism. For the equivalence relation: reflexivity is witnessed by the identity automorphism idG; 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. □

Any property expressible through the operation alone, such as the orders of elements, the lattice of subgroups, or commutativity, transfers across an isomorphism, so groups are classified up to isomorphism; the next theorem does so for cyclic groups.

Theorem 3.43 (Classification of cyclic groups).

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

  1. 1.

    the infinite cyclic group (ℤ,+), if it is infinite;

  2. 2.

    the finite cyclic group (ℤ/nℤ,+), if it has order n.

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

Proof.

Let G=⟨g⟩ and define

ϕ:ℤ→G,ϕ⁢(k)=gk.

The exponent law gk+l=gkgl says exactly that ϕ is a homomorphism from (ℤ,+) to G, and ϕ 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 ϕ is injective, hence a bijective homomorphism, and ℤ≅G.

Case 2: ord(g)=n. By Proposition 3.12(1),

ker⁡(ϕ)={k∈ℤ:gk=e}=n⁢ℤ.

Define the induced map

ϕ¯:ℤ/n⁢ℤ→G,ϕ¯⁢([k]n)=gk.

It is well defined: if [k]n=[l]n then n∣(k−l), so gk=gl by Proposition 3.12(2). It is a homomorphism: ϕ¯([k]n+[l]n)=ϕ¯([k+l]n)=gk+l=ϕ¯([k]n)ϕ¯([l]n). It is surjective because ϕ is. And it is injective by Proposition 3.40: if ϕ¯([k]n)=gk=e, then n∣k (Proposition 3.12(1)), so [k]n=[0]n; the kernel of ϕ¯ is trivial. Hence ℤ/nℤ≅G.

Distinctness. Isomorphic groups have equal order, an isomorphism being in particular a bijection. The group ℤ is infinite and the groups ℤ/nℤ for n=1,2,3,… 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. □

In key agreement over a public channel, two parties fix a finite group G and a public element g∈G, of order n=ord(g); each combines g with itself a secret number of times, a and b respectively, publishes the result, and applies its own count to the other’s. By generalised associativity (Proposition 3.4), a repetitions of g give the element ga however bracketed, and the exponent laws give

(ga)b=ga⁢b=(gb)a,

so the two parties obtain a common secret element, while an eavesdropper sees only g and the two published values. By the classification of cyclic groups, ⟨g⟩ is isomorphic to ℤ/nℤ, so exponents add, negate, and matter only modulo n (Proposition 3.12), in the modular arithmetic of 2. By Lagrange’s theorem, n divides |G|. That publishing ga hides a is not a theorem of algebra but a statement about computation: it fails in some groups, such as (ℤ/nℤ,+), where recovering a from ag is a single modular division, and appears to hold in others. The sections that follow and later volumes make this hiding property precise and construct the groups for which it is credible.