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.
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 group is a pair
Associativity. For all
Identity. There exists
Inverses. For each
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 .
Let
The identity element is unique.
Each
(Cancellation.) For all
For all
(1) Suppose e and e ′ both satisfy (G2). Using that e ′ is an
identity,
(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
| 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 ∗ b) ∗ (b − 1 ∗ a − 1) = a ∗ (b ∗ b − 1) ∗ a − 1 = a ∗ a − 1 = e, |
and symmetrically
Two notational conventions are standard. Multiplicative notation writes
the operation as juxtaposition a b (or
| a m a n = a m + n, (a m) n = a m n |
hold for all integers
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.
Let
By strong induction on n . For
| P = L k (R ′ a n) = (L k R ′) a n = L n − 1 a n = L n . |
Every bracketing therefore equals L n . □
A group
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
The pair
The nonzero rationals
Most finite examples below are built from congruence classes. On the set Z / n Z 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 Z / n Z a commutative ring, is
Theorem 4.6 in 4; the present
section uses only the laws listed above.) Under addition, all of
Z / n Z is a group, as Example 3.9 below records.
For
Under multiplication of classes, the set (Z / n Z) × of units of
Z / n Z is an abelian group. Its order is
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
The pair
The one-element set { e } , with its only possible operation
The groups V and Z / 4 Z 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 Z / 4 Z the class 1 must be added to itself four times to give 0 .
Let G be a group and
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).
Let a have finite order
The distinct powers of a are exactly
(1) If
| e = a m = (a d) q a r = a r, |
so r is a nonnegative integer smaller than d with
(2) We have
(3) By (2) the powers
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
In
| i 1 = i, i 2 = − 1, i 3 = − i, i 4 = 1 . |
In
A subset
The definition is unambiguous. The identity of a subgroup coincides with
the identity of G : if
Since a subset inherits associativity from G , a single condition suffices.
Let G be a group and
H is nonempty, and
for all
If
Conversely, suppose (1) and (2) hold. Pick
For a finite nonempty subset H , closure under the operation
alone forces
The even integers
The intersection ⋂ i ∈ I H i of any family of subgroups
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
For a subset
Concretely, ⟨ S ⟩ consists of all finite products
s 1 ε 1 s 2 ε 2 ⋯ s k ε k
with
A group G is cyclic if there exists
| G = ⟨ g ⟩ = { g k : k ∈ Z } ; |
such an element g is a generator of G .
The displayed equality agrees with
Definition 3.19: the set
Let
If g has infinite order, the powers g k
If g has finite order d , then
In both cases
(1) Suppose
(2) This is Proposition 3.12(3): the distinct
powers of g are exactly
The group
| 2 1 ≡ 2, 2 2 ≡ 4, 2 3 ≡ 3, 2 4 ≡ 1 (mod 5), |
exhausting the group.
Let g have finite order n and let
| ord (g k) = n gcd (n, k) . |
In particular g k generates ⟨ g ⟩ if and only if
Set
| (g k) m = g k 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
For the second claim,
Let
Every subgroup of G is cyclic.
If G is infinite, its subgroups are exactly
⟨ g m ⟩ for
If
(1) Let
| g r = g t − m q = g t (g m) − q ∈ H, |
and minimality of m forces
(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
(3) Let
Existence. Let
| ord (g n / d) = n gcd (n, n / d) = n n / d = d, |
and ⟨ g n / d ⟩ is a subgroup of order d by Proposition 3.21.
Uniqueness. Let
| d = | H | = ord (g m) = n gcd (n, m), so gcd (n, m) = n d . |
In particular n / d divides m , say
All subgroups arise. Any
Specialised to
| ⟨ n / d ⟩ = { 0, n / d, 2 n / d, ..., (d − 1) n / d }, |
itself cyclic of order d , hence isomorphic to Z / d Z by the
classification below. For
The classification of the subgroups of Z announced in
Example 3.17 is
Theorem 3.24(2) read additively for
Every subgroup of
Let
The cosets of a subgroup
Let
| a H = { a h : h ∈ H }, |
and the right coset is
Let
Each
Two left cosets are either equal or disjoint:
Every left coset has the same cardinality as H : the map
The same statements hold for right cosets, with
(1) Since
(2) First suppose the cosets meet:
(3) The map
For right cosets, the same three arguments apply with sides exchanged;
in (2) the criterion becomes
Let G be a finite group and
| | G | = [G : H] | H | . |
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 | = ∑ distinct cosets a H | a H | = k | H | = [G : H] | H | . ∎ |
In a finite group G , the order of every element divides | G | .
If G is a finite group of order N , then
Let
Let
| a φ (n) ≡ 1 (mod n) . |
In particular, for a prime p and a not divisible by p ,
| a p − 1 ≡ 1 (mod p), |
and
Apply Corollary 3.31 to the group
(Z / n Z) × , which has order φ (n)
(Proposition 3.8). For
Every group G of prime order p is cyclic, hence isomorphic to Z / p Z , and has no proper nontrivial subgroups.
Pick
The quotient of an abelian group by a subgroup underlies the quotient rings of 4 and, through them, Z / n Z and the polynomial quotients used throughout the series.
Let A be an abelian group, written additively, and let
| (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
| | A / H | = [A : H] = | A | | H | . |
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 ′ + b ′) − (a + b) = (a ′ − a) + (b ′ − b) ∈ H, |
since H is closed under addition; applying
Lemma 3.28(2) once more,
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
For
For a non-abelian group G the same construction succeeds exactly for
those subgroups
Groups are compared through the maps that respect their operations.
Let
| φ (a ∗ b) = φ (a) ∘ φ (b) for all a, b ∈ G . |
The set of all homomorphisms from G to G ′ is denoted Hom (G, G ′) .
Let
The image φ (G) is a subgroup of G ′ .
(1) From
(2) Applying φ to
| φ (a) ∘ φ (a − 1) = e ′ = φ (a − 1) ∘ φ (a), |
so φ (a − 1) is an inverse of φ (a) ; by uniqueness of
inverses,
(3) For
(4) The image is nonempty, containing
| x ∘ y − 1 = φ (a) ∘ φ (b) − 1 = φ (a ∗ b − 1) ∈ φ (G), |
using (2); the one-step subgroup test (Proposition 3.15) concludes. □
The kernel and image of a homomorphism
| ker (φ) = { a ∈ G : φ (a) = e ′ } = φ − 1 ({ e ′ }), im (φ) = φ (G) = { φ (a) : a ∈ G } . |
For any homomorphism
The kernel contains e by
Proposition 3.38(1), so it is nonempty; and for
| φ (a b − 1) = φ (a) ∘ φ (b) − 1 = e ′ ∘ (e ′) − 1 = e ′, |
so
If φ is injective and
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
An isomorphism is a bijective homomorphism
The set-theoretic inverse of an isomorphism is an isomorphism, and ≅ is an equivalence relation on any collection of groups.
Let
| φ − 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 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. □
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.
Every cyclic group is isomorphic to exactly one of the following:
the infinite cyclic group
the finite cyclic group
In particular, two cyclic groups are isomorphic if and only if they have the same order.
Let
| φ : Z → G, φ (k) = g k . |
The exponent law
Case 1: g has infinite order. Distinct exponents give
distinct powers (Proposition 3.21(1)), so
φ is injective, hence a bijective homomorphism, and
Case 2:
| ker (φ) = { k ∈ Z : g k = e } = n Z . |
Define the induced map
| φ ̄ : Z / n Z → G, φ ̄ ([k] n) = g k . |
It is well defined: if
Distinctness. Isomorphic groups have equal order, an isomorphism
being in particular a bijection. The group Z is infinite and the
groups Z / n Z for
In key agreement over a public channel, two parties fix a finite group
G and a public element
| (g a) b = g a b = (g b) 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 Z / n Z , 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 g a hides a is not a theorem of algebra but a
statement about computation: it fails in some groups, such as