Groups, Rings and Fields main definitions and results version 3

Robin Chapman

2 January 2003

This is a skeleton summary of the course notes. They are incomplete and in a rough state. I intend to extend them, so newer versions may appear, but I do not promise that they will. Corrections and comments are welcome, and will be acknowledged in future versions.

1 Groups

1.1 Basics

A group G is a set G together with an operation ∗, (that is, given a, b ∈ G there is an element a ∗ b ∈ G), satisfying the following conditions:

G1 (a ∗ b) ∗ c = a ∗ (b ∗ c) for all a, b, c ∈ G (associativity).

G2 There is e ∈ G with e ∗ a = a = a ∗ e for all a ∈ G (identity).

G3 For each a ∈ G there is some b ∈ G with a ∗ b = e = b ∗ a (inverses).

If G is a group with the property that

G4 a ∗ b = b ∗ a for all a, b ∈ G (commutativity),

then G is an abelian group.

In almost all cases, the group operation is written as addition or multiplication.

In additive notation the result of the group operation is written as a + b. Additive notation is only used for abelian groups. The identity element is denoted by 0, and the inverse of a is denoted by −a.

In multiplicative notation the result of the group operation is written as ab. The identity element is denoted by e (or 1 or I etc.), and the inverse of a is denoted by a^{−1}.

When talking about an arbitrary group, we shall normally employ multiplicative notation, but many specific examples will use additive notation.

1.2 Subgroups

A subgroup of a group G is a subset H of G which is also a group under the same operation. In detail, H is a subgroup of G if H is a subset of G and

SG1 ab ∈ H whenever a ∈ H and b ∈ H (closure).

SG2 If e denotes the identity element of G, then e ∈ H (identity).

SG3 For each a ∈ H then a^{−1} ∈ H where a^{−1} denotes the inverse of a in G (inverses).

We write H ≤ G as shorthand for “H is a subgroup of G”.

Let G be a multiplicative group. If a ∈ G we define a^{2} = aa, a^{3} = aa^{2} etc., a^{0} = e the identity, a^{−1} as the inverse of a, a^{−2} = a^{−1}a^{−1}, a^{−3} = a^{−1}a^{−2} etc. Thus a^{n} is the n-th power of a. Then a^{m}a^{n} = a^{m+n} and (a^{m})^{n} = a^{mn}.

For additive groups G the same concept requires a different notation: we define 2a = a + a, 3a = a + 2a etc., 0a = 0, (−1)a = −a, (−2)a = (−1)a + (−1)a, (−3)a = (−1)a + (−2)a, etc. We call the na the multiples of a. In this notation ma + na = (m + n)a and m(na) = (mn)a.

If a ∈ G the set of powers ⟨a⟩ = {…, a^{−2}, a^{−1}, e, a, a^{2}, a^{3}, …} is a subgroup of G. The subgroup ⟨a⟩ is the cyclic subgroup of G generated by a. (In additive groups ⟨a⟩ = {…, −2a, −a, 0, a, 2a, 3a, …}.)

The order of a group G is the number of elements it has, and is denoted by |G|. Thus |G| is a positive integer or ∞.

The order of an element a in a group G is the order of the subgroup ⟨a⟩ of G. It is denoted by o(a). In other words, o(a) is the number of distinct powers of a. Again o(a) is a positive integer or ∞.

Theorem 1 Let G be a group, and let a be an element of G such that o(a) = n is finite. Then n is the least positive integer with a^{n} = e and moreover

⟨a⟩ = {a, a^{2}, a^{3}, …, a^{n−1}, e}.

Proof As a has only n distinct powers, the sequence

a, a^{2}, a^{3}, …  (∗)

must contain two identical entries somewhere, that is a^{j} = a^{k} for some j and k with j < k. Hence a^{k−j} = e and so the sequence (∗) contains the identity somewhere. Let the first occurrence of the identity be in the m-th place, so that m is the least positive integer with a^{m} = e. We aim to show that m = n.

Now a^{m+1} = ea = a, a^{m+2} = ea^{2} = a^{2} and so after m terms, (∗) starts repeating itself:

a, a^{2}, …, a^{m−1}, e, a, a^{2}, …, a^{m−1}, e, a, a^{2}, ….

We can work backwards as well, a^{0} = e, a^{−1} = ea^{−1} = a^{m−1}, a^{−2} = ea^{−2} = a^{m−2} etc. In short, all powers of a lie in the set

⟨a⟩ = {a, a^{2}, a^{3}, …, a^{m−1}, e}

which must equal ⟨a⟩.

Now n is the number of elements in ⟨a⟩ so to show that m = n we need to show that there are no repeats in the finite sequence

a, a^{2}, a^{3}, …, a^{m−1}, a^{m} = e.

If there were, then a^{j} = a^{k} where 1 ≤ j < k ≤ m and so a^{k−j} = e. But 0 < k − j ≤ m − 1 and so a^{k−j} precedes a^{m} in (∗). But this is impossible as a^{m} is the first occurrence of e in (∗). We conclude that m must equal n. □

Theorem 2 Let G be a group, and let a be an element of G such that o(a) = ∞. Then all powers a^{j} of a are distinct, that is if j ≠ k then a^{j} ≠ a^{k}. In particular if n ≠ 0 then a^{n} ≠ e.

Proof Suppose that a^{j} = a^{k} where j < k. Then a^{k−j} = e, that is a^{r} = e where r = k − j > 0. It will suffice to show this is impossible. But this implies, by a similar argument to the previous proof, that

⟨a⟩ = {a, a^{2}, a^{3}, …, a^{r−1}, e}

and so o(a) is finite, contrary to the hypothesis. This contradiction completes the proof. □

1.3 Cyclic and dihedral groups

A cyclic group is a group G which is a cyclic subgroup of itself: G = ⟨a⟩ for some a ∈ G, that is, all the elements of G are powers of one fixed element.

Let a, b and m be integers with m > 0. We say that ‘a is congruent to b modulo m’ and write

a ≡ b (mod m)

if a − b is a multiple of m. It is easy to show that for each positive integer m, • a ≡ a (mod m) for all integers a,

• if a ≡ b (mod m) then b ≡ a (mod m) and

• if a ≡ b (mod m) and b ≡ c (mod m) then a ≡ c (mod m).

In short, congruence modulo m is an equivalence relation on Z.

In addition if a ≡ b (mod m) and c ≡ d (mod m) then

• a + c ≡ b + d (mod m),

• a − c ≡ b − d (mod m) and

• ac ≡ bd (mod m).

Given m > 0, each integer a is congruent modulo m to a unique element of {0, 1, 2, …, m−1}. If we let Z_{m} = {0, 1, 2, …, m−1}, then we can define an operation +_{m} on Z_{m} namely “addition modulo m” making Z_{m} into a group. In detail, a +_{m} b is the unique integer in Z_{m} congruent to a + b modulo m. With respect to this operation Z_{m} is a cyclic group having 1 as a generator. (Normally we are lazy and write + instead of +_{n}.)

Let n be a integer with n ≥ 3. The symmetry group of a regular polygon P with n sides is called the dihedral group D_{2n} and contains 2n elements: n rotations and n reflections. If we let R be the rotation about the centre through (360/n)^{∘} then the rotations in D_{n} are R^{j} for 0 ≤ j < n. If we let S be a fixed reflection in D_{n} then the reflections are R^{j}S for 0 ≤ j < n. The elements R and S obey the relations R^{n} = I, S^{2} = I and SRS = R^{−1} where I denotes the identity.

1.4 Cosets and Lagrange’s theorem

Let H be a subgroup of a group G. If a ∈ G the set

aH = {ah : h ∈ H}

is a left coset of H in G. As e ∈ H then a = ae ∈ aH. Similarly

Ha = {ha : h ∈ H}

is a right coset. (If G is an abelian additive group left/right cosets are written of course as a + H.) It is easy to see that |H| = |aH| since h ↦ ah is a bijection from H to aH with inverse k ↦ a^{−1}k.

Lemma 1 Let H be a subgroup of a group G, and let a, b ∈ G.

(i) If b ∈ aH then aH = bH, but

(ii) If b ∉ aH then aH ∩ bH = ∅.

Proof (i) Let b ∈ aH. Then there is h_{1} ∈ H with b = ah_{1}. Let x = bh_{2} with h_{2} ∈ H, be a typical element of bH. Then x = ah_{1}h_{2} ∈ aH (since as H is a subgroup of G and h_{1}, h_{2} ∈ H then h_{1}h_{2} ∈ H. Hence bH ⊆ aH. Now let y = ah_{3} be a typical element of aH. Then y = bh_{1}^{−1}h_{3} ∈ bH (since as H is a subgroup of G and h_{1}, h_{3} ∈ H then h_{1}^{−1} ∈ H and so h_{1}^{−1}h_{3} ∈ H. Hence aH ⊆ bH. We conclude that aH = bH. (ii) Suppose that b ∉ aH but that aH ∩ bH ≠ ∅. Then there exists c ∈ aH ∩ bH and so c ∈ aH and c ∈ bH. By part (i) cH = aH and cH = bH. Hence bH = aH and so b ∈ aH and we have a contradiction. □

Let H ≤ G. The number of left cosets of H in G is called the index of H in G and is denoted as |G : H|. If |G| is finite then |G : H| is finite, but if |G| is infinite, then |G : H| can be finite or infinite.

Theorem 3 (Lagrange) Let G be a finite group and H be a subgroup of G. Then |H| is a factor of |G|.

Proof Consider the left cosets of H in G. There are |G : H| of them, each having |H| elements. Each of the |G| elements of G lies in exactly one left coset of H in G and so

|G| = |G : H||H|.

Hence |G| is a multiple of |H|. □

Corollary 1 Let G be a finite group and let a ∈ G. Then a^{|G|} = e.

Proof Let H = ⟨a⟩. By Lagrange’s theorem, |G| = m|H| where m is an integer. But |H| = | ⟨a⟩ | = o(a) and so a^{|H|} = e. Hence

a^{|G|} = a^{m|H|} = (a^{|H|})^{m} = e^{m} = e.
□

1.5 Permutations

For each positive integer n let [n] denote the set {1, 2, …, n}. A permutation σ of [n] is a bijection σ : [n] → [n]. The symmetric group of degree n is the set of all permutations of [n] and is denoted by S_{n}. It is a group, with composition as operation: we define στ = σ ∘ τ. To check that it is a group, note that the composition of two bijections is a bijection, associativity holds in full generality for composition of functions: f ∘ (g ∘ h) = (f ∘ g) ∘ h, the identity function id : [n] → [n] (defined by id(j) = j) is bijective and satisfies id ∘σ = σ = σ ∘ id, and a bijection σ has an inverse σ^{−1} (so that σ^{−1}(k) = j whenever σ(j) = k) which is also a bijection, satisfying σ∘σ^{−1} = id = σ^{−1}∘σ.

The group S_{n} has order n!.

Let σ ∈ S_{n} and a ∈ [n]. If we consider the sequence a, σ(a), σ^{2}(a), … we find that it is periodic; eventually we find r with σ^{r}(a) = a. Let a_{1} = a, a_{2} = σ(a), …, a_{r} = σ^{r−1}(a). Then σ(a_{j}) = a_{j+1} if 1 ≤ j < r and σ(a_{r}) = a_{1}. We call the sequence a_{1}, a_{2}, …, a_{r} a cycle of σ, and we write it as (a_{1} a_{2} … a_{r}). Its length is r. If we start with some a_{j} instead of a_{1} we get the cycle (a_{j} a_{j+1} … a_{r} a_{1} a_{2} … a_{j−1}); we regard this cycle as equivalent to (a_{1} a_{2} … a_{r}). In cycle notation for the permutation σ we write down all its cycles, up to equivalence. For example σ = (1 5 3 4 8)(2 7)(6) ∈ S_{8} is the permutation with σ(1) = 5, σ(2) = 7, σ(3) = 4, σ(4) = 8, σ(5) = 3, σ(6) = 6, σ(7) = 2 and σ(8) = 1. In cycle notation, we may write the cycles in any order, and replace any cycle by an equivalent cycle. Hence

σ = (1 5 3 4 8)(2 7)(6) = (5 3 4 8 1)(6)(2 7) = (6)(7 2)(4 8 1 5 3)

and so on. In practice we usually omit cycles of length 1 so we write the above σ as simply (1 5 3 4 8)(2 7). (The identity permutation of S_{n} is (1)(2) ⋯ (n) with all cycles of length 1; if we omitted them all there would be nothing left, so we use the notation id for this.)

It is easy to see that the order of a permutation σ is the least common multiple of the lengths of its cycles.

A transposition is a permutation of the form (a b). As

(a_{1} a_{2} ⋯ a_{m}) = (a_{1} a_{2})(a_{2} a_{3}) ⋯ (a_{m−1} a_{m})

then each permutation is a product of a sequence of transpositions. If σ is a product of an even number of transpositions, we say σ is an even permutation and if σ is a product of an odd number of transpositions, we say σ is an odd permutation. Clearly every permutation is even or odd, but it is not immediately apparent that a permutation cannot be both even and odd. This is in fact the case.

Lemma 2 Let σ τ ∈ S_{n} with τ = (a b) being a transposition. Suppose that σ has s cycles (including cycles of length 1). Then στ has either s + 1 cycles (if both a and b lie in the same cycle of σ) or s − 1 cycles (if a and b lie in different cycles of σ).

Proof See Fraleigh’s book. □

Theorem 4 Let σ ∈ S_{n} be a product of r transpositions and suppose that σ has s cycles (including cycles of length 1). Then r ≡ n − s (mod 2).

Proof We use induction on r. We regard the identity permutation as the product of zero transpositions. The identity has n cycles (all of length 1) and in this case r = 0 and s = n. Thus r = 0 = n − s.

Suppose σ = τ_{1} ⋯ τ_{r} with r > 0 and the τ_{j} transpositions and set σ′ = τ_{1} ⋯ τ_{r−1}. Let σ have s cycles and σ′ have s′ cycles. By the induction hypothesis r − 1 ≡ n − s′. Now, as σ = στ_{r} then by the previous lemma s = s′ ± 1. Hence n − s = n − s′ ± 1 ≡ n − s + 1 ≡ r − 1 ≡ r (mod 2). □

Corollary 2 Let σ ∈ S_{n}. Then σ cannot be both even and odd.

Proof Let σ be the product of r transpositions. Then r ≡ n − s (mod 2) where s is the number of cycles in σ. The parity (evenness/oddness) of r is thus uniquely determined. □

We define the sign sgn(σ) of a permutation σ as follows:

sgn(σ) = \{ \begin{matrix}+1 & if σ is even, \\ −1 & if σ is odd. \end{matrix}

Lemma 3 Let σ, ρ ∈ S_{n}. Then

• sgn(σρ) = sgn(σ) sgn(ρ),

• sgn(id) = 1 and

• sgn(σ^{−1}) = sgn(σ).

Proof Let σ = τ_{1} … τ_{r} and ρ = τ′_{1} … τ′_{s} where the τ_{i} and τ′_{j} are transpositions. Then sgn(σ) = (−1)^{r} and sgn(ρ) = (−1)^{s}. Also σρ = τ_{1} … τ_{r}τ′_{1} … τ′_{s} and so sgn(στ) = (−1)^{r+s} = (−1)^{r}(−1)^{s} = sgn(σ) sgn(τ).

As id = id id then sgn(id) = sgn(id id) = sgn(id)^{2}. Thus sgn(id) = 1. As id = σσ^{−1} then 1 = sgn(id) = sgn(σσ^{−1}) = sgn(σ) sgn(σ^{−1}) and so

sgn(σ^{−1}) = sgn(σ)^{−1}. But as sgn(σ) = ±1 then sgn(σ)^{−1} = sgn(σ). □

An easy corollary is that the set A_{n} of even permutations is a subgroup of A_{n}; A_{n} is called the alternating group of degree n. When n ≥ 2 the subgroup A_{n} has exactly two cosets in S_{n}: A_{n} itself, and the set of odd permutations in S_{n}. It follows that |A_{n}| = \frac{1}{2}n!.

One application of signs is in the formula for the determinant of an arbitrary matrix. Let A be an n by n matrix with entry a_{ij} in row i and column j. Then

det A = ∑_{σ∈S_{n}} sgn(σ) ∏_{j=1}^{n} a_{jσ(j)} = ∑_{σ∈S_{n}} sgn(σ)a_{1σ(1)}a_{2σ(2)} ⋯ a_{nσ(n)}.

1.6 Homomorphisms and isomorphisms

Let G and H be groups with operations ∗ and ∘ respectively. A homomorphism ϕ from G to H is a function ϕ : G → H satisfying

ϕ(a ∗ b) = ϕ(a) ∘ ϕ(b)

for all a, b ∈ G. If ϕ : G → H and ψ : H → K are homomorphisms then so is ψ ∘ ϕ : G → K. Homomorphisms preserve identities and inverses, that is

ϕ(e) = e′ and ϕ(i(a)) = i(ϕ(a))

where e and e′ denote respectively the identities of G and H, and i(a) denotes the inverse of a etc.

An isomorphism is a bijective homomorphism. Groups G and H are isomorphic if there is an isomorphism ϕ : G → H. We write G ≅ H to denote that G and H are isomorphic. Isomorphic groups have the same structure; apart from the names of elements they are the “same” group: if G and H are isomorphic then they share all group-theoretical properties. For instance, if G is abelian, so is H, G and H have the same order, G and H have the same number of elements of a given order and so on.

Isomorphism is an equivalence relation: for groups G, H and K

• G ≅ G,

• if G ≅ H then H ≅ G,

• if G ≅ H and H ≅ K then G ≅ K.

Every finite cyclic group of order n is isomorphic to Z_{n}, and every infinite cyclic group is isomorphic to Z.

To measure how far away a homomorphism is from being an isomorphism we introduce the notions of kernel and image. Let ϕ : G → H be a homomorphism. The kernel of ϕ is defined as

ker ϕ = {a ∈ G : ϕ(a) = e′},

where e′ denotes the identity of H, and the image of ϕ is defined as

im ϕ = {ϕ(a) : a ∈ G}.

Then ker ϕ is a subset of G and im ϕ is a subset of H. In fact more is true.

Lemma 4 Let ϕ : G → H be a homomorphism. Then ker ϕ is a subgroup of G and im ϕ is a subgroup of H.

Proof Let e and e′ denote the identities of G and H respectively (and use multiplicative notation, so that a^{−1} denotes the inverse of a).

Let a, b ∈ ker ϕ. Then ϕ(a) = ϕ(b) = e′, and as ϕ is a homomorphism, then

ϕ(ab) = ϕ(a)ϕ(b) = e′e′ = e′

so that ab ∈ ker ϕ. As ϕ(e) = e′ then e ∈ ker ϕ. Also

ϕ(a^{−1}) = ϕ(a)^{−1} = e^{′−1} = e′

so that a^{−1} ∈ ker ϕ. Hence ker ϕ is a subgroup of G.

Let u, v ∈ im ϕ. Then u = ϕ(c) and v = ϕ(d) where c, d ∈ G. Then

uv = ϕ(c)ϕ(d) = ϕ(cd) ∈ im ϕ,
e′ = ϕ(e) ∈ im ϕ

and

u^{−1} = ϕ(c)^{−1} = ϕ(c^{−1}) ∈ im ϕ.

Hence im ϕ is a subgroup of G. □

As im ϕ is the range of the function ϕ, it is trivial that ϕ is surjective if and only if im ϕ = H. Similarly the kernel detects injectivity.

Theorem 5 Let ϕ : G → H be a homomorphism. Then ϕ is injective if and only if ker ϕ = {e}.

Proof Certainly e ∈ ker ϕ, since ker ϕ is a subgroup of G. If ker ϕ has another element, a say, then ϕ is not injective since then ϕ(a) = e′ = ϕ(e). Hence if ϕ is injective then ker ϕ = {e}.

Now assume that ker ϕ = {e}. Suppose that ϕ(a) = ϕ(b). Then

ϕ(ab^{−1}) = ϕ(a)ϕ(b^{−1}) = ϕ(a)ϕ(b)^{−1} = ϕ(a)ϕ(a)^{−1} = e′.

Hence ab^{−1} ∈ ker ϕ = {e}, so that ab^{−1} = e. Then a = ab^{−1}b = eb = b. Hence ϕ is injective. □

Not every subgroup of a group G can be a kernel of a homomorphism from G to some group.

Theorem 6 Let ϕ : G → H be a homomorphism. Let K = ker ϕ and take a ∈ G. Then

aK = Ka = {x ∈ G : ϕ(x) = ϕ(a)}.

Proof Define

A = {x ∈ G : ϕ(x) = ϕ(a)}.

Then

x ∈ A ⟺ ϕ(x) = ϕ(a) ⟺ ϕ(x)ϕ(a)^{−1} = e′
⟺ ϕ(x)ϕ(a^{−1}) = e′ ⟺ ϕ(xa^{−1}) = e′
⟺ xa^{−1} ∈ K.

If x ∈ A then x = (xa^{−1})a ∈ Ka and if k ∈ K then (ka)a^{−1} ∈ A and so ka ∈ A. That us, A ⊆ Ka and Ka ⊆ A and so A = Ka.

By a similar argument,

x ∈ A ⟺ a^{−1}x ∈ K

whence follows aK = A. □

If K is the kernel of a homomorphism from G then aK = Ka for all a ∈ G. Not all subgroups of a group G have this property. We say that K is a normal subgroup of G if

• K is a subgroup of G, and

• aK = Ka for all a ∈ G.

We write K ◁ G to denote that K is a normal subgroup of G. Obviously all subgroups of an abelian group are normal. There’s a useful alternative criterion for normality.

Lemma 5 Let H be a subgroup of the group G. Then H is a normal subgroup of G if and only if aha^{−1} ∈ H for all a ∈ G and h ∈ H.

Proof Assume first that H is normal subgroup of G. Let a ∈ G and h ∈ H. Then ah ∈ aH which by normality equals Ha. Hence ah = h′a where h′ ∈ H, whence aha^{−1} = h′ ∈ H.

Now suppose that H ≤ G and that aha^{−1} ∈ H for all a ∈ G and h ∈ H. Let a ∈ H and h ∈ H. Then ah = (aha^{−1})a ∈ Ha as aha^{−1} ∈ H. Hence aH ⊆ Ha. But a^{−1}h(a^{−1})^{−1} = a^{−1}ha ∈ H also, and so ha = a(a^{−1}ha) ∈ aH. Hence Ha ⊆ aH and so aH = Ha. Consequently H is a normal subgroup of G. □

Let H be a normal subgroup of G. We shall construct a group G/H and a homomorphism π : G → G/H which is surjective and has kernel H. This is called the quotient group of G by H. The elements of G/H are the cosets aH where a runs through G. As H is normal it matters not whether we take left or right cosets. The set G/H has |G : H| elements. Let A and B be elements of G/H (so they are cosets of H in G). Define their product as follows: take a ∈ A and b ∈ B, then AB = abH. Certainly abH is an element of G/H. But as it stands this “definition” is dubious. It may depend on the choice of a and b. If we chose other elements of A and B, a′ and b′ say, there is no reason to suppose that the coset a′b′H is the same as abH. If fact if H is not normal this can happen! But if H is normal it cannot, and the definition of AB makes sense.

Lemma 6 Let H be a normal subgroup of the group G. Let A and B be cosets of H in G. Let a, a′ ∈ A and b, b′ ∈ B. Then

abH = a′b′H.

Proof As a ∈ A and H is a coset of the normal subgroup H then A = aH = Ha. Similarly B = bH = Hb. As a′ ∈ A and b′ ∈ B then a′ = ah_{1} and b′ = bh_{2} where h_{1}, h_{2} ∈ H. Thus

a′b′ = ah_{1}bh_{2} = ab(b^{−1}h_{1}b)h_{2}.

As h_{1} ∈ H then b^{−1}h_{1}b ∈ H as H is a normal subgroup of G. Then (b^{−1}h_{1}b)h_{2} ∈ H as h_{2} ∈ H and H is a subgroup. Hence

a′b′ ∈ abH

and so a′b′H = abH. □

With this operation, G/H becomes a group. We can abbreviate the definition to

(aH)(bH) = abH.

It is easily seen that this operation is associative, H = eH is an identity and that a^{−1}H is an inverse for aH. Define π : G → G/H by π(a) = aH. It is easy to see that π is a surjective homomorphism. Now

a ∈ ker ϕ ⟺ ϕ(a) = eH ⟺ aH = eH ⟺ a ∈ H

and so ker π = H. Hence for every normal subgroup H of G there is a homomorphism from G having kernel H.

We conclude with a major theorem which explains the structure of homomorphisms.

Theorem 7 (The first isomorphism theorem) Let ϕ : G → H be a homomorphism. Then

im ϕ ≅ G/ ker ϕ.

Proof For convenience let K = ker ϕ and L = im ϕ. We shall define an isomorphism ψ : G/K → L. Let A ∈ G/K. We attempt to define ψ(A) = ϕ(a) where a is any element of A.

We first ensure that this “definition” makes sense. The problem is that if we choose different elements a, a′ ∈ A we are not yet certain that ϕ(a) = ϕ(a′). Actually, we have already proved this in Lemma 6. We have A = aH, and this lemma showed that if a′ ∈ A then ϕ(a′) = ϕ(a). Hence ψ is welldefined, and maps G/K to L.

We can summarize the definition of ψ by

ψ(aK) = ϕ(a).

It is apparent that ϕ is a homomorphism as

ψ(aKbK) = ψ(abK) = ϕ(ab) = ϕ(a)ϕ(b) = ψ(aK)ψ(bK).

If c ∈ L then

c = ϕ(a) = ψ(aK)

for some a ∈ G and so ψ : G/H → L is surjective. If aK ∈ ker ψ then ψ(aK) = ϕ(a) = e′, the identity of H, and so a ∈ K so that aK = K = eK. Hence ker ψ = {K} and ψ is injective. We have now shown that ψ is an isomorphism. □

1.7 Applications to number theory

Let p be a prime number. The set Z_{p} = {0, 1, 2, …, p − 1} does not form a group under the operation of multiplication modulo p since 0 has no inverse. If we discard 0 we get the set Z_{p}^{∗} = {1, 2, …, p − 1} which appears, for small values of p, to be a group under multiplication modulo p. This is in fact the case for all primes p.

Theorem 8 Let p be a prime number. The set Z_{p}^{∗} = {1, 2, …, p − 1} is an abelian group under multiplication modulo p.

Proof We first show that each element of Z_{p}^{∗} has an inverse. Let a ∈ Z_{p}^{∗}. Consider a as an element of the additive group Z_{p}. Let ⟨a⟩ be the cyclic subgroup of Z_{p} generated by a. By Lagrange’s theorem, | ⟨a⟩ | is a factor of the prime p. Thus | ⟨a⟩ | = 1 or p. Hence ⟨a⟩ = {0} or Z_{p}. But ⟨a⟩ contains the nonzero element 0, so ⟨a⟩ = Z_{p}. This means that for some integer c, ca ≡ 1 (mod p). Thus c, which must be nonzero modulo p, is a multiplicative inverse of a in Z_{p}^{∗}.

To prove that Z_{p}^{∗} is a group the first thing we need is that ab ∈ Z_{p}^{∗} whenever a, b ∈ Z_{p}^{∗}. We need to check that ab ≢ 0 (mod p) whenever a, b ≢ 0 (mod p). But we have seen that if a ≢ 0 (mod p) then there is c with ca ≡ 1 (mod p). Then ab ≡ 0 (mod p) implies cab ≡ 0 (mod p) implies b ≡ 0 (mod p). This contradiction shows that ab ≢ 0 (mod p).

We have seen that multiplication modulo p is a well-defined operation on Z_{p}^{∗}. It is commutative and associative since multiplication of integers is commutative and associative. Finally 1 is an identity, and we have seen that each element has an inverse. □

The group Z_{p}^{∗} has order p − 1, and by the corollary to Lagrange, a^{p−1} = 1 in Z_{p}^{∗} for all elements a ∈ Z_{p}^{∗}. We can rephrase this as Fermat’s Little Theorem:

Let p be a prime, and a an integer not divisible by p. Then

a^{p−1} ≡ 1 (mod p).

Fermat’s little theorem has applications to primality testing. If we have natural numbers a and n with a < n and a^{n−1} ≢ 1 (mod n) then we can be certain that n is not a prime. For a given number n we may be able to find such an a even though it may be computationally infeasible to find a factorization of n.

An amusing consequence of Z_{p}^{∗} forming a group is Wilson’s Theorem.

Theorem 9 (Wilson) Let p be a prime number. Then

(p − 1)! ≡ −1 (mod p).

Proof We can regard (p−1)! = 1×2×3×⋯×(p−1) as the product of all elements of the group Z_{p}^{∗}. In this product we pair off each element with its inverse in Z_{p}^{∗}. The product of an element and its inverse is 1 modulo p. We cannot pair off elements which are their own inverses though; these elements a satisfy a^{2} ≡ 1 (mod p). We conclude that

(p − 1)! ≡ A (mod p)

where A is the product of the a ∈ Z_{p}^{∗} which satisfy a^{2} ≡ 1 (mod p). Certainly a = 1 and a = p − 1 ≡ −1 (mod p) satisfy a^{2} ≡ 1 (mod p). There are no others: for

a^{2} ≡ 1 (mod p) ⟺ a^{2} − 1 ≡ 0 (mod p)
⟺ (a + 1)(a − 1) ≡ 0 (mod p)

which means that either a + 1 ≡ 0 (mod p) or a − 1 ≡ 0 (mod p). Hence A = 1 × (p − 1) ≡ −1 (mod p) and so

(p − 1)! ≡ −1 (mod p).
□

I finish by stating but not proving, a very important theorem in number theory, the Theorem of the Primitive Root. It states that

If p is a prime, then the multiplicative group Z_{p}^{∗} is cyclic.

2 Rings and Fields

2.1 Basics

We now move on to rings. While groups are algebraic systems with a single operation, rings have two main operations, namely addition and multiplication.

A ring R is a set R together with an operations of addition and multiplication (that is, given a, b ∈ R there are elements a + b ∈ R and ab ∈ R), satisfying the following conditions:

A1 a + b = b + a for all a, b ∈ R. (The commutative law for addition.)

A2 (a + b) + c = a + (b + c) for all a, b, c ∈ R. (The associative law for addition.)

A3 There is an element 0 ∈ R such that a + 0 = a for all a ∈ R. (There is an additive identity.)

A4 For each a ∈ R there is an element −a ∈ R with a + (−a) = 0. (There exist additive inverses.)

M1 (ab)c = a(bc) for all a, b, c ∈ R. (The associative law for multiplication.)

M2 There is an element 1 ∈ R such that a1 = a = 1a for all a ∈ R. (There is a multiplicative identity.)

D a(b + c) = ab + ac and (b + c)a = ba + ca for all a, b, c ∈ R. (The distributive law.)

Note that axioms A1–4 say that R is an Abelian group under the operation of addition.

We do not assume that ab = ba, but a ring for which this is always true is called a commutative ring.

A field is a commutative ring where the nonzero elements form a group under multiplication, that is 1 ≠ 0 and for each a ≠ 0 there is b ∈ R with ab = 1.

Basic examples of commutative rings include Z, Q, R, C and Z_{n}, the set {0, 1, 2, …, n − 1} under the operations of addition and multiplication modulo n. The rings Q, R and C are fields; so too is Z_{p} whenever p is prime.

Some examples of noncommutative rings include M_{2}(R), the ring of 2 by 2 matrices with real entries, and H the ring of quaternions. The ring H consists of the expressions a + bi + cj + dk with a, b, c, d ∈ R. Addition in H is defined in the obvious way, while multiplication is defined using the equations

i^{2} = j^{2} = k^{2} = −1, ij = k, ji = −k, jk = i, kj = −i, ki = j, ik = −j.

If α = a + bi + cj + dk is a nonzero quaternion, let β = (a^{2} + b^{2} + c^{2} + d^{2})^{−1}(a − bi − cj − dk). Then αβ = βα = 1.

An element u in a ring R is a unit if there exists v ∈ R with uv = vu = 1. We call v the reciprocal of u and write v = u^{−1}. We denote the set of units of R by U(R).

Theorem 10 Let R be a ring. Then U(R) is a group under the operation of multiplication.

Proof We first need to show that the product of two units of R is a unit of R. Let a, b ∈ U(R). Then there exist u and v ∈ R with au = ua = bv = vb = 1. Then (ab)(vu) = abvu = a1u = au = 1 and (vu)(ab) = vuab = v1b = vb = 1. Hence ab ∈ U(R).

Since multiplication in R is associative, then multiplication in U(R) is associative. Also 1 × 1 = 1, so 1 ∈ U(R) and 1 is manifestly an identity in U(R). Finally if a ∈ U(R) then there is u ∈ R with au = ua = 1. Then u ∈ U(R) and u is an inverse of a in U(R). We conclude that U(R) is a multiplicative group. □

2.2 Subrings

A subring of a group R is a subset S of R which is also a ring under the same operations and having the same identity elements. In detail, S is a subgroup of R if S is a subset of R and SR1 a + b, ab ∈ S whenever a ∈ S and b ∈ S (closure).

SR2 0 ∈ S and 1 ∈ S where 0 and 1 are the additive and multiplicative identities of R (identities).

SR3 For each a ∈ S then −a ∈ S (negatives).

It is clear that whenever S is a subring of the ring R then S is a ring.

2.3 Integral domains

Let R be a ring. If a and b are nonzero elements of R with ab = 0 we say that a and b are zerodivisors. A commutative ring without zerodivisors is an integral domain. That is a commutative ring R is an integral domain if whenever ab = 0 in R then either a = 0 or b = 0.

From now on in this section let R denote an integral domain.

Let a, b ∈ R. If b = ac for some c ∈ R we say that a is a divisor of b, or a is a factor of b, or b is a multiple of a, or that a divides b, and we write a | b. The relation of divisibility has various simple properties, familiar from the case where R = Z, which we shall not list, but will use without comment.

An element a of R is irreducible if a is nonzero and not a unit and whenever a = bc with b, c ∈ R then either b or c is a unit. An element a of R is composite if a = bc where a and b are nonzero and not units. The elements of R fall into four classes: the zero element, the units, the irreducibles and the composites.

We wish to investigate the factorization of composites into irreducibles. For instance in Z, the composite 21 can be factorized into irreducibles in four ways:

21 = (3)(7) = (7)(3) = (−3)(−7) = (−7)(−3).

However these factorizations can all be obtained from the first by simple manipulations: changing the order of factors and replacing factors a by −a, that is by multiplying by the unit −1. Suppose we have two factorizations

a = b_{1}b_{2} ⋯ b_{r} = c_{1}c_{2} ⋯ c_{s}

of a ∈ R. We say these factorizations are equivalent if s = r and the elements c_{1}, …, c_{r} can be re-ordered so that c_{j} = u_{j}b_{j} where each u_{j} ∈ U(R).

We aim to prove that Z has unique factorization, and then extend the method of proof to a wider class of integral domains, the so-called Euclidean domains.

The irreducibles of Z are the numbers ±p where p is prime.

Lemma 7 Let a and b ∈ Z and let p be a prime number. If p | ab then either p | a or p | b.

Proof This is essentially the same as Theorem 8. Suppose that p ∤ ab. If p ∤ a then a ≡ a′ (mod p) for some a′ ∈ {1, 2, …, p − 1}. From Theorem 8 there is an integer c with a′c ≡ 1 (mod p). Hence ac ≡ a′c ≡ 1 (mod p) and so 0 ≡ abc ≡ b (mod p). □

Corollary 3 Let a_{1}, …, a_{r} ∈ Z and let p be a prime number. If p | a_{1}a_{2} ⋯ a_{r} then either p | a_{j} for some j.

Proof This follows from the lemma by a simple induction argument. □ We can now prove unique factorization in Z.

Theorem 11 The integral domain Z has unique factorization.

Proof The units of Z are ±1 and so it is sufficient to prove that if we have two factorizations

n = p_{1}p_{2} ⋯ p_{r} = q_{1}q_{2} ⋯ q_{s}

into primes, then r = s and the q_{j} can be re-ordered so that q_{j} = p_{j} for all j.

Since p_{1} is a prime, and p_{1} | n, then p_{1} | q_{1}q_{2} ⋯ q_{s}. By the previous corollary, p_{1} | q_{j} for some j. By re-ordering the qs we may suppose that p_{1} | q_{1}. As p_{1} and q_{1} are prime, then p_{1} = q_{1} and so

n/p_{1} = p_{2}p_{3} ⋯ p_{r} = q_{2}q_{3} ⋯ q_{s}.

Repeating the argument shows that by re-ordering q_{2}, …, q_{s} we have p_{2} = q_{2}, then p_{3} = q_{3} and so on. Eventually all p_{j} = q_{j} and we must have r = s. □

2.4 Euclidean domains

Euclidean domains are a class of integral domains having unique factorization. An integral domain R is a Euclidean domain if there is a function v from R − {0} (the set of nonzero elements of R) to N ∪ {0} (the set of nonnegative integers) having the following Euclidean property:

• if a, b ∈ R with b ≠ 0 then there exists q ∈ R with a − bq = 0 (so that b | q) or v(a − bq) < v(b).

The standard examples of Euclidean domains are Z with v(a) = |a|, the polynomial ring F [X], where F is a field, with v(f) being the degree of f and Z[i] = {a + bi : a, b ∈ Z}, the Gaussian integers, with v(a + bi) = |a + bi|^{2} = a^{2} + b^{2}.

In Euclidean domains, there is a Euclidean algorithm for finding greatest common divisors. If a and b are nonzero elements of an integral domain, a greatest common divisor of a and b is an element c ∈ R such that

• c | a and c | b (that is, c is a common divisor of a and b, and

• if d ∈ R, d | a and d | b then d | c (all common divisors of a and b divide c).

If c is a greatest common divisor of a and b then so is uc whenever u is a unit of R. Thus we should talk of “a greatest common divisor of a and b” rather than “the greatest common divisor of a and b”.

We now state the Euclidean algorithm. Our version is the so-called extended Euclidean algorithm which computes additional information as well as a greatest common divisor.

Let R be a Euclidean domain with Euclidean function v. Let a and b be nonzero elements of R. We shall compute sequences a_{1}, a_{2}, …, r_{1}, r_{2}, … and s_{1}, s_{2}, … of elements of R with a_{j} = r_{j}a + s_{j}b for each j. We start with a_{1} = a, r_{1} = 1, s_{1} = 0, a_{2} = b, r_{2} = 0 and s_{2} = 1. It’s obvious then that a_{j} = r_{j}a + s_{j}b for j = 1 and j = 2. We now repeat the following step.

At the k-th step we will have nonzero a_{k}, a_{k+1} ∈ R and r_{k}, r_{k+1}, s_{k} and s_{k+1} ∈ R with a_{k} = r_{k}a + s_{k}b and a_{k+1} = r_{k+1}a + s_{k+1}b. By the Euclidean condition, there exists q_{k} ∈ R with a_{k} − q_{k}a_{k+1} = 0 or v(a_{k} − q_{k}a_{k+1}) < v(a_{k+1}). Set a_{k+2} = a_{k} − q_{k}a_{k+1}. If a_{k+2} = 0 we stop. Otherwise set

r_{k+2} = r_{k} − q_{k}r_{k+1} and s_{k+2} = s_{k} − q_{k}s_{k+1}.

In this case

a_{k+2} = a_{k} − q_{k}a_{k+1}
= (r_{k}a + s_{k}b) − q_{k}(r_{k+1}a + s_{k+1}b)
= (r_{k} − q_{k}r_{k+1})a + (s_{k} − q_{k}s_{k+1})b
= r_{k+2}a + s_{k+2}b

and we may proceed to the next step. Note that v(a_{k+2}) < v(a_{k+1}).

The algorithm must terminate. For v(a_{2}) > v(a_{3}) > ⋯ is a strictly decreasing sequence of nonnegative integers and so cannot continue indefinitely. For some n, then a_{n} ≠ 0 but a_{n+1} = 0. We output c = a_{n}, r = r_{n} and s = s_{n}.

Theorem 12 Let R be a Euclidean domain with Euclidean function v, and let a and b be nonzero elements of R. Let c, r and s be the outputs of the extended Euclidean algorithm applied to a and b. Then c is a greatest common divisor of a and b. Also c = ra + sb.

Proof Let D(a_{j}, a_{j+1}) denote the set of common divisors of a_{j} and a_{j+1} in R, that is

D(a_{j}, a_{j+1}) = {d ∈ R : d | a_{j} and d | a_{j+1}}.

I claim that D(a_{j}, a_{j+1}) = D(a_{j+1}, a_{j+2}). We have a_{j+2} = a_{j} − q_{j}a_{j+1} and so a_{j} = a_{j+2} + q_{j}a_{j+1}. If d ∈ D(a_{j}, a_{j+1}) then d | a_{j+1} so d | q_{j}a_{j+1} and as d | a_{j} then d | (a_{j} − q_{j}a_{j+1}), that is d | a_{j+2}. Hence d ∈ D(a_{j+1}, a_{j+2}), and so D(a_{j}, a_{j+1}) ⊆ D(a_{j+1}, a_{j+2}). Similarly if d ∈ D(a_{j+1}, a_{j+1}) then d | a_{j+1} so d | q_{j}a_{j+1} and as d | a_{j+2} then d | (a_{j+2} + q_{j}a_{j+1}), that is d | a_{j}. Hence d ∈ D(a_{j}, a_{j+1}), and so D(a_{j+1}, a_{j+2}) ⊆ D(a_{j}, a_{j+1}). Hence D(a_{j}, a_{j+1}) = D(a_{j+1}, a_{j+2}).

It follows that

D(a, b) = D(a_{1}, a_{2}) = D(a_{2}, a_{3}) = ⋯ = D(a_{n}, a_{n+1}) = D(c, 0).

As c | c and c | 0 then c ∈ D(c, 0) and so c ∈ D(a, b), that is, c | a and c | b. If d | a and d | b then d ∈ D(a, b) and so d ∈ D(c, 0) so that d | c. Hence c is a greatest common divisor of a and b.

Finally

c = a_{n} = r_{n}a + s_{n}b = ra + sb.
□

We now proceed to the proof of unique factorization.

Lemma 8 Let R be a Euclidean domain. Let a, b and c ∈ R. Suppose that c is irreducible in R. Then either c | a or c | b.

Proof Suppose that c ∤ a. Applying the extended Euclidean algorithm to a and c yields a greatest common divisor g of a and c and r, s ∈ R with g = ra + sc. Now g | c and so c = gh where h ∈ R. As c is irreducible either g is a unit, or h is a unit. We show the latter is impossible. If h is a unit, then g = ch^{−1}, so c | g and as g | b then c | a contrary to hypothesis. Hence g is a unit and so

1 = g^{−1}g = (g^{−1}r)a + (g^{−1}s)c

and consequently

b = g^{−1}g = (g^{−1}r)ab + (g^{−1}s)c.

As c | ab then c | (g^{−1}r)ab and as obviously c | (g^{−1}s)c then c | [(g^{−1}r)ab + (g^{−1}s)c], that is, c | b. □

As before it follows that if c | a_{1}a_{2} ⋯ a_{n} in a Euclidean domain with c irreducible, then c | a_{j} for some j.

Theorem 13 Each Euclidean domain R has unique factorization.

Proof As the proof is almost identical to that of Theorem 11 we omit it but make some comments on some salient points.

As before if we have two factorizations

a = p_{1}p_{2} ⋯ p_{r} = q_{1}q_{2} ⋯ q_{s}

into irreducibles, then we may re-order the qs so that p_{1} | q_{1}. This does not imply that p_{1} = q_{1} in this case. We have q_{1} = p_{1}u where u ∈ R. As q_{1} is irreducible and p_{1} is not a unit, then u is a unit. We must expect this eventuality which is allowed by the definition of equivalence of factorizations. At the next stage we get

p_{2}p_{3} ⋯ p_{r} = uq_{2}q_{3} ⋯ q_{s}.

As we cannot have p_{2} | u (since u is a unit and p_{2} isn’t) then we have p_{2} | q_{j} for some j ≥ 2 and the argument can continue. □