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 be a set. A binary operation on is a function
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 , written , is the order of the group; if is finite, is a finite group, and otherwise an infinite group. When the operation is understood, one writes “the group ”.
The axioms assert only the existence of an identity and of inverses; their uniqueness, proved next, justifies the notations and .
Let
The identity element is unique.
Each
(Cancellation.) For all
For all
(1) Suppose and both satisfy (G2). Using that is an
identity,
(2) Suppose and are both inverses of . Then
using (G2), the inverse property of , associativity, and the inverse property of .
(3) Suppose
The right-cancellation law is proved symmetrically, multiplying on the right by .
(4) Since
and symmetrically
Two notational conventions are standard. Multiplicative notation writes
the operation as juxtaposition (or
hold for all integers
The power notation presupposes that an -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 . For
Every bracketing therefore equals . □
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 of residue classes of 2, define operations through representatives,
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 and , negatives—passes to classes by
computing on representatives. (The full structural statement, that these
operations make a commutative ring, is
Theorem 4.6 in 4; the present
section uses only the laws listed above.) Under addition, all of
is a group, as Example 3.9 below records.
For
Under multiplication of classes, the set of units of
is an abelian group. Its order is
Multiplication of classes is associative and commutative with identity
, as derived above from
Proposition 2.21 by computing on
representatives, and
is a unit (it is its own inverse). The operation is closed on
units: if and are units with inverses
and , then has inverse ,
since
The pair
The one-element set , with its only possible operation
The groups and both have order but are not isomorphic, that is, structurally different (§3.8): in every element combined with itself gives the identity, so has no element of order in the sense defined next, whereas in the class must be added to itself four times to give .
Let be a group and
The order of an element shares its name with the order of a group because it equals the order of the smallest subgroup of containing (Proposition 3.21).
Let have finite order
The distinct powers of are exactly
(1) If
so is a nonnegative integer smaller than 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 , divide an arbitrary witness
In
In
A subset
The definition is unambiguous. The identity of a subgroup coincides with
the identity of : if
Since a subset inherits associativity from , a single condition suffices.
Let be a group and
is nonempty, and
for all
If
Conversely, suppose (1) and (2) hold. Pick
For a finite nonempty subset , closure under the operation
alone forces
The even integers
The intersection of any family of subgroups
The identity lies in every , so the intersection is
nonempty. If and lie in the intersection, then for each
both lie in , so
For a subset
Concretely, consists of all finite products
with
A group is cyclic if there exists
such an element is a generator of .
The displayed equality agrees with
Definition 3.19: the set
Let
If has infinite order, the powers
If has finite order , then
In both cases
(1) Suppose
(2) This is Proposition 3.12(3): the distinct
powers of are exactly
The group
exhausting the group.
Let have finite order and let
In particular generates if and only if
Let
Every subgroup of is cyclic.
If is infinite, its subgroups are exactly
for
If
(1) Let
and minimality of forces
(2) Let be infinite. Then has infinite order, for otherwise
would be finite by
Proposition 3.21(2). By part (1) every
subgroup is
(3) Let
Existence. Let
and is a subgroup of order by Proposition 3.21.
Uniqueness. Let
In particular divides , say
All subgroups arise. Any
Specialised to
itself cyclic of order , hence isomorphic to by the
classification below. For
The classification of the subgroups of announced in
Example 3.17 is
Theorem 3.24(2) read additively for
Every subgroup of
Let
The cosets of a subgroup
Let
and the right coset is
Let
Each
Two left cosets are either equal or disjoint:
Every left coset has the same cardinality as : 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 be a finite group and
By Lemma 3.28, the distinct left cosets of
partition : they cover by part (1) and are pairwise
disjoint by part (2). Since is finite there are finitely many of
them, say
In a finite group , the order of every element divides .
If is a finite group of order , then
Let
Let
In particular, for a prime and not divisible by ,
and
Apply Corollary 3.31 to the group
, which has order
(Proposition 3.8). For
Every group of prime order is cyclic, hence isomorphic to , and has no proper nontrivial subgroups.
The quotient of an abelian group by a subgroup underlies the quotient rings of 4 and, through them, and the polynomial quotients used throughout the series.
Let be an abelian group, written additively, and let
on the coset set is well defined and makes an abelian
group—the quotient group of by —with identity
The substantive claim is that the operation is well defined: its output
is stated in terms of chosen representatives and , and
replacing them by other representatives of the same cosets must leave the
result unchanged. Suppose then that
since is closed under addition; applying
Lemma 3.28(2) once more,
The axioms then pass coset-wise from : for associativity,
commutativity follows the same way from commutativity in ; the
coset
For
For a non-abelian group the same construction succeeds exactly for
those subgroups
Groups are compared through the maps that respect their operations.
Let
The set of all homomorphisms from to is denoted .
Let
The image is a subgroup of .
(1) From
(2) Applying to
so is an inverse of ; by uniqueness of
inverses,
(3) For
(4) The image is nonempty, containing
using (2); the one-step subgroup test (Proposition 3.15) concludes. □
The kernel and image of a homomorphism
For any homomorphism
The kernel contains by
Proposition 3.38(1), so it is nonempty; and for
so
If is injective and
Kernels are exactly the subgroups by which one may quotient: for abelian
, Proposition 3.35 forms
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
so is a homomorphism, and it is a bijection; hence an isomorphism. For the equivalence relation: reflexivity is witnessed by the identity automorphism ; 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
The exponent law
Case 1: has infinite order. Distinct exponents give
distinct powers (Proposition 3.21(1)), so
is injective, hence a bijective homomorphism, and
Case 2:
Define the induced map
It is well defined: if
Distinctness. Isomorphic groups have equal order, an isomorphism
being in particular a bijection. The group is infinite and the
groups for
In key agreement over a public channel, two parties fix a finite group
and a public element
so the two parties obtain a common secret element, while an eavesdropper
sees only and the two published values. By the classification of cyclic
groups, is isomorphic to , so exponents add,
negate, and matter only modulo
(Proposition 3.12), in the modular arithmetic of
2. By Lagrange’s theorem, divides .
That publishing hides is not a theorem of algebra but a
statement about computation: it fails in some groups, such as