Abstract Algebra - Wilkins

Course 311: Michaelmas Term 1999 Part I: Topics in Number Theory D. R. Wilkins

Contents 1 Topics in Number Theory 1.1 Subgroups of the Integers . . . . . . . . . . 1.2 Greatest Common Divisors . . . . . . . . . . 1.3 The Euclidean Algorithm . . . . . . . . . . . 1.4 Prime Numbers . . . . . . . . . . . . . . . . 1.5 The Fundamental Theorem of Arithmetic . . 1.6 The Infinitude of Primes . . . . . . . . . . . 1.7 Congruences . . . . . . . . . . . . . . . . . . 1.8 The Chinese Remainder Theorem . . . . . . 1.9 The Euler Totient Function . . . . . . . . . 1.10 The Theorems of Fermat, Wilson and Euler 1.11 Solutions of Polynomial Congruences . . . . 1.12 Primitive Roots . . . . . . . . . . . . . . . . 1.13 Quadratic Residues . . . . . . . . . . . . . . 1.14 Quadratic Reciprocity . . . . . . . . . . . . 1.15 The Jacobi Symbol . . . . . . . . . . . . . .

1

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

2 2 2 3 4 5 6 6 8 9 11 13 14 16 21 22

1 1.1

Topics in Number Theory Subgroups of the Integers

A subset S of the set Z of integers is a subgroup of Z if 0 ∈ S, −x ∈ S and x + y ∈ S for all x ∈ S and y ∈ S. It is easy to see that a non-empty subset S of Z is a subgroup of Z if and only if x − y ∈ S for all x ∈ S and y ∈ S. Let m be an integer, and let mZ = {mn : n ∈ Z}. Then mZ (the set of integer multiples of m) is a subgroup of Z. Theorem 1.1 Let S be a subgroup of Z. Then S = mZ for some nonnegative integer m. Proof If S = {0} then S = mZ with m = 0. Suppose that S 6= {0}. Then S contains a non-zero integer, and therefore S contains a positive integer (since −x ∈ S for all x ∈ S). Let m be the smallest positive integer belonging to S. A positive integer n belonging to S can be written in the form n = qm + r, where q is a positive integer and r is an integer satisfying 0 ≤ r < m. Then qm ∈ S (because qm = m + m + · · · + m). But then r ∈ S, since r = n − qm. It follows that r = 0, since m is the smallest positive integer in S. Therefore n = qm, and thus n ∈ mZ. It follows that S = mZ, as required.

1.2

Greatest Common Divisors

Definition Let a1 , a2 , . . . , ar be integers, not all zero. A common divisor of a1 , a2 , . . . , ar is an integer that divides each of a1 , a2 , . . . , ar The greatest common divisor of a1 , a2 , . . . , ar is the greatest positive integer that divides each of a1 , a2 , . . . , ar . The greatest common divisor of a1 , a2 , . . . , ar is denoted by (a1 , a2 , . . . , ar ). Theorem 1.2 Let a1 , a2 , . . . , ar be integers, not all zero. Then there exist integers u1 , u2 , . . . , ur such that (a1 , a2 , . . . , ar ) = u1 a1 + u2 a2 + · · · + ur ar . where (a1 , a2 , . . . , ar ) is the greatest common divisor of a1 , a2 , . . . , ar . Proof Let S be the set of all integers that are of the form n1 a1 + n2 a2 + · · · + nr ar for some n1 , n2 , . . . , nr ∈ Z. Then S is a subgroup of Z. It follows that S = mZ for some non-negative integer m (Theorem 1.1). Then m is a 2

common divisor of a1 , a2 , . . . , ar , (since ai ∈ S for i = 1, 2, . . . , r). Moreover any common divisor of a1 , a2 , . . . , ar is a divisor of each element of S and is therefore a divisor of m. It follows that m is the greatest common divisor of a1 , a2 , . . . , ar . But m ∈ S, and therefore there exist integers u1 , u2 , . . . , ur such that (a1 , a2 , . . . , ar ) = u1 a1 + u2 a2 + · · · + ur ar , as required. Definition Let a1 , a2 , . . . , ar be integers, not all zero. If the greatest common divisor of a1 , a2 , . . . , ar is 1 then these integers are said to be coprime. If integers a and b are coprime then a is said to be coprime to b. (Thus a is coprime to b if and only if b is coprime to a.) Corollary 1.3 Let a1 , a2 , . . . , ar be integers, not all zero, Then a1 , a2 , . . . , ar are coprime if and only if there exist integers u1 , u2 , . . . , ur such that 1 = u1 a1 + u2 a2 + · · · + ur ar . Proof If a1 , a2 , . . . , ar are coprime then the existence of the required integers u1 , u2 , . . . , ur follows from Theorem 1.2. On the other hand if there exist integers u1 , u2 , . . . , ur with the required property then any common divisor of a1 , a2 , . . . , ar must be a divisor of 1, and therefore a1 , a2 , . . . , ar must be coprime.

1.3

The Euclidean Algorithm

Let a and b be positive integers with a > b. Let r0 = a and r1 = b. If b does not divide a then let r2 be the remainder on dividing a by b. Then a = q1 b + r2 , where q1 and r2 are positive integers and 0 < r2 < b. If r2 does not divide b then let r3 be the remainder on dividing b by r2 . Then b = q2 r2 + r3 , where q2 and r3 are positive integers and 0 < r3 < r2 . If r3 does not divide r2 then let r4 be the remainder on dividing r2 by r3 . Then r2 = q3 r3 + r4 , where q3 and r4 are positive integers and 0 < r4 < r3 . Continuing in this fashion, we construct positive integers r0 , r1 , . . . , rn such that r0 = a, r1 = b and ri is the remainder on dividing ri−2 by ri−1 for i = 2, 3, . . . , n. Then ri−2 = qi−1 ri−1 + ri , where qi−1 and ri are positive integers and 0 < ri < ri−1 . The algorithm for constructing the positive integers r0 , r1 , . . . , rn terminates when rn divides rn−1 . Then rn−1 = qn rn for some positive integer qn . (The algorithm must clearly terminate in a finite number of steps, since r0 > r1 > r2 > · · · > rn .) We claim that rn is the greatest common divisor of a and b. 3

Any divisor of rn is a divisor of rn−1 , because rn−1 = qn rn . Moreover if 2 ≤ i ≤ n then any common divisor of ri and ri−1 is a divisor of ri−2 , because ri−2 = qi−1 ri−1 + ri . If follows that every divisor of rn is a divisor of all the integers r0 , r1 , . . . , rn . In particular, any divisor of rn is a common divisor of a and b. In particular, rn is itself a common divisor of a and b. If 2 ≤ i ≤ n then any common divisor of ri−2 and ri−1 is a divisor of ri , because ri = ri−2 − qi−1 ri−1 . It follows that every common divisor of a and b is a divisor of all the integers r0 , r1 , . . . , rn . In particular any common divisor of a and b is a divisor of rn . It follows that rn is the greatest common divisor of a and b. There exist integers ui and vi such that ri = ui a + vi b for i = 1, 2, . . . , n. Indeed ui = ui−2 −qi−1 ui−1 and vi = vi−2 −qi−1 vi−1 for each integer i between 2 and n, where u0 = 1, v0 = 0, u1 = 0 and v1 = 1. In particular rn = un a+vn b. The algorithm described above for calculating the greatest common divisor (a, b) of two positive integers a and b is referred to as the Euclidean algorithm. It also enables one to calculate integers u and v such that (a, b) = ua + vb. Example We calculate the greatest common divisor of 425 and 119. Now 425 119 68 51

= = = =

3 × 119 + 68 68 + 51 51 + 17 3 × 17.

It follows that 17 is the greatest common divisor of 425 and 119. Moreover 17 = 68 − 51 = 68 − (119 − 68) = 2 × 68 − 119 = 2 × (425 − 3 × 119) − 119 = 2 × 425 − 7 × 119.

1.4

Prime Numbers

Definition A prime number is an integer p greater than one with the property that 1 and p are the only positive integers that divide p. Let p be a prime number, and let x be an integer. Then the greatest common divisor (p, x) of p and x is a divisor of p, and therefore either (p, x) = p or else (p, x) = 1. It follows that either x is divisible by p or else x is coprime to p.

4

Theorem 1.4 Let p be a prime number, and let x and y be integers. If p divides xy then either p divides x or else p divides y. Proof Suppose that p divides xy but p does not divide x. Then p and x are coprime, and hence there exist integers u and v such that 1 = up + vx (Corollary 1.3). Then y = upy + vxy. It then follows that p divides y, as required. Corollary 1.5 Let p be a prime number. If p divides a product of integers then p divides at least one of the factors of the product. Proof Let a1 , a2 , . . . , ak be integers, where k > 1. Suppose that p divides a1 a2 · · · ak . Then either p divides ak or else p divides a1 a2 · · · ak−1 . The required result therefore follows by induction on the number k of factors in the product.

1.5

The Fundamental Theorem of Arithmetic

Lemma 1.6 Every integer greater than one is a prime number or factors as a product of prime numbers. Proof Let n be an integer greater than one. Suppose that every integer m satisfying 1 < m < n is a prime number or factors as a product of prime numbers. If n is not a prime number then n = ab for some integers a and b satisfying 1 < a < n and 1 < b < n. Then a and b are prime numbers or products of prime numbers. It follows that n is a prime number or a product of prime numbers. The required result therefore follows by induction on n. An integer greater than one that is not a prime number is said to be a composite number. Let n be an composite number. We say that n factors uniquely as a product of prime numbers if, given prime numbers p1 , p2 , . . . , pr and q1 , q2 , . . . , qs such that n = p1 p2 · · · pr = q1 q2 . . . , qs , the number of times a prime number occurs in the list p1 , p2 , . . . , pr is equal to the number of times it occurs in the list q1 , q2 , . . . , qs . (Note that this implies that r = s.) Theorem 1.7 (The Fundamental Theorem of Arithmetic) Every composite number greater than one factors uniquely as a product of prime numbers. 5

Proof Let n be a composite number greater than one. Suppose that every composite number greater than one and less than n factors uniquely as a product of prime numbers. We show that n then factors uniquely as a product of prime numbers. Suppose therefore that n = p1 p2 · · · pr = q1 q2 . . . , qs , where p1 , p2 , . . . , pr and q1 , q2 , . . . , qs are prime numbers, p1 ≤ p2 ≤ · · · ≤ pr and q1 ≤ q2 ≤ · · · ≤ qs . We must prove that r = s and pi = qi for all integers i between 1 and r. Let p be the smallest prime number that divides n. If a prime number divides a product of integers then it must divide at least one of the factors (Corollary 1.5). It follows that p must divide pi and thus p = pi for some integer i between 1 and r. But then p = p1 , since p1 is the smallest of the prime numbers p1 , p2 , . . . , pr . Similarly p = q1 . Therefore p = p1 = q1 . Let m = n/p. Then m = p2 p3 · · · pr = q2 q3 · · · qs . But then r = s and pi = qi for all integers i between 2 and r, because every composite number greater than one and less than n factors uniquely as a product of prime numbers. It follows that n factors uniquely as a product of prime numbers. The required result now follows by induction on n. (We have shown that if all composite numbers m satisfying 1 < m < n factor uniquely as a product of prime numbers, then so do all composite numbers m satisfying 1 < m < n + 1.)

1.6

The Infinitude of Primes

Theorem 1.8 (Euclid) The number of prime numbers is infinite. Proof Let p1 , p2 , . . . , pr be prime numbers, let m = p1 p2 · · · pr + 1. Now pi does not divide m for i = 1, 2, . . . , r, since if pi were to divide m then it would divide m − p1 p2 · · · pr and thus would divide 1. Let p be a prime factor of m. Then p must be distinct from p1 , p2 , . . . , pr . Thus no finite set {p1 , p2 , . . . , pr } of prime numbers can include all prime numbers.

1.7

Congruences

Let m be a positive integer. Integers x and y are said to be congruent modulo m if x − y is divisible by m. If x and y are congruent modulo m then we denote this by writing x ≡ y (mod m).

6

The congruence class of an integer x modulo m is the set of all integers that are congruent to x modulo m. Let x, y and z be integers. Then x ≡ x (mod m). Also x ≡ y (mod m) if and only if y ≡ x (mod m). If x ≡ y (mod m) and y ≡ z (mod m) then x ≡ z (mod m). Thus congruence modulo m is an equivalence relation on the set of integers. Lemma 1.9 Let m be a positive integer, and let x, x0 , y and y 0 be integers. Suppose that x ≡ x0 (mod m) and y ≡ y 0 (mod m). Then x + y ≡ x0 + y 0 (mod m) and xy ≡ x0 y 0 (mod m). Proof The result follows immediately from the identities (x + y) − (x0 + y 0 ) = (x − x0 ) + (y − y 0 ), xy − x0 y 0 = (x − x0 )y + x0 (y − y 0 ). Lemma 1.10 Let x, y and m be integers with m 6= 0. Suppose that m divides xy and that m and x are coprime. Then m divides y. Proof There exist integers a and b such that 1 = am + bx, since m and x are coprime (Corollary 1.3). Then y = amy + bxy, and m divides xy, and therefore m divides y, as required. Lemma 1.11 Let m be a positive integer, and let a, x and y be integers with ax ≡ ay (mod m). Suppose that m and a are coprime. Then x ≡ y (mod m). Proof If ax ≡ ay (mod m) then a(x − y) is divisible by m. But m and a are coprime. It therefore follows from Lemma 1.10 that x − y is divisible by m, and thus x ≡ y (mod m), as required. Lemma 1.12 Let x and m be non-zero integers. Suppose that x is coprime to m. Then there exists an integer y such that xy ≡ 1 (mod m). Moreover y is coprime to m. Proof There exist integers y and k such that xy + mk = 1, since x and m are coprime (Corollary 1.3). Then xy ≡ 1 (mod m). Moreover any common divisor of y and m must divide xy and therefore must divide 1. Thus y is coprime to m, as required. Lemma 1.13 Let m be a positive integer, and let a and b be integers, where a is coprime to m. Then there exist integers x that satisfy the congruence ax ≡ b (mod m). Moreover if x and x0 are integers such that ax ≡ b (mod m) and ax0 ≡ b (mod m) then x ≡ x0 mod m. 7

Proof There exists an integer c such that ac ≡ 1 (mod m), since a is coprime to m (Lemma 1.12). Then ax ≡ b (mod m) if and only if x ≡ cb (mod m). The result follows. Lemma 1.14 Let a1 , a2 , . . . , ar be integers, and let x be an integer that is coprime to ai for i = 1, 2, . . . , r. Then x is coprime to the product a1 a2 · · · ar of the integers a1 , a2 , . . . , ar . Proof Let p be a prime number which divides the product a1 a2 · · · ar . Then p divides one of the factors a1 , a2 , . . . , ar (Corollary 1.5). It follows that p cannot divide x, since x and ai are coprime for i = 1, 2, . . . , r. Thus no prime number is a common divisor of x and the product a1 a2 · · · ar . It follows that the greatest common divisor of x and a1 a2 · · · ar is 1, since this greatest common divisor cannot have any prime factors. Thus x and a1 a2 · · · ar are coprime, as required. Let m be a positive integer. For each integer x, let [x] denote the congruence class of x modulo m. If x, x0 , y and y 0 are integers and if x ≡ x0 (mod m) and y ≡ y 0 (mod m) then xy ≡ x0 y 0 (mod m). It follows that there is a well-defined operation of multiplication defined on congruence classes of integers modulo m, where [x][y] = [xy] for all integers x and y. This operation is commutative and associative, and [x][1] = [x] for all integers x. If x is an integer coprime to m, then it follows from Lemma 1.12 that there exists an integer y coprime to m such that xy ≡ 1 (mod m). Then [x][y] = [1]. Therefore the set Z∗m of congruence classes modulo m of integers coprime to m is an Abelian group (with multiplication of congruence classes defined as above).

1.8

The Chinese Remainder Theorem

Let I be a set of integers. The integers belonging to I are said to be pairwise coprime if any two distinct integers belonging to I are coprime. Proposition 1.15 Let m1 , m2 , . . . , mr be non-zero integers that are pairwise coprime. Let x be an integer that is divisible by mi for i = 1, 2, . . . , r. Then x is divisible by the product m1 m2 · · · mr of the integers m1 , m2 , . . . , mr . Proof For each integer k between 1 and r let Pk be the product of the integers mi with 1 ≤ i ≤ k. Then P1 = m1 and Pk = Pk−1 mk for k = 2, 3, . . . , r. Let x be a positive integer that is divisible by mi for i = 1, 2, . . . , r. We must show that Pr divides x. Suppose that Pk−1 divides x for some integer k between 2 and r. Let y = x/Pk−1 . Then mk and Pk−1 are coprime 8

(Lemma 1.14) and mk divides Pk−1 y. It follows from Lemma 1.10 that mk divides y. But then Pk divides x, since Pk = Pk−1 mk and x = Pk−1 y. On successively applying this result with k = 2, 3, . . . , r we conclude that Pr divides x, as required. Theorem 1.16 (Chinese Remainder Theorem) Let m1 , m2 , . . . , mr be pairwise coprime positive integers. Then, given any integers x1 , x2 , . . . , xr , there exists an integer z such that z ≡ xi (mod mi ) for i = 1, 2, . . . , r. Moreover if z 0 is any integer satisfying z 0 ≡ xi (mod mi ) for i = 1, 2, . . . , r then z 0 ≡ z (mod m), where m = m1 m2 · · · mr . Proof Let m = m1 m2 · · · mr , and let si = m/mi for i = 1, 2, . . . , r. Note that si is the product of the integers mj with j 6= i, and is thus a product of integers coprime to mi . It follows from Lemma 1.14 that mi and si are coprime for i = 1, 2, . . . , r. Therefore there exist integers ai and bi such that ai mi + bi si = 1 for i = 1, 2, . . . , r (Corollary 1.3). Let ui = bi si for i = 1, 2, . . . , r. Then ui ≡ 1 (mod mi ), and ui ≡ 0 (mod mj ) when j 6= i. Thus if z = x1 u1 + x2 u2 + · · · xr ur then z ≡ xi (mod mi ) for i = 1, 2, . . . , r. Now let z 0 be an integer with z 0 ≡ xi (mod mi ) for i = 1, 2, . . . , r. Then 0 z − z is divisible by mi for i = 1, 2, . . . , r. It follows from Proposition 1.15 that z 0 − z is divisible by the product m of the integers m1 , m2 , . . . , mr . Then z 0 ≡ z (mod m), as required.

1.9

The Euler Totient Function

Let n be a positive integer. We define ϕ(n) to be the number of integers x satisfying 0 ≤ x < n that are coprime to n. The function ϕ on the set of positive integers is referred to as the Euler totient function. Every integer (including zero) is coprime to 1, and therefore ϕ(1) = 1. Let p be a prime number. Then ϕ(p) = p − 1, since every positive integer less than p is coprime to p. Moreover ϕ(pk ) = pk − pk−1 for all positive integers k, since there are pk−1 integers x satisfying 0 ≤ x < pk that are divisible by p, and the integers coprime to pk are those that are not divisible by p. Theorem 1.17 Let m1 and m2 be positive integers. Suppose that m1 and m2 are coprime. Then ϕ(m1 m2 ) = ϕ(m1 )ϕ(m2 ).

9

Proof Let x be an integer satisfying 0 ≤ x < m1 that is coprime to m1 , and let y be an integer satisfying 0 ≤ y < m2 that is coprime to m2 . It follows from the Chinese Remainder Theorem (Theorem 1.16) that there exists exactly one integer z satisfying 0 ≤ z < m1 m2 such that z ≡ x (mod m1 ) and z ≡ y (mod m2 ). Moreover z must then be coprime to m1 and to m2 , and must therefore be coprime to m1 m2 . Thus every integer z satisfing 0 ≤ z < m1 m2 that is coprime to m1 m2 is uniquely determined by its congruence classes modulo m1 and m2 , and the congruence classes of z modulo m1 and m2 contain integers coprime to m1 and m2 respectively. Thus the number ϕ(m1 m2 ) of integers z satisfying 0 ≤ z < m1 m2 that are coprime to m1 m2 is equal to ϕ(m1 )ϕ(m2 ), since ϕ(m1 ) is the number of integers x satisfying 0 ≤ x < m1 that are coprime to m1 and ϕ(m2 ) is the number of integers y satisfying 0 ≤ y < m2 that are coprime to m2 .  Y 1 Corollary 1.18 ϕ(n) = n 1− , for all positive integers n, where p p|n  Y 1 1 1− denotes the product of 1 − taken over all prime numbers p p p p|n

that divide n. Proof Let n = pk11 pk22 · · · pkmm , where p1 , p2 , . . . , pm are prime numbers and k1 , k2 , . . . , km are positive integers. Then ϕ(n) = ϕ(pk11 )ϕ(pk22 ) · · · ϕ(pkmm ), and  m  Y 1 ki ki ϕ(pi ) = pi (1 − (1/pi )) for i = 1, 2, . . . , m. Thus ϕ(n) = n , as 1− p i i=1 required. Let f be any function defined on the set of positive integers, and let n be a positive Xinteger. We denote the sum of the values of f (d) over all divisors d of n by f (d). d|n

Lemma 1.19 Let n be a positive integer. Then

X

ϕ(d) = n.

d|n

Proof If x is an integer satisfying X0 ≤ x < n then (x, n) = n/d for some divisor d of n. It follows that n = nd , where nd is the number of integers x d|n

satisfying 0 ≤ x < n for which (x, n) = n/d. Thus it suffices to show that nd = ϕ(d) for each divisor d of n. Let d be a divisor of n, and let a = n/d. Given any integer x satisfying 0 ≤ x < n that is divisible by a, there exists an integer y satisfying 0 ≤ y < d 10

such that x = ay. Then (x, n) is a multiple of a. Moreover a multiple ae of a divides both x and n if and only if e divides both y and d. Therefore (x, n) = a(y, d). It follows that the integers x satisfying 0 ≤ x < n for which (x, n) = a are those of the form ay, where y is an integer, 0 ≤ y < d and (y, d) = 1. It follows that there are exactly ϕ(d) integers X x satisfying 0 ≤ x < n for which (x, n) = n/d, and thus nd = ϕ(d) and n = ϕ(d), as d|n

required.

1.10

The Theorems of Fermat, Wilson and Euler

Theorem 1.20 (Fermat) Let p be a prime number. Then xp ≡ x (mod p) for all integers x. Moreover if x is coprime to p then xp−1 ≡ 1 (mod p). We shall give three proofs of this theorem below.   p Lemma 1.21 Let p be a prime number. Then the binomial coefficient k is divisible by p for all integers k satisfying 0 < k < p.   p p! Proof The binomial coefficient is given by the formula = . k (p − k)!k!   p pm (p − 1)! Thus if 0 < k < p then = , where m = . Thus if 0 < k < p k k! (p − k)! then k! divides pm. Also k! is coprime to p. It follows that k! divides m   p (Lemma 1.10), and therefore the binomial coefficient is a multiple of k p. First Proof of Theorem 1.20 Let p be prime number. Then p   X p k (x + 1) = x . k k=0 p

It then follows from Lemma 1.21 that (x + 1)p ≡ xp + 1 (mod p). Thus if f (x) = xp − x then f (x + 1) ≡ f (x) (mod p) for all integers x, since f (x + 1) − f (x) = (x + 1)p − xp − 1. But f (0) ≡ 0 (mod p). It follows by induction on |x| that f (x) ≡ 0 (mod p) for all integers x. Thus xp ≡ x (mod p) for all integers x. Moreover if x is coprime to p then it follows from Lemma 1.11 that xp−1 ≡ 1 (mod p), as required.

11

Second Proof of Theorem 1.20 Let x be an integer. If x is divisible by p then x ≡ 0 (mod p) and xp ≡ 0 (mod p). Suppose that x is coprime to p. If j is an integer satisfying 1 ≤ j ≤ p − 1 then j is coprime to p and hence xj is coprime to p. It follows that there exists a unique integer uj such that 1 ≤ uj ≤ p − 1 and xj ≡ uj (mod p). If j and k are integers between 1 and p − 1 and if j 6= k then uj 6= uk . It follows that each integer between 1 and p − 1 occurs exactly once in the list u1 , u2 , . . . , up−1 , and therefore u1 u2 · · · up−1 = (p − 1)!. Thus if we multiply together the left hand sides and right hand sides of the congruences xj ≡ uj (mod p) for j = 1, 2, . . . , p−1 we obtain the congruence xp−1 (p−1)! ≡ (p−1)! (mod p). But then xp−1 ≡ 1 (mod p) by Lemma 1.11, since (p−1)! is coprime to p. But then xp ≡ x (mod p), as required. Third Proof of Theorem 1.20 Let p be a prime number. The congruence classes modulo p of integers coprime to p constitute a group of order p − 1, where the group operation is multiplication of congruence classes. Now it follows from Lagrange’s Theorem that that order of any element of a finite group divides the order of the group. If we apply this result to the group of congruence classes modulo p of integers coprime to p we find that if an integer x is not divisible by p then xp−1 ≡ 1 (mod p). It follows that xp ≡ x (mod p) for all integers x that are not divisible by p. This congruence also holds for all integers x that are divisible by p. Theorem 1.22 (Wilson’s Theorem) (p−1)!+1 is divisible by p for all prime numbers p. Proof Let p be a prime number. If x is an integer satisfying x2 ≡ 1 (mod p) then p divides (x − 1)(x + 1) and hence either p divides either x − 1 or x + 1. Thus if 1 ≤ x ≤ p − 1 and x2 ≡ 1 mod p then either x = 1 or x = p − 1. For each integer x satisfying 1 ≤ x ≤ p − 1, there exists exactly one integer y satisfying 1 ≤ y ≤ p − 1 such that xy ≡ 1 (mod p). Moreover y 6= x when 2 ≤ x ≤ p − 2. It follows that (p − 2)! is a product of numbers of the form xy, where x and y are distinct integers between 2 and p − 2 and xy ≡ 1 (mod p). It follows that (p − 2)! ≡ 1 (mod p). But then (p − 1)! ≡ p − 1 (mod p), and hence (p − 1)! + 1 ≡ 0 (mod p), as required. The following theorem of Euler generalizes Fermat’s Theorem (Theorem 1.20). Theorem 1.23 (Euler) Let m be a positive integer, and let x be an integer coprime to m. Then xϕ(m) ≡ 1 (mod m). 12

First Proof of Theorem 1.23 The result is trivially true when m = 1. Suppose that m > 1. Let I be the set of all positive integers less than m that are coprime to m. Then ϕ(m) is by definition the number of integers in I. If y is an integer coprime to m then so is xy. It follows that, to each integer j in I there exists a unique integer uj in I such that xj ≡ uj (mod m). Moreover if j ∈ I and k ∈ I and j 6= k then uj 6≡ uk . Therefore I = {uj : j ∈ I}. Thus if we multiply the left hand sides and right hand sides of the congruences xj ≡ uj (mod m) for all j ∈ I we obtain the congruence xϕ(m) z ≡ z (mod m), where z is the product of all the integers in I. But z is coprime to m, since a product of integers coprime to m is itself coprime to m. It follows from Lemma 1.11 that xϕ(m) ≡ 1 (mod m), as required. 2nd Proof of Theorem 1.23 Let m be a positive integer. Then the congruence classes modulo m of integers coprime to m constitute a group of order ϕ(m), where the group operation is multiplication of congruence classes. Now it follows from Lagrange’s Theorem that that order of any element of a finite group divides the order of the group. If we apply this result to the group of congruence classes modulo m of integers coprime to m we find that xϕ(m) ≡ 1 (mod m), as required.

1.11

Solutions of Polynomial Congruences

Let f be a polynomial with integer coefficients, and let m be a positive integer. If x and x0 are integers with x ≡ x0 (mod m) then f (x) ≡ f (x0 ) (mod m). It follows that the set of integers x satisfying the congruence f (x) ≡ 0 (mod m) is a union of congruence classes modulo m. The number of solutions modulo m of the congruence f (x) ≡ 0 (mod m) is defined to be the number of congruence classes of integers modulo m such that an integer x satisfies the congruence f (x) ≡ 0 (mod m) if and only if it belongs to one of those congruence classes. Thus a congruence f (x) ≡ 0 (mod m) has n solutions modulo m if and only if there exist n integers a1 , a2 , . . . , an satisfying the congruence such that every solution of the congruence f (x) ≡ 0 (mod m) is congruent modulo m to exactly one of the integers a1 , a2 , . . . , an . Note that the number of solutions of the congruence f (x) ≡ 0 (mod m) is equal to the number of integers x satisfying 0 ≤ x < m for which f (x) ≡ 0 (mod m). This follows immediately from the fact that each congruence class of integers modulo m contains exactly one integer x satisfying 0 ≤ x < m. Theorem 1.24 Let f be a polynomial with integer coefficients, and let p be a prime number. Suppose that the coefficients of f are not all divisible by p. Then the number of solutions modulo p of the congruence f (x) ≡ 0 (mod p) is at most the degree of the polynomial f . 13

Proof The result is clearly true when f is a constant polynomial. We can prove the result for non-constant polynomials by induction on the degree of the polynomial. First we observe that, given any integer a, there exists a polynomial g with integer coefficients such that f (x) = f (a) + (x − a)g(x). Indeed f (y + a) is a polynomial in y with integer coefficients, and therefore f (y+a) = f (a)+yh(y) for some polynomial h with integer coefficients. Thus if g(x) = h(x − a) then g is a polynomial with integer coefficients and f (x) = f (a) + (x − a)g(x). Suppose that f (a) ≡ 0 (mod p) and f (b) ≡ 0 (mod p). Let f (x) = f (a) + (x − a)g(x), where g is a polynomial with integer coefficients. The coefficients of f are not all divisible by p, but f (a) is divisible by p, and therefore the coefficients of g cannot all be divisible by p. Now f (a) and f (b) are both divisible by the prime number p, and therefore (b−a)g(b) is divisible by p. But a prime number divides a product of integers if and only if it divides one of the factors. Therefore either b − a is divisible by p or else g(b) is divisible by p. Thus either b ≡ a (mod p) or else g(b) ≡ 0 (mod p). The required result now follows easily by induction on the degree of the polynomial f .

1.12

Primitive Roots

Lemma 1.25 Let m be a positive integer, and let x be an integer coprime to m. Then there exists a positive integer n such that xn ≡ 1 (mod m). Proof There are only finitely many congruence classes modulo m. Therefore there exist positive integers j and k with j < k such that xj ≡ xk (mod m). Let n = k − j. Then xj xn ≡ xj (mod m). But xj is coprime to m. It follows from Lemma 1.11 that xn ≡ 1 (mod m). Remark The above lemma also follows directly from Euler’s Theorem (Theorem 1.23). Let m be a positive integer, and let x be an integer coprime to m. The order of the congruence class of x modulo m is by definition the smallest positive integer d such that xd ≡ 1 (mod m). Lemma 1.26 Let m be a positive integer, let x be an integer coprime to m, and let j and k be positive integers. Then xj ≡ xk (mod m) if and only if j ≡ k (mod d), where d is the order of the congruence class of x modulo m. Proof We may suppose without loss of generality that j < k. If j ≡ k (mod d) then k − j is divisible by d, and hence xk−j ≡ 1 (mod m). But then 14

xk ≡ xj xk−j ≡ xj (mod m). Conversely suppose that xj ≡ xk (mod m) and j < k. Then xj xk−j ≡ xj (mod m). But xj is coprime to m. It follows from Lemma 1.11 that xk−j ≡ 1 (mod m). Thus if k − j = qd + r, where q and r are integers and 0 ≤ r < d, then xr ≡ 1 (mod m). But then r = 0, since d is the smallest positive integer for which xd ≡ 1 (mod m). Therefore k − j is divisible by d, and thus j ≡ k (mod d). Lemma 1.27 Let p be a prime number, and let x and y be integers coprime to p. Suppose that the congruence classes of x and y modulo p have the same order. Then there exists a non-negative integer k, coprime to the order of the congruence classes of x and y, such that y ≡ xk (mod p). Proof Let d be the order of the congruence class of x modulo p. The solutions of the congruence xd ≡ 1 (mod p) include xj with 0 ≤ j < d. But the congruence xd ≡ 1 (mod p) has at most d solutions modulo p, since p is prime (Theorem 1.24), and the congruence classes of 1, x, x2 , . . . , xd−1 modulo p are distinct (Lemma 1.26). It follows that any solution of the congruence xd ≡ 1 (mod p) is congruent to xk for some positive integer k. Thus if y is an integer coprime to p whose congruence class is of order d then y ≡ xk (mod p) for some positive integer k. Moreover k is coprime to d, for if e is a common divisor of k and d then y d/e ≡ xd(k/e) ≡ 1 (mod p), and hence e = 1. Let m be a positive integer. An integer g is said to be a primitive root modulo m if, given any integer x coprime to m, there exists an integer j such that x ≡ g j (mod m). A primitive root modulo m is necessarily coprime to m. For if g is a primitive root modulo m then there exists an integer n such that g n ≡ 1 (mod m). But then any common divisor of g and m must divide 1, and thus g and m are coprime. Theorem 1.28 Let p be a prime number. Then there exists a primitive root modulo p. Proof If x is an integer coprime to p then it follows from Fermat’s Theorem (Theorem 1.20) that xp−1 ≡ 1 (mod p). It then follows from Lemma 1.26 that the order of the congruence class of x modulo p divides p − 1. For each divisor d of p − 1, let ψ(d) denote the number of congruence X classes modulo p of integers coprime to p that are of order d. Clearly ψ(d) = p − 1. d|p−1

Let x be an integer coprime to p whose congruence class is of order d, where d is a divisor of p − 1. If k is coprime to d then the congruence class of xk is also of order d, for if (xk )n ≡ 1 (mod p) then d divides kn and 15

hence d divides n (Lemma 1.10). Let y be an integer coprime to p whose congruence class is also of order d. It follows from Lemma 1.27 that there exists a non-negative integer k coprime to d such that y ≡ xk (mod p). It then follows from Lemma 1.26 that there exists a unique integer k coprime to d such that 0 ≤ k < d and y ≡ xk (mod p). Thus if there exists at least one integer x coprime to p whose congruence class modulo p is of order d then the congruence classes modulo p of integers coprime to p that are of order d are the congruence classes of xk for those integers k satisfying 0 ≤ k < d that are coprime to d. Thus if ψ(d) > 0 then ψ(d) = ϕ(d), where ϕ(d) is the number of integers k satisfying 0 ≤ k < d that are coprime X to d. Now 0 ≤ ψ(d) ≤ ϕ(d) for each divisor d of p−1. But ψ(d) = p−1 and d|p−1

X

ϕ(d) = p − 1 (Lemma 1.19). Therefore ψ(d) = ϕ(d) for each divisor d of

d|p−1

p − 1. In particular ψ(p − 1) = ϕ(p − 1) ≥ 1. Thus there exists an integer g whose congruence class modulo p is of order p − 1. The congruence classes of 1, g, g 2 , . . . g p−2 modulo p are then distinct. But there are exactly p − 1 congruence classes modulo p of integers coprime to p. It follows that any integer that is coprime to p must be congruent to g j for some non-negative integer j. Thus g is a primitive root modulo p. Corollary 1.29 Let p be a prime number. Then the group of congruence classes modulo p of integers coprime to p is a cyclic group of order p − 1. Remark It can be shown that there exists a primitive root modulo m if m = 1, 2 or 4, if m = pk or if m = 2pk , where p is some odd prime number and k is a positive integer. In all other cases there is no primitive root modulo m.

1.13

Quadratic Residues

Definition Let p be a prime number, and let x be an integer coprime to p. The integer x is said to be a quadratic residue of p if there exists an integer y such that x ≡ y 2 (mod p). If x is not a quadratic residue of p then x is said to be a quadratic non-residue of p. Proposition 1.30 Let p be an odd prime number, and let a, b and c be integers, where a is coprime to p. Then there exist integers x satisfying the congruence ax2 + bx + c ≡ 0 (mod p) if and only if either b2 − 4ac is a quadratic residue of p or else b2 − 4ac ≡ 0 mod p.

16

Proof Let x be an integer. Then ax2 + bx + c ≡ 0 (mod p) if and only if 4a2 x2 + 4abx + 4ac ≡ 0 (mod p), since 4a is coprime to p (Lemma 1.11). But 4a2 x2 + 4abx + 4ac = (2ax + b)2 − (b2 − 4ac). It follows that ax2 + bx + c ≡ 0 (mod p) if and only if (2ax + b)2 ≡ b2 − 4ac (mod p). Thus if there exist integers x satisfying the congruence ax2 + bx + c ≡ 0 (mod p) then either b2 − 4ac is a quadratic residue of p or else b2 − 4ac ≡ 0 (mod p). Conversely suppose that either b2 − 4ac is a quadratic residue of p or b2 − 4ac ≡ 0 (mod p). Then there exists an integer y such that y 2 ≡ b2 − 4ac (mod p). Also there exists an integer d such that 2ad ≡ 1 (mod p), since 2a is coprime to p (Lemma 1.12). If x ≡ d(y − b) (mod p) then 2ax + b ≡ y (mod p), and hence (2ax + b)2 ≡ b2 − 4ac (mod p). But then ax2 + bx + c ≡ 0 (mod p), as required. Lemma 1.31 Let p be an odd prime number, and let x and y be integers. Suppose that x2 ≡ y 2 (mod p). Then either x ≡ y (mod p) or else x ≡ −y (mod p). Proof x2 − y 2 is divisible by p, since x2 ≡ y 2 (mod p). But x2 − y 2 = (x − y)(x + y), and a prime number divides a product of integers if and only if it divides at least one of the factors. Therefore either x − y is divisible by p or else x + y is divisible by p. Thus either x ≡ y (mod p) or else x ≡ −y (mod p). Lemma 1.32 Let p be an odd prime number, and let m = (p − 1)/2. Then there are exactly m congruence classes of integers coprime to p that are quadratic residues of p. Also there are exactly m congruence classes of integers coprime to p that are quadratic non-residues of p. Proof If i and j are integers between 1 and m, and if i 6= j then i 6≡ j (mod p) and i 6≡ −j (mod p). It follows from Lemma 1.31 that if i and j are integers between 1 and m, and if i 6= j then i2 6≡ j 2 . Thus the congruence classes of 12 , 22 , . . . , m2 modulo p are distinct. But, given any integer x coprime to p, there is an integer i such that 1 ≤ i ≤ m and either x ≡ i (mod p) or x ≡ −i (mod p), and therefore x2 ≡ i2 (mod p). Thus every quadratic residue of p is congruent to i2 for exactly one integer i betweeen 1 and m. Thus there are m congruence classes of quadratic residues of p. There are 2m congruence classes of integers modulo p that are coprime to p. It follows that there are m congruence classes of quadratic non-residues of p, as required. Theorem 1.33 Let p be an odd prime number, let R be the set of all integers coprime to p that are quadratic residues of p, and let N be the set of all 17

integers coprime to p that are quadratic non-residues of p. If x ∈ R and y ∈ R then xy ∈ R. If x ∈ R and y ∈ N then xy ∈ N . If x ∈ N and y ∈ N then xy ∈ R. Proof Let m = (p − 1)/2. Then there are exactly m congruence classes of integers coprime to p that are quadratic residues of p. Let these congruence classes be represented by the integers r1 , r2 , . . . , rm , where ri 6≡ rj (mod p) when i 6= j. Also there are exactly m congruence classes of integers coprime to p that are quadratic non-residules modulo p. The product of two quadratic residues of p is itself a quadratic residue of p. Therefore xy ∈ R for all x ∈ R and y ∈ R. Suppose that x ∈ R. Then xri ∈ R for i = 1, 2, . . . , m, and xri 6≡ xrj when i 6= j. It follows that the congruence classes of xr1 , xr2 , . . . , xrm are distinct, and consist of quadratic residues of p. But there are exactly m congruence classes of quadratic residues of p. It follows that every quadratic residue of p is congruent to exactly one of the integers xr1 , xr2 , . . . , xrm . But if y ∈ N then y 6≡ ri and hence xy 6≡ xri for i = 1, 2, . . . , m. It follows that xy ∈ N for all x ∈ R and y ∈ N . Now suppose that x ∈ N . Then xri ∈ N for i = 1, 2, . . . , m, and xri 6≡ xrj when i 6= j. It follows that the congruence classes of xr1 , xr2 , . . . , xrm are distinct, and consist of quadratic non-residues modulo p. But there are exactly m congruence classes of quadratic non-residues modulo p. It follows that every quadratic non-residue of p is congruent to exactly one of the integers xr1 , xr2 , . . . , xrm . But if y ∈ N then y 6≡ ri and hence xy 6≡ xri for i = 1, 2, . . . , m. It follows that xy ∈ R for all x ∈ N and y ∈ N . x Let p be an odd prime number. The Legendre symbol is defined for p integers x as follows: if x is coprime to p and x is a quadratic residue of p x then = +1; if x is coprime to p and x is a quadratic non-residue of p  xp  x then = −1; if x is divisible by p then = 0. p p The following result follows directly from Theorem 1.33. Corollary 1.34 Let p be an odd prime number. Then  x  y   xy  = p p p for all integers x and y. Lemma 1.35 (Euler) Let p be an odd prime number, and let x be an integer coprime to p. Then x is a quadratic residue of p if and only if x(p−1)/2 ≡ 1 18

(mod p). Also x is a quadratic non-residue of p if and only if x(p−1)/2 ≡ −1 (mod p). Proof Let m = (p − 1)/2. If x is a quadratic residue of p then x ≡ y 2 (mod p) for some integer y coprime to p. Then xm = y p−1 , and y p−1 ≡ 1 (mod p) by Fermat’s Theorem (Theorem 1.20), and thus xm ≡ 1 (mod p). It follows from Theorem 1.24 that there are at most m congruence classes of integers x satisfying xm ≡ 1 (mod p). However all quadratic residues modulo p satisfy this congruence, and there are exactly m congruence classes of quadratic residues modulo p. It follows that an integer x coprime to p satisfies the congruence xm ≡ 1 (mod p) if and only if x is a quadratic residue of p. Now let x be a quadratic non-residue of p and let u = xm . Then u2 ≡ 1 (mod p) but u 6≡ 1 (mod p). It follows from Lemma 1.31 that u ≡ −1 (mod p). It follows that an integer x coprime to p is a quadratic residue of p if and only if xm ≡ −1 (mod p). Corollary 1.36 Let p be an odd prime number. Then x (p−1)/2 x ≡ (mod p) p for all integers x. Proof If x is coprime to p then the result follows from Lemma 1.35. If x is by p then so is x(p−1)/2 . In that case x(p−1)/2 ≡ 0 (mod p) and  xdivisible  = 0 (mod p). p Corollary 1.37

 −1  p

= (−1)(p−1)/2 for all odd prime numbers p.

 −1  ≡ (−1)(p−1)/2 (mod p) for Proof It follows from Corollary 1.36 that p  −1  = ±1, by the definition of the Legendre all odd prime numbers p. But p  −1  symbol. Therefore = (−1)(p−1)/2 , as required. p Remark Let p be an odd prime number. It follows from Theorem 1.28 that there exists a primitive root g modulo p. Moreover the congruence class of g modulo p is of order p − 1. It follows that g j ≡ g k (mod p), where j and k are positive integers, if and only if j − k is divisible by p − 1. But p − 1 is 19

even. Thus if g j ≡ g k then j − k is even. It follows easily from this that an integer x is a quadratic residue of p if and only if x ≡ g k (mod p) for some even integer k. The results of Theorem 1.33 and Lemma 1.35 follow easily from this fact. Let p be an odd prime number, and let m = (p − 1)/2. Then each integer not divisible by p is congruent to exactly one of the integers ±1, ±2, . . . , ±m. The following lemma was proved by Gauss. Lemma 1.38 Let p be an odd prime number, letm = (p − 1)/2, and let x x be an integer that is not divisible by p. Then = (−1)r , where r is the p number of pairs (j, u) of integers satisfying 1 ≤ j ≤ m and 1 ≤ u ≤ m for which xj ≡ −u (mod p). Proof For each integer j satisfying 1 ≤ j ≤ m there is a unique integer uj satisfying 1 ≤ uj ≤ m such that xj ≡ ej uj (mod p) with ej = ±1. Then e1 e2 · · · em = (−1)r . If j and k are integers between 1 and m and if j 6= k, then j 6≡ k (mod p) and j 6≡ −k (mod p). But then xj 6≡ xk (mod p) and xj 6≡ −xk (mod p) since x is not divisible by p. Thus if 1 ≤ j ≤ m, 1 ≤ k ≤ m and j 6= k then uj 6= uk . It follows that each integer between 1 and m occurs exactly once in the list u1 , u2 , . . . , um , and therefore u1 u2 · · · um = m!. Thus if we multiply the congruences xj ≡ ej uj (mod p) for j = 1, 2, . . . , m we obtain the congruence xm m! ≡ (−1)r m! (mod p). But m! is not divisible by p, since p isprime and m < p. It follows that xm  ≡ (−1)r (mod p). But x x xm ≡ (mod p) by Lemma 1.35. Therefore ≡ (−1)r (mod p), and p p x = (−1)r , as required. hence p Let n be an odd integer. Then n = 2k + 1 for some integer k. Then n = 4(k 2 + k) + 1, and k 2 + k is an even integer. It follows that if n is an 2 odd integer then n2 ≡ 1 (mod 8), and hence (−1)(n −1)/8 = ±1. 2 2 Theorem 1.39 Let p be an odd prime number. Then = (−1)(p −1)/8 . p 2

2

Proof The value of (−1)(p −1)/8 is determined by the congruence class of p 2 modulo 8. Indeed (−1)(p −1)/8 = 1 when p ≡ 1 (mod 8) or p ≡ −1 (mod 8), 2 and (−1)(p −1)/8 = −1 when p ≡ 3 (mod 8) or p ≡ −3 (mod 8). 2 = (−1)r , where Let m = (p − 1)/2. It follows from Lemma 1.38 that p r is the number of integers x between 1 and m for which 2x is not congruent 20

modulo p to any integer between 1 and m. But the integers x with this property are those for which m/2 < x ≤ m. Thus r = m/2 if m is even, and r = (m + 1)/2 if m is odd. If p ≡ 1 (mod 8) then m is divisible by 4 and hence r is even. If p ≡ 3 (mod 8) then m ≡ 1 (mod 4) and hence r is odd. If p ≡ 5 (mod 8) then m ≡ 2 (mod 4) and hence r is odd. If p ≡ 7 (mod 8) then m ≡ 3 (mod 4) 2 and hence r is even. Therefore = 1 when p ≡ 1 (mod 8) and when p ≡ 7 p 2 (mod 8), and = −1 when p ≡ 3 (mod 8) and p ≡ 5 (mod 8). Thus p 2 2 = (−1)(p −1)/8 for all odd prime numbers p, as required. p

1.14

Quadratic Reciprocity

Theorem 1.40 (Quadratic Reciprocity Law) Let p and q be distinct odd prime numbers. Then  p  q  = (−1)(p−1)(q−1)/4 q p Proof Let S be the set of all ordered pairs (x, y) of integers x and y satisfying 1 ≤ x ≤ mand 1 ≤ y ≤ n, where p = 2m + 1 and q = 2n + 1. We must p  q  prove that = (−1)mn . q p p First we show that = (−1)a , where a is the number of pairs (x, y) q of integers in S satisfying −n ≤ py − qx ≤ −1. If (x, y) is a pair of integers in S satisfying −n ≤ py − qx ≤ −1, and if z = qx − py, then 1 ≤ y ≤ n, 1 ≤ z ≤ n and py ≡ −z (mod q). On the other hand, if (y, z) is a pair of integers such that 1 ≤ y ≤ n, 1 ≤ z ≤ n and py ≡ −z (mod q) then there is a unique positive integer x such that z = qx − py. Moreover qx = py + z ≤ (p + 1)n = 2n(m + 1) and q > 2n, and therefore x < m + 1. It follows that the pair (x, y) of integers is in S, and −n ≤ py − qx ≤ −1. We deduce that the number a of pairs (x, y) of integers in S satisfying −n ≤ py − qx ≤ −1 is equal to the number of pairs (y, z) of integers satisfying 1 ≤ y ≤n,1 ≤ z ≤ n p and py ≡ −z (mod q). It now follows from Lemma 1.38 that = (−1)a . q q  Similarly = (−1)b , where b is the number of pairs (x, y) in S satisfying p 1 ≤ py − qx ≤ m. If x and y are integers satisfying py − qx = 0 then x is divisible by p and y is divisible by q. It follows from this that py − qx 6= 0 for all pairs (x, y) in 21

S. The total number of pairs (x, y) in S is mn. Therefore mn = a + b + c + d, where c is the number of pairs (x, y) in S satisfying py − qx < −n and d is the number of pairs (x, y) in S satisfying py − qx > m. Let (x, y) be a pair of integers in S, and let and let x0 = m + 1 − x and y 0 = n + 1 − y. Then the pair (x0 , y 0 ) also belongs to S, and py 0 − qx0 = m − n − (py − qx). It follows that py − qx > m if and only if py 0 − qx0 < −n. Thus there is a one-to-one correspondence between pairs (x, y) in S satisfying py − qx > m and pairs (x0 , y 0 ) in S satisfying py 0 − qx0 < −n, where (x0 , y 0 ) = (m + 1 − x, n + 1 − y) and (x, y) = (m + 1 − x0 , n + 1 − y 0 ). Therefore  p  qc= d, mn a b and thus mn = a + b + 2c. But then (−1) = (−1) (−1) = , as q p required. Corollary 1.41 Let p and  q  odd prime numbers. If p ≡ 1 (mod 4)  p q be distinct or q ≡ 1 (mod 4) then = . If p ≡ 3 (mod 4) and q ≡ 3 (mod 4) q p p q  then =− . q p Example We wish to determine whether or not 654 is a quadratic residue modulo the prime number 239. Now 654 = 2 × 239 + 176 and thus 653 ≡ 176 (mod 239). Also 176 = 16 × 11. Therefore  654   176   16  11   4 2  11   11  = = = = 239 239 239 239 239 239 239  11   239  But =− by the Law of Quadratic Reciprocity. Also 239 ≡ 8 239 11 (mod 11). Therefore  239   8   2 3 = = = (−1)3 = −1 11 11 11  654  It follows that = +1 and thus 654 is a quadratic residue of 239, as 239 required.

1.15

The Jacobi Symbol

Let s be an odd positive integer. Then s = p1 p2 · · · pm , where p1 , p2 , . . ., pm x are odd prime numbers. For each integer x we define the Jacobi symbol s by m   x Y x = s pi i=1 22

x is the product of the Legendre symbols for i = 1, 2, . . . , m.) s   pi x We define = 1. 1 Note that the Jacobi symbol can have the values 0, +1 and −1. (i.e.,

x

Lemma 1.42 Let s be an odd positive integer, and let x be an integer. Then x 6= 0 if and only if x is coprime to s. s Proof Let s = p1 p2 · · · pm , where p1 , p2 , . . . , pm are odd prime numbers. Suppose that  x x is coprime to s. Then x is coprime to each prime  x  factor of s, and hence = ±1 for i = 1, 2, . . . , m. It follows that = ±1 and thus pi s x 6= 0. s Next suppose that x is not coprime to s. Let p be a prime factor of the x greatest common divisor of x and s. Then p = pi , and hence = 0 for p i x some integer i between 1 and m. But then = 0. s Lemma 1.43 Let s be an odd positive integer, and let x and x0 be integers.  x   x0  0 Suppose that x ≡ x (mod s). Then = . s s Proof If x ≡ x0 (mod s) then x ≡ x0 (mod p) for each prime factor p of s, and  x   x0   x   x0  therefore = for each prime factor of s. Therefore = . p p s s Lemma x and y be integers, and let s and t be odd positive integers.  xy1.44  Let x  y  x   x  x  Then = and = . s s s st s t  xy   x  y  Proof = for all prime numbers p (Corollary 1.34). The p p p required result therefore follows from the definition of the Jacobi symbol.  x2  x Lemma 1.45 = 1 and = 1 for for all odd positive integers s s s2 and all integers x that are coprime to s. Proof This follows directly from Lemma 1.44 and Lemma 1.42. Theorem 1.46

 −1  s

= (−1)(s−1)/2 for all odd positive integers s.

23

 −1  Proof Let f (s) = (−1) . for each odd positive integer s. We s must prove that f (s) = 1 for all odd positive integers s. If s and t are odd positive integers then (s−1)/2

(st − 1) − (s − 1) − (t − 1) = st − s − t + 1 = (s − 1)(t − 1) But (s − 1)(t − 1) is divisible by 4, since s and t are odd positive integers. Therefore (st − 1)/2 ≡ (s − 1)/2 + (t − 1)/2 (mod 2), and hence (−1)(st−1)/2 = (−1)(s−1)/2 (−1)(t−1)/2 . It now follows from Lemma 1.44 that f (st) = f (s)f (t) for all odd numbers s and t. But f (p) = 1 for all prime numbers p, since  −1  = (−1)(p−1)/2 (Lemma 1.37). It follows that f (s) = 1 for all odd p positive integers s. as required. 2 2 Theorem 1.47 = (−1)(s −1)/8 for all odd positive integers s. s 2 2 Proof Let g(s) = (−1)(s −1)/8 . for each odd positive integer s. We must s prove that g(s) = 1 for all odd positive integers s. If s and t are odd positive integers then (s2 t2 − 1) − (s2 − 1) − (t2 − 1) = s2 t2 − s2 − t2 + 1 = (s2 − 1)(t2 − 1). But (s2 − 1)(t2 − 1) is divisible by 64, since s2 ≡ 1 (mod 8) and t2 ≡ 1 mod 8. Therefore (s2 t2 − 1)/8 ≡ (s2 − 1)/8 + (t2 − 1)/8 (mod 8), and hence 2 2 2 2 (−1)(s t −1)/8 = (−1)(s −1)/8 (−1)(t −1)/8 . It now follows from Lemma 1.44 that g(st) = g(s)g(t) for all odd numbers s and t. But g(p) = 1 for all prime 2 2 = (−1)(p −1)/8 (Lemma 1.39). It follows that g(s) = 1 numbers p, since p for all odd positive integers, as required.  s  t  Theorem 1.48 = (−1)(s−1)(t−1)/4 for all odd positive integers s t s and t.  s  t  Proof Let h(s, t) = (−1)(s−1)(t−1)/4 . We must prove that h(s, t) = 1 t s for all odd positive integers s and t. Now h(s1 s2 , t) = h(s1 , t)h(s2 , t) and h(s, t1 )h(s, t2 ) = h(s, t1 t2 ) for all odd positive integers s, s1 , s2 , t, t1 and t2 . Also h(s, t) = 1 when s and t are prime numbers by the Law of Quadratic Reciprocity (Theorem 1.40). It follows from this that h(s, t) = 1 when s is an odd positive integer and t is a prime number, since any odd positive integer is a product of odd prime numbers. But then h(s, t) = 1 for all odd positive integers s and t, as required. 24

The results proved above can be used to calculate Jacobi symbols, as in the following example. Example We wish to determine whether a quadratic  442 or not  2442 is221   residue 2  modulo the prime number 751. Now = . Also = 751 751 751 751    221 751 1, since 751 ≡ 7 (mod 8) (Theorem 1.39). Also = (Theo751 221 rem 1.48), and 751 ≡ 88 (mod 221). Thus  88   2 3  11  = = = . 751 221 221 221 221

 442 

 751 

 2  Now = −1, since 221 ≡ 5 (mod 8) (Theorem 1.47). Also it follows 221 from Theorem 1.48 that  11   221   1  = = = 1, 221 11 11  442  since 221 ≡ 1 (mod 4) and 221 ≡ 1 (mod 11). Therefore = −1, and 751 thus 442 is a quadratic non-residue of 751. The number 221 is not prime, since 221 = 13 × 17. Thus the above calculation made use of Jacobi symbols that are not Legendre symbols.

25

Course 311: Michaelmas Term 1999 Part II: Topics in Group Theory D. R. Wilkins c David R. Wilkins 1997 Copyright

Contents 2 Topics in Group Theory 2.1 Groups . . . . . . . . . . . . . . . . . . . . . 2.2 Examples of Groups . . . . . . . . . . . . . 2.3 Cayley Tables . . . . . . . . . . . . . . . . . 2.4 Elementary Properties of Groups . . . . . . 2.5 The General Associative Law . . . . . . . . 2.6 Subgroups . . . . . . . . . . . . . . . . . . . 2.7 Cyclic Groups . . . . . . . . . . . . . . . . . 2.8 Cosets and Lagrange’s Theorem . . . . . . . 2.9 Normal Subgroups and Quotient Groups . . 2.10 Homomorphisms . . . . . . . . . . . . . . . 2.11 The Isomorphism Theorems . . . . . . . . . 2.12 Direct products of groups . . . . . . . . . . 2.13 Cayley’s Theorem . . . . . . . . . . . . . . . 2.14 Group Actions, Orbits and Stabilizers . . . . 2.15 Conjugacy . . . . . . . . . . . . . . . . . . . 2.16 Permutations and the Symmetric Groups . . 2.17 The Alternating Groups . . . . . . . . . . . 2.18 Normal Subgroups of the Symmetric Groups 2.19 Finitely Generated Abelian Groups . . . . . 2.20 The Class Equation of a Finite Group . . . . 2.21 Cauchy’s Theorem . . . . . . . . . . . . . . 2.22 The Structure of p-Groups . . . . . . . . . . 2.23 The Sylow Theorems . . . . . . . . . . . . . 2.24 Solvable Groups . . . . . . . . . . . . . . . .

1

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

2 2 3 4 5 6 8 9 11 12 16 18 19 20 21 21 22 26 29 30 33 34 34 35 37

2

Topics in Group Theory

2.1

Groups

A binary operation ∗ on a set G associates to elements x and y of G a third element x ∗ y of G. For example, addition and multiplication are binary operations of the set of all integers. Definition A group G consists of a set G together with a binary operation ∗ for which the following properties are satisfied: • (x ∗ y) ∗ z = x ∗ (y ∗ z) for all elements x, y, and z of G (the Associative Law ); • there exists an element e of G (known as the identity element of G) such that e ∗ x = x = x ∗ e, for all elements x of G; • for each element x of G there exists an element x0 of G (known as the inverse of x) such that x ∗ x0 = e = x0 ∗ x (where e is the identity element of G). The order |G| of a finite group G is the number of elements of G. A group G is Abelian (or commutative) if x ∗ y = y ∗ x for all elements x and y of G. One usually adopts multiplicative notation for groups, where the product x ∗ y of two elements x and y of a group G is denoted by xy. The inverse of an element x of G is then denoted by x−1 . The identity element is usually denoted by e (or by eG when it is necessary to specify explicitly the group to which it belongs). Sometimes the identity element is denoted by 1. Thus, when multiplicative notation is adopted, the group axioms are written as follows:• (xy)z = x(yz) for all elements x, y, and z of G (the Associative Law ); • there exists an element e of G (known as the identity element of G) such that ex = x = xe, for all elements x of G; • for each element x of G there exists an element x−1 of G (known as the inverse of x) such that xx−1 = e = x−1 x (where e is the identity element of G).

2

The group G is said to be Abelian (or commutative) if xy = yx for all elements x and y of G. It is sometimes convenient or customary to use additive notation for certain groups. Here the group operation is denoted by +, the identity element of the group is denoted by 0, the inverse of an element x of the group is denoted by −x. By convention, additive notation is only used for Abelian groups. When expressed in additive notation the axioms for a Abelian group are as follows: • x + y = y + x for all elements x and y of G (the Commutative Law ); • (x+y)+z = x+(y +z) for all elements x, y, and z of G (the Associative Law ); • there exists an element 0 of G (known as the identity element or zero element of G) such that 0 + x = x = x + 0, for all elements x of G; • for each element x of G there exists an element −x of G (known as the inverse of x) such that x + (−x) = 0 = (−x) + x (where 0 is the identity element of G). We shall usually employ multiplicative notation when discussing general properties of groups. Additive notation will be employed for certain groups (such as the set of integers with the operation of addition) where this notation is the natural one to use.

2.2

Examples of Groups

The sets of integers, rational numbers, real numbers and complex numbers are Abelian groups, where the group operation is the operation of addition. The sets of non-zero rational numbers, non-zero real numbers and nonzero complex numbers are also Abelian groups, where the group operation is the operation of multiplication. For each positive integer m the set Zm of congruence classes of integers modulo m is a group, where the group operation is addition of congruence classes. For each positive integer m the set Z∗m of congruence classes modulo m of integers coprime to m is a group, where the group operation is multiplication of congruence classes. In particular, for each prime number p the set Z∗p of congruence classes modulo p of integers not divisible by p is a group, where the group operation is multiplication of congruence classes. 3

For each positive integer n the set of all nonsingular n × n matrices is a group, where the group operation is matrix multiplication. These groups are not Abelian when n ≥ 2. The set of all transformations of the plane that are of the form (x, y) 7→ (ax + by, cx + dy) with ad − bc 6= 0 is a group with respect to the operation of composition of transformations. This group includes all rotations about the origin, and all reflections in lines passing through the origin. It is not Abelian. Consider a regular n-sided polygon centered at the origin. The symmetries of this polygon (i.e., length- and angle-preserving transformations of the plane that map this polygon onto itself) are rotations about the origin through an integer multiple of 2π/n radians, and reflections in the n axes of symmetry of the polygon. The symmetries of the polygon constitute a group of order 2n. This group is referred to as the dihedral group of order 2n. The symmetries of a rectangle that is not a square constitute a group of order 4. This group consists of the identity transformation, reflection in the axis of symmetry joining the midpoints of the two shorter sides, reflection in the axis of symmetry joining the two longer sides, and rotation though an angle of π radians (180◦ ). If I denotes the identity transformation, A and B denote the reflections in the two axes of symmetry, and C denotes the rotation through π radians then A2 = B 2 = C 2 = I, AB = BA = C, AC = CA = B and BC = CB = A. This group is Abelian: it is often referred to as the Klein 4-group (or, in German, Kleinsche Viergruppe). The symmetries of a regular tetrahedron in 3-dimensional space constitute a group. Any permutation of the vertices of the tetrahedron can be effected by an appropriate symmetry of the tetrahedron. Moreover each symmetry is completely determined by the permutation of the vertices which it induces. Therefore the group of symmetries of a regular tetrahedron is of order 24, since there are 24 permutations of a set with four elements. It turns out that this group is non-Abelian.

2.3

Cayley Tables

The algebraic structure of a finite group can be exhibited using a Cayley table, provided that the number of elements in the group is sufficiently small. The rows and columns of the Cayley table are labelled by the elements of the group, and each entry in the table is the product xy of the element x labelling its row with the element y labelling its column. Example Let D6 be the group of symmetries of an equilateral triangle with vertices labelled A, B and C in anticlockwise order. The elements of D6 4

consist of the identity transformation I, an anticlockwise rotation R about the centre through an angle of 2π/3 radians (i.e., 120◦ ), a clockwise rotation S about the centre through an angle of 2π/3 radians, and reflections U, V and W in the lines joining the vertices A, B and C respectively to the midpoints of the opposite edges. Calculating the compositions of these rotations, we obtain the following Cayley table: I

R

S

U

V W

I I R S U V W R R S I W U V S S I R V W U U U V W I R S V V W U S I R W W U V R S I . Thus, for example, VU = S (i.e., the reflection U followed by the reflection V is the rotation S), and UV = R. Note that each element of the group occurs exactly once in each row and in each column in the main body of the table (excluding the labels at the left of each row and at the head of each column), This is a general property of Cayley tables of groups which can be proved easily from the group axioms.

2.4

Elementary Properties of Groups

In what follows, we describe basic properties of a group G, using multiplicative notation and denoting the identity element of the group by the letter e. Lemma 2.1 A group G has exactly one identity element e satisfying ex = x = xe for all x ∈ G. Proof Suppose that f is an element of G with the property that f x = x for all elements x of G. Then in particular f = f e = e. Similarly one can show that e is the only element of G satisfying xe = x for all elements x of G. Lemma 2.2 An element x of a group G has exactly one inverse x−1 . Proof We know from the axioms that the group G contains at least one element x−1 which satisfies xx−1 = e and x−1 x = e. If z is any element of G which satisfies xz = e then z = ez = (x−1 x)z = x−1 (xz) = x−1 e = x−1 . Similarly if w is any element of G which satisfies wx = e then w = x−1 . In particular we conclude that the inverse x−1 of x is uniquely determined, as required. 5

Lemma 2.3 Let x and y be elements of a group G. Then (xy)−1 = y −1 x−1 . Proof It follows from the group axioms that (xy)(y −1 x−1 ) = x(y(y −1 x−1 )) = x((yy −1 )x−1 ) = x(ex−1 ) = xx−1 = e. Similarly (y −1 x−1 )(xy) = e, and thus y −1 x−1 is the inverse of xy, as required. Note in particular that (x−1 )−1 = x for all elements x of a group G, since x has the properties that characterize the inverse of the inverse x−1 of x. Given an element x of a group G, we define xn for each positive integer n by the requirement that x1 = x and xn = xn−1 x for all n > 1. We also define x0 = e, where e is the identity element of the group, and we define x−n to be the inverse of xn for all positive integers n. Theorem 2.4 Let x be an element of a group G. Then xm+n = xm xn and xmn = (xm )n for all integers m and n. Proof The identity xm+n = xm xn clearly holds when m = 0 and when n = 0. The identity xm+n = xm xn can be proved for all positive integers m and n by induction on n. The identity when m and n are both negative then follows from the identity x−m−n = x−n x−m on taking inverses. The result when m and n have opposite signs can easily be deduced from that where m and n both have the same sign. The identity xmn = (xm )n follows immediately from the definitions when n = 0, 1 or −1. The result when n is positive can be proved by induction on n. The result when n is negative can then be obtained on taking inverses. If additive notation is employed for an Abelian group then the notation ‘x ’ is replaced by ‘nx’ for all integers n and elements x of the group. The analogue of Theorem 2.4 then states that (m + n)x = mx + nx and (mn)x = m(n(x)) for all integers m and n. n

2.5

The General Associative Law

Let x1 , x2 , . . . , xn be elements of a group G. We define the product x1 x2 · · · xn as follows:x1 x2 x3 = (x1 x2 )x3 x1 x2 x3 x4 = (x1 x2 x3 )x4 = ((x1 x2 )x3 )x4 x1 x2 x3 x4 x5 = (x1 x2 x3 x4 )x5 = (((x1 x2 )x3 )x4 )x5 .. . x1 x2 x3 · · · xn = (x1 x2 · · · xn−1 )xn = (· · · ((x1 x2 )x3 ) · · · xn−1 )xn . 6

(Thus if pj = x1 , x2 , . . . , xj for j = 1, 2, . . . , n then pj = pj−1 xj for each j > 1.) Now an arbitrary product of n elements of G is determined by an expression involving n elements of G together with equal numbers of left and right parentheses that determine the order in which the product is evaluated. The General Associative Law ensures that the value of such a product is determined only by the order in which the elements of the group occur within that product. Thus a product of n elements of G has the value x1 x2 · · · xn , where x1 , x2 , . . . , xn are the elements to be multiplied, listed in the order in which they occur in the expression defining the product. Example Given four elements x1 , x2 , x3 and x4 of a group, the products ((x1 x2 )x3 )x4 ,

(x1 x2 )(x3 x4 ),

(x1 (x2 x3 ))x4 ,

x1 ((x2 x3 )x4 ),

x1 (x2 (x3 x4 ))

all have the same value. (Note that x1 x2 x3 x4 is by definition the value of the first of these expressions.) The General Associative Law for products of four or more elements of a group can be verified by induction on the number on the number of elements involved. Consider a product of n elements of the group G, where n > 3. Let these elements be x1 , x2 , . . . , xn when listed in the order in which they occur in the expression for the product. Suppose also that it is known that the General Associative Law holds for all products involving fewer than n elements (i.e., any two products with fewer than n elements have the same value whenever the same elements of G occur in both products in the same order). We must show that the value of the product is x1 x2 · · · xn , where x1 x2 · · · xn = (. . . (((x1 x2 )x3 )x4 ) · · ·)xn Now the first step in evaluating the product will involve multiplying some element xr with the succeeding element xr+1 . The subsequent steps will then evaluate a product of n − 1 elements, namely the elements xi for 1 ≤ i < r, the element xr xr+1 , and the elements xi for r + 1 < i ≤ n. The validity of the General Associative Law for products of fewer than n elements then ensures that the value p of the product is given by  (x1 x2 )x3 · · · xn if r = 1;     if r = 2;  x1 (x2 x3 )x4 · · · xn if r = 3 (and n > 4); p = x1 x2 (x3 x4 )x5 · · · xn  ..    . x1 x2 · · · xn−2 (xn−1 xn ) if r = n − 1. 7

Also the General Associativity Law for products of fewer than n elements ensures that if r < n − 1 then x1 x2 · · · xr−1 (xr xr+1 ) = x1 x2 · · · xr+1 and thus p = x1 x2 · · · xn . Thus in order to verify the General Associative Law for products of n elements it only remains to verify that x1 x2 · · · xn−2 (xn−1 xn ) = x1 x2 · · · xn . The case when n = 3 is the Associative Law for products of three elements. For n > 3 let y be the product x1 x2 , · · · xn−2 of the elements x1 , x2 , . . . , xn−2 (with y = x1 x2 in the case when n = 4). Then x1 x2 · · · xn−2 (xn−1 xn ) = y(xn−1 xn ) = (yxn−1 )xn = (x1 x2 · · · xn−1 )xn = x1 x 2 · · · xn . We have thus shown that if the General Associative Law holds for all products involving fewer than n elements of the group G, then it holds for all products involving n elements of G. The validity of the General Associative Law therefore follows by induction on the number of elements occurring in the product in question. Note that the only group axiom used in verifying the General Associative Law is the Associative Law for products of three elements. It follows from this that the General Associative Law holds for any binary operation on a set that satisfies the Associative Law for products of three elements. (A set with a binary operation satisfying the Associative Law is referred to as a semigroup—the General Associative Law holds in all semigroups.)

2.6

Subgroups

Definition Let G be a group, and let H be a subset of G. We say that H is a subgroup of G if the following conditions are satisfied: • the identity element of G is an element of H; • the product of any two elements of H is itself an element of H; • the inverse of any element of H is itself an element of H. Lemma 2.5 Let x be an element of a group G. Then the set of all elements of G that are of the form xn for some integer n is a subgroup of G.

8

Proof Let H = {xn : n ∈ Z}. Then the identity element belongs to H, since it is equal to x0 . The product of two elements of H is itself an element of H, since xm xn = xm+n for all integers m and n (see Theorem 2.4). Also the inverse of an element of H is itself an element of H since (xn )−1 = x−n for all integers n. Thus H is a subgroup of G, as required. Definition Let x be an element of a group G. The order of x is the smallest positive integer n for which xn = e. The subgroup generated by x is the subgroup consisting of all elements of G that are of the form xn for some integer n. Lemma 2.6 Let H and K be subgroups of a group G. Then H ∩ K is also a subgroup of G. Proof The identity element of G belongs to H ∩ K since it belongs to the subgroups H and K. If x and y are elements of H ∩ K then xy is an element of H (since x and y are elements of H), and xy is an element of K, and therefore xy is an element of H ∩ K. Also the inverse x−1 of an element x of H ∩ K belongs to H and to K and thus belongs to H ∩ K, as required. More generally, the intersection of any collection of subgroups of a given group is itself a subgroup of that group.

2.7

Cyclic Groups

Definition A group G is said to be cyclic, with generator x, if every element of G is of the form xn for some integer n. Example The group Z of integers under addition is a cyclic group, generated by 1. Example Let n be a positive integer. The set Zn of congruence classes of integers modulo n is a cyclic group of order n with respect to the operation of addition. Example The group of all rotations of the plane about the origin through an integer multiple of 2π/n radians is a cyclic group of order n for all integers n. This group is generated by an anticlockwise rotation through an angle of 2π/n radians. Lemma 2.7 Let G be a finite cyclic group with generator x, and let j and k be integers. Then xj = xk if and only if j − k is divisible by the order of the group. 9

Proof First we show that xm = e for some strictly positive integer m, where e is the identity element of G. Now xj = xk for some integers j and k with j < k, since G is finite. Let m = k − j. Then m > 0 and xm = xk (xj )−1 = e. Let n be the smallest strictly positive integer for which xn = e. Now any integer i can be expressed in the form i = qn + r, where q and r are integers and 0 ≤ r < n. (Thus q is the greatest integer for which qn ≤ i.) Then xi = (xn )q xr = xr (since xn = e). Now the choice of n ensures that xr 6= e if 0 < r < n. It follows that an integer i satisfies xi = e if and only if n divides i. Let j and k be integers. Now xj = xk if and only if xj−k = e, since xj−k = xj (xk )−1 . It follows that xj = xk if and only if j − k is divisible by n. Moreover n is the order of the group G, since each element of G is equal to one of the elements xi with 0 ≤ i < n and these elements are distinct. We now classify all subgroups of a cyclic group G. Let x be a generator of G. Given a subgroup H of G with more than one element, let m be the smallest strictly positive integer for which xm ∈ H. Suppose that xi ∈ H for some integer i. Now i can be expressed in the form i = qm + r, where q and r are integers and 0 ≤ r < m. (Thus q is the greatest integer for which qm ≤ i.) But then xr = xi−qm = xi (xm )−q , where xi ∈ H and xm ∈ H, and therefore xr ∈ H. The choice of m now ensures that r = 0, and hence i = qm. Thus xi ∈ H if and only if i is some integer multiple of m. This shows that H is the cyclic group generated by xm , where m is the smallest strictly positive integer for which xm ∈ H. Let us consider the case when the cyclic group G is finite. Let s be the order of G. Then xs = e, and hence xs belongs to the subgroup H. It follows that s must be some integer multiple of m, where m is the smallest strictly positive integer for which xm ∈ H. Thus the subgroups of a finite cyclic group G with generator g are the trivial subgroup {e} and the cyclic subgroups generated by xm for each divisor m of the order of G. Consider now the case when the cyclic group G is infinite. For each positive integer m, the element xm generates a subgroup of G, and moreover m is the smallest strictly positive integer for which xm belongs to that subgroup. Thus if G is an infinite cyclic group with generator x then the subgroups of G are the trivial subgroup {e} and the cyclic subgroups generated by xm for each positive integer m. We have thus classified all subgroups of a cyclic group. In particular we see that any subgroup of a cyclic group is itself a cyclic group.

10

2.8

Cosets and Lagrange’s Theorem

Definition Let H be a subgroup of a group G. A left coset of H in G is a subset of G that is of the form xH, where x ∈ G and xH = {y ∈ G : y = xh for some h ∈ H}. Similarly a right coset of H in G is a subset of G that is of the form Hx, where x ∈ G and Hx = {y ∈ G : y = hx for some h ∈ H}. Note that a subgroup H of a group G is itself a left coset of H in G. Lemma 2.8 Let H be a subgroup of a group G. Then the left cosets of H in G have the following properties:— (i) x ∈ xH for all x ∈ G; (ii) if x and y are elements of G, and if y = xa for some a ∈ H, then xH = yH; (iii) if x and y are elements of G, and if xH ∩ yH is non-empty then xH = yH. Proof Let x ∈ G. Then x = xe, where e is the identity element of G. But e ∈ H. It follows that x ∈ xH. This proves (i). Let x and y be elements of G, where y = xa for some a ∈ H. Then yh = x(ah) and xh = y(a−1 h) for all h ∈ H. Moreover ah ∈ H and a−1 h ∈ H for all h ∈ H, since H is a subgroup of G. It follows that yH ⊂ xH and xH ⊂ yH, and hence xH = yH. This proves (ii). Finally suppose that xH ∩ yH is non-empty for some elements x and y of G. Let z be an element of xH ∩ yH. Then z = xa for some a ∈ H, and z = yb for some b ∈ H. It follows from (ii) that zH = xH and zH = yH. Therefore xH = yH. This proves (iii). Lemma 2.9 Let H be a finite subgroup of a group G. Then each left coset of H in G has the same number of elements as H. Proof Let H = {h1 , h2 , . . . , hm }, where h1 , h2 , . . . , hm are distinct, and let x be an element of G. Then the left coset xH consists of the elements xhj for j = 1, 2, . . . , m. Suppose that j and k are integers between 1 and m for which xhj = xhk . Then hj = x−1 (xhj ) = x−1 (xhk ) = hk , and thus j = k, since h1 , h2 , . . . , hm are distinct. It follows that the elements xh1 , xh2 , . . . , xhm are distinct. We conclude that the subgroup H and the left coset xH both have m elements, as required. 11

Theorem 2.10 (Lagrange’s Theorem) Let G be a finite group, and let H be a subgroup of G. Then the order of H divides the order of G. Proof Each element of G belongs to at least one left coset of H in G, and no element can belong to two distinct left cosets of H in G (see Lemma 2.8). Therefore every element of G belongs to exactly one left coset of H. Moreover each left coset of H contains |H| elements (Lemma 2.9). Therefore |G| = n|H|, where n is the number of left cosets of H in G. The result follows. Definition Let H be a subgroup of a group G. If the number of left cosets of H in G is finite then the number of such cosets is referred to as the index of H in G, denoted by [G: H]. The proof of Lagrange’s Theorem shows that the index [G: H] of a subgroup H of a finite group G is given by [G: H] = |G|/|H|. Corollary 2.11 Let x be an element of a finite group G. Then the order of x divides the order of G. Proof Let H be the set of all elements of G that are of the form xn for some integer n. Then H is a subgroup of G (see Lemma 2.5), and the order of H is the order of x. But the order of H divides G by Lagrange’s Theorem (Theorem 2.10). The result follows. Corollary 2.12 Any finite group of prime order is cyclic. Proof Let G be a group of prime order, and let x be some element of G that is not the identity element. Then the order of x is greater than one and divides the order of G. But then the order of x must be equal to the order of G, since the latter is a prime number. Thus G is a cyclic group generated by x, as required.

2.9

Normal Subgroups and Quotient Groups

Let A and B be subsets of a group G. The product AB of the sets A and B is defined by AB = {xy : x ∈ A and y ∈ B}. We denote {x}A and A{x} by xA and Ax, for all elements x of G and subsets A of G. The Associative Law for multiplication of elements of G ensures that (AB)C = A(BC) for all subsets A, B and C of G. We can therefore use the notation ABC to denote the products (AB)C and A(BC); 12

and we can use analogous notation to denote the product of four or more subsets of G. If A, B and C are subsets of a group G, and if A ⊂ B then clearly AC ⊂ BC and CA ⊂ CB. Note that if H is a subgroup of the group G and if x is an element of G then xH is the left coset of H in G that contains the element x. Similarly Hx is the right coset of H in G that contains the element x. If H is a subgroup of G then HH = H. Indeed HH ⊂ H, since the product of two elements of a subgroup H is itself an element of H. Also H ⊂ HH since h = eh for any element h of H, where e, the identity element of G, belongs to H. Definition A subgroup N of a group G is said to be a normal subgroup of G if xnx−1 ∈ N for all n ∈ N and x ∈ G. The notation ‘N / G’ signifies ‘N is a normal subgroup of G’. Definition A group G is said to be simple if the only normal subgroups of G are the whole of G and the trivial subgroup {e} whose only element is the identity element e of G. Lemma 2.13 Every subgroup of an Abelian group is a normal subgroup. Proof Let N be a subgroup of an Abelian group G. Then xnx−1 = (xn)x−1 = (nx)x−1 = n(xx−1 ) = ne = n for all n ∈ N and x ∈ G, where e is the identity element of G. The result follows. Example Let S3 be the group of permutations of the set {1, 2, 3}, and let H be the subgroup of S3 consisting of the identity permutation and the transposition (1 2). Then H is not normal in G, since (2 3)−1 (1 2)(2 3) = (2 3)(1 2)(2 3) = (1 3) and (1 3) does not belong to the subgroup H. Proposition 2.14 A subgroup N of a group G is a normal subgroup of G if and only if xN x−1 = N for all elements x of G. Proof Suppose that N is a normal subgroup of G. Let x be an element of G. Then xN x−1 ⊂ N . (This follows directly from the definition of a normal subgroup.) On replacing x by x−1 we see also that x−1 N x ⊂ N , and thus N = x(x−1 N x)x−1 ⊂ xN x−1 . Thus each of the sets N and xN x−1 is contained in the other, and therefore xN x−1 = N . Conversely if N is a subgroup of G with the property that xN x−1 = N for all x ∈ G, then it follows immediately from the definition of a normal subgroup that N is a normal subgroup of G. 13

Corollary 2.15 A subgroup N of a group G is a normal subgroup of G if and only if xN = N x for all elements x of G. Proof Let N be a subgroup of G, and let x be an element of G. If xN x−1 = N then xN = (xN x−1 )x = N x. Conversely if xN = N x then xN x−1 = N xx−1 = N e = N , where e is the identity element of G. Thus xN = N x if and only if xN x−1 = N . It follows from Proposition 2.14 that a subgroup N of G is normal if and only if xN = N x for all elements x of G, as required. Let N be a normal subgroup of G. Corollary 2.15 shows that a subset of G is a left coset of N in G if and only if it is a right coset of N in G. We may therefore refer to the left and right cosets of a normal subgroup N as cosets of N in G (since it is not in this case necessary to distinguish between left and right cosets). Lemma 2.16 Let N be a normal subgroup of a group G and let x and y be elements of G. Then (xN )(yN ) = (xy)N . Proof If N is a normal subgroup of G then N y = yN , and therefore (xN )(yN ) = x(N y)N = x(yN )N = (xy)(N N ). But N N = N , since N is a subgroup of G. Therefore (xN )(yN ) = (xy)N , as required. Proposition 2.17 Let G be a group, and let N be a normal subgroup of G. Then the set of all cosets of N in G is a group under the operation of multiplication. The identity element of this group is N itself, and the inverse of a coset xN is the coset x−1 N for any element x of G. Proof Let x, y and z be any elements of G. Then the product of the cosets xN and yN is the coset (xy)N . The subgroup N is itself a coset of N in G, since N = eN . Moreover (xN )N = (xN )(eN ) = (xe)N = xN, N (xN ) = (eN )(xN ) = (ex)N = xN, (xN )(x−1 N ) = (xx−1 )N = N, (x−1 N )(xN ) = (x−1 x)N = N. for all elements x of G. Thus the group axioms are satisfied. Definition Let N be a normal subgroup of a group G. The quotient group G/N is defined to be the group of cosets of N in G under the operation of multiplication. 14

Example Consider the dihedral group D8 of order 8, which we represent as the group of symmetries of a square in the plane with corners at the points whose Cartesian co-ordinates are (1, 1), (−1, 1), (−1, −1) and (1, −1). Then D8 = {I, R, R2 , R3 , T1 , T2 , T3 , T4 }, where I denotes the identity transformation, R denotes an anticlockwise rotation about the origin through a right angle, and T1 , T2 , T3 and T4 denote the reflections in the lines y = 0, x = y, x = 0 and x = −y respectively. Let N = {I, R2 }. Then N is a subgroup of D8 . The left cosets of N in D8 are N , A, B and C, where A = {R, R3 },

B = {T1 , T3 },

C = {T2 , T4 }.

Moreover N , A, B and C are also the right cosets of N in D8 , and thus N is a normal subgroup of D8 . On multiplying the cosets A, B and C with one another we find that AB = BA = C, AC = CA = B and BC = CB = A. Therefore the quotient group D8 /N is a group of order 4 with Cayley table N

A B C

N N A B C A A N C B B B C N A C C B A N . This is the Cayley table of the Klein 4-group V4 . There is an alternative approach to the construction of quotient groups which utilises the basic properties of equivalence relations. Let G be a group, and let H be a subgroup of G. Define a relation ∼H on G, where elements x and y of G satisfy x ∼H y if and only if there exists some element h of H satisfying x = yh. Now x = xe, where e, the identity element of G, is an element of H. It follows that x ∼H x for all elements x of G. Thus the relation ∼H is reflexive. If elements x and y of G satisfy x ∼H y then they also satisfy y ∼H x, for if x = yh, where h is an element of H, then y = xh−1 . Thus the relation ∼H is symmetric. If x, y and z are elements of G satisfying x ∼H y and y ∼H z then x ∼H z, for if x = yh and y = zk, where h and k belong to H, then x = zkh, and kh belongs to H. Thus the relation ∼H is transitive. We conclude that the relation ∼H is an equivalence relation. One can readily verify that its equivalence classes are the left cosets of H in G. Now suppose that the subgroup H is normal in G. Let x, y, u and v be elements of G, where x ∼H u and y ∼H v. Then there exist elements h and 15

k of H such that x = uh and y = vk. Then xy = uhvk = uv(v −1 hvk). Now v −1 hv ∈ H since h ∈ H and H is normal in G. It follows that v −1 hvk ∈ H, since the product of any two elements of a subgroup belongs to that subgroup. We deduce that if x ∼H u and y ∼H v then xy ∼H uv. Also x−1 = (uh)−1 = h−1 u−1 = u−1 (uh−1 u−1 , where uh−1 u−1 ∈ H. It follows that if x ∼H u then x−1 ∼H u−1 . Now, for any x ∈ G, let Cx denote the coset of H to which the element x belongs. Now Cx is the equivalence class of x with respect to the equivalence relation ∼H . It follows from this that elements x and u satisfy Cx = Cu if and only if x ∼H u. We conclude that if H is normal in G, and if Cx = Cu and Cy = Cv then Cxy = Cuv and Cx−1 = Cu−1 . One can deduce from this that there is a well-defined group multiplication operation on cosets of H in G, where Cx Cy is defined to be Cxy . The results just prove show that this definition of Cx Cy does not depend on the choice of x and y representing their respective cosets. The identity element is the subgroup H itself, which can be viewed as the coset containing the identity element, and the inverse of the coset Cx is the coset Cx−1 . One can readily verify that all the group axioms are satisfied and thus the set of cosets of H in G does indeed constitute a group, the quotient group G/H.

2.10

Homomorphisms

Definition A homomorphism θ: G → K from a group G to a group K is a function with the property that θ(g1 ∗ g2 ) = θ(g1 ) ∗ θ(g2 ) for all g1 , g2 ∈ G, where ∗ denotes the group operation on G and on K. Example Let q be an integer. The function from the group Z of integers to itself that sends each integer n to qn is a homomorphism. Example Let x be an element of a group G. The function that sends each integer n to the element xn is a homomorphism from the group Z of integers to G, since xm+n = xm xn for all integers m and n (Theorem 2.4). Lemma 2.18 Let θ: G → K be a homomorphism. Then θ(eG ) = eK , where eG and eK denote the identity elements of the groups G and K. Also θ(x−1 ) = θ(x)−1 for all elements x of G. Proof Let z = θ(eG ). Then z 2 = θ(eG )θ(eG ) = θ(eG eG ) = θ(eG ) = z. The result that θ(eG ) = eK now follows from the fact that an element z of K satisfies z 2 = z if and only if z is the identity element of K. Let x be an element of G. The element θ(x−1 ) satisfies θ(x)θ(x−1 ) = θ(xx−1 ) = θ(eG ) = eK , and similarly θ(x−1 )θ(x) = eK . The uniqueness of the inverse of θ(x) now ensures that θ(x−1 ) = θ(x)−1 . 16

An isomorphism θ: G → K between groups G and K is a homomorphism that is also a bijection mapping G onto K. Two groups G and K are isomorphic if there exists an isomorphism mapping G onto K. Example Let D6 be the group of symmetries of an equilateral triangle in the plane with vertices A, B and C, and let S3 be the group of permutations of the set {A, B, C}. The function which sends a symmetry of the triangle to the corresponding permutation of its vertices is an isomorphism between the dihedral group D6 of order 6 and the symmetric group S3 . Example Let R be the group of real numbers with the operation of addition, and let R+ be the group of strictly positive real numbers with the operation of multiplication. The function exp: R → R+ that sends each real number x to the positive real number ex is an isomorphism: it is both a homomorphism of groups and a bijection. The inverse of this isomorphism is the function log: R+ → R that sends each strictly positive real number to its natural logarithm. Here is some further terminology regarding homomorphisms: • A monomorphism is an injective homomorphism. • An epimorphism is a surjective homomorphism. • An endomorphism is a homomorphism mapping a group into itself. • An automorphism is an isomorphism mapping a group onto itself. Definition The kernel ker θ of the homomorphism θ: G → K is the set of all elements of G that are mapped by θ onto the identity element of K. Example Let the group operation on the set {+1, −1} be multiplication, and let θ: Z → {+1, −1} be the homomorphism that sends each integer n to (−1)n . Then the kernel of the homomorphism θ is the subgroup of Z consisting of all even numbers. Lemma 2.19 Let G and K be groups, and let θ: G → K be a homomorphism from G to K. Then the kernel ker θ of θ is a normal subgroup of G. Proof Let x and y be elements of ker θ. Then θ(x) = eK and θ(y) = eK , where eK denotes the identity element of K. But then θ(xy) = θ(x)θ(y) = eK eK = eK , and thus xy belongs to ker θ. Also θ(x−1 ) = θ(x)−1 = e−1 K = eK , and thus x−1 belongs to ker θ. We conclude that ker θ is a subgroup of K. Moreover ker θ is a normal subgroup of G, for if g ∈ G and x ∈ ker θ then θ(gxg −1 ) = θ(g)θ(x)θ(g)−1 = θ(g)θ(g −1 ) = eK . 17

If N is a normal subgroup of some group G then N is the kernel of the quotient homomorphism θ: G → G/N that sends g ∈ G to the coset gN . It follows therefore that a subset of a group G is a normal subgroup of G if and only if it is the kernel of some homomorphism. Proposition 2.20 Let G and K be groups, let θ: G → K be a homomorphism from G to K, and let N be a normal subgroup of G. Suppose that N ⊂ ker θ. Then the homomorphism θ: G → K induces a homomorphism ˆ G/N → K sending gN ∈ G/N to θ(g). Moreover θ: ˆ G/N → K is injective θ: if and only if N = ker θ. Proof Let x and y be elements of G. Now xN = yN if and only if x−1 y ∈ N . Also θ(x) = θ(y) if and only if x−1 y ∈ ker θ. Thus if N ⊂ ker θ then θ(x) = θ(y) whenever xN = yN , and thus θ: G → K induces a well-defined function ˆ G/N → K sending xN ∈ G/N to θ(x). This function is a homomorphism, θ: ˆ ˆ ˆ ˆ since θ((xN )(yN )) = θ(xyN ) = θ(xy) = θ(x)θ(y) = θ(xN )θ(yN ). Suppose now that N = ker θ. Then θ(x) = θ(y) if and only if xN = yN . ˆ G/N → K is injective. Conversely if θ: ˆ G/N → Thus the homomorphism θ: K is injective then N must be the kernel of θ, as required. Corollary 2.21 Let G and K be groups, and let θ: G → K be a homomorphism. Then θ(G) ∼ = G/ ker θ.

2.11

The Isomorphism Theorems

Lemma 2.22 Let G be a group, let H be a subgroup of G, and let N be a normal subgroup of G. Then the set HN is a subgroup of G, where HN = {hn : h ∈ H and n ∈ N }. Proof The set HN clearly contains the identity element of G. Let x and y be elements of HN . We must show that xy and x−1 belong to HN . Now x = hu and y = kv for some elements h and k of H and for some elements u and v of N . Then xy = (hk)(k −1 ukv). But k −1 uk ∈ N , since N is normal. It follows that k −1 ukv ∈ N , since N is a subgroup and k −1 ukv is the product of the elements k −1 uk and v of N . Also hk ∈ H. It follows that xy ∈ HN . We must also show that x−1 ∈ HN . Now x−1 = u−1 h−1 = h−1 (hu−1 h−1 ). Also h−1 ∈ H, since H is a subgroup of G, and hu−1 h−1 ∈ N , since N is a normal subgroup of G. It follows that x−1 ∈ HN , and thus HN is a subgroup of G, as required.

18

Theorem 2.23 (First Isomorphism Theorem) Let G be a group, let H be a subgroup of G, and let N be a normal subgroup of G. Then HN ∼ H . = N N ∩H Proof Every element of HN/N is a coset of N that is of the form hN for some h ∈ H. Thus if ϕ(h) = hN for all h ∈ H then ϕ: H → HN/N is a surjective homomorphism, and ker ϕ = N ∩ H. But ϕ(H) ∼ = H/ ker ϕ (Corollary 2.21). Therefore HN/N ∼ = H/(N ∩ H) as required. Theorem 2.24 (Second Isomorphism Theorem) Let M and N be normal subgroups of a group G, where M ⊂ N . Then G ∼ G/M . = N N/M Proof There is a well-defined homomorphism θ: G/M → G/N that sends gM to gN for all g ∈ G. Moreover the homomorphism θ is surjective, and ker θ = N/M . But θ(G/M ) ∼ = (G/M )/ ker θ (Corollary 2.21). Therefore G/N is isomorphic to (G/M ) / (N/M ), as required.

2.12

Direct products of groups

Let G1 , G2 , . . . , Gn be groups, and let G be the Cartesian product G1 × G2 × · · · × Gn of G1 , G2 , . . . , Gn (when the latter are regarded as sets). Then the elements of G are n-tuples (x1 , x2 , . . . , xn ) where xi ∈ Gi for i = 1, 2, . . . , n. We can multiply two elements of G as follows: (x1 , x2 , . . . , xn )(y1 , y2 , . . . , yn ) = (x1 y1 , x2 y2 , . . . , xn yn ). One can readily verify that G is a group with respect to this binary operation: multiplication is associative; the identity element of the group is (e1 , e2 , . . . , en ), where ei is the identity element of Gi for each i; and the in−1 −1 verse of an element (x1 , x2 , . . . , xn ) of G is (x−1 1 , x2 , . . . , xn ). We say that the group G is the direct product of the groups G1 , G2 , . . . , Gn : this direct product is (not surprisingly) denoted by G1 × G2 × · · · × Gn . Example Let C2 and C3 be cyclic groups of orders 2 and 3 respectively. Then C2 × C3 is a cyclic group of order 6, and C2 × C2 is isomorphic to the Klein 4-group whose Cayley table is I

A B C

I I A B A A I C B B C I C C B A 19

C B A I .

Let us first consider C2 × C3 . Let x and y be generators of C2 and C3 respectively, and let e and e0 denote the identity elements of C2 and C3 . Thus C2 = {e, x} and C3 = {e0 , y, y 2 }, where x2 = e and y 3 = e0 . The elements of C2 × C3 are (e, e0 ),

(e, y),

(e, y 2 ),

(x, e0 ),

(x, y),

(x, y 2 ).

Let z = (x, y). On computing the powers of z we find that z 2 = (e, y 2 ),

z 3 = (x, e0 ),

z 4 = (e, y),

z 5 = (x, y 2 ),

z 6 = (e, e0 ).

Thus 6 is the smallest positive integer n for which z n is equal to the identity element (e, e0 ) of the group. We deduce that the group C2 × C3 (which is a group of order 6) must be a cyclic group generated by the element z. Next consider C2 × C2 . This has four elements I, A, B and C, where I = (e, e), A = (e, x), B = (x, e) and C = (x, x). If we calculate the Cayley table for the group, we discover that it is that of the Klein 4-group.

2.13

Cayley’s Theorem

Theorem 2.25 (Cayley’s Theorem) Let G be a group of order n. Then G is isomorphic to a subgroup of the group Sn of permutations of a set of n elements. Proof For each element x of G, let σx : G → G be the function defined such that σx (g) = xg for all g ∈ G. Now σx−1 (σx (g)) = x−1 (xg) = (x−1 x)g = g and σx (σx−1 (g)) = x(x−1 g) = (x(x−1 )g = g for all g ∈ G. It follows that, for any x ∈ G, the function σx : G → G is a bijection whose inverse is σx−1 It follows that σx is a permutation of G for all x ∈ G, and thus the function sending an element x of G to the permutation σx is a function from G to the group of permutations of G. This function is a homomorphism. Indeed σxy = σx ◦ σy since σxy (g) = (xy)g = x(yg) = σx (σy (g)) for all g ∈ G. The homomorphism sending x ∈ G to σx is be injective, for if σx is the identity permutation then xg = g for all g ∈ G, and hence x is the identity element of G. It follows that G is isomorphic to the image of the homomorphism. This image is a subgroup {σx : x ∈ G} of the group of permutations of G. The result follows.

20

2.14

Group Actions, Orbits and Stabilizers

Definition A left action of a group G on a set X associates to each g ∈ G and x ∈ X an element g.x of X in such a way that g.(h.x) = (gh).x and 1.x = x for all g, h ∈ G and x ∈ X, where 1 denotes the identity element of G. Given a left action of a group G on a set X, the orbit of an element x of X is the subset {g.x : g ∈ G} of X, and the stabilizer of x is the subgroup {g ∈ G : g.x = x} of G. Lemma 2.26 Let G be a finite group which acts on a set X on the left. Then the orbit of an element x of X contains [G: H] elements, where [G: H] is the index of the stabilizer H of x in G. Proof There is a well-defined function θ: G/H → X defined on the set G/H of left cosets of H in G which sends gH to g.x for all g ∈ G. Moreover this function is injective, and its image is the orbit of x. The result follows.

2.15

Conjugacy

Definition Two elements h and k of a group G are said to be conjugate if k = ghg −1 for some g ∈ G. One can readily verify that the relation of conjugacy is reflexive, symmetric and transitive and is thus an equivalence relation on a group G. The equivalence classes determined by this relation are referred to as the conjugacy classes of G. A group G is the disjoint union of its conjugacy classes. Moreover the conjugacy class of the identity element of G contains no other element of G. A group G is Abelian if and only if all its conjugacy classes contain exactly one element of the group G. Definition Let G be a group. The centralizer C(h) of an element h of G is the subgroup of G defined by C(h) = {g ∈ G : gh = hg}. Lemma 2.27 Let G be a finite group, and let h ∈ G. Then the number of elements in the conjugacy class of h is equal to the index [G: C(h)] of the centralizer C(h) of h in G. Proof There is a well-defined function f : G/C(h) → G, defined on the set G/C(h) of left cosets of C(h) in G, which sends the coset gC(h) to ghg −1 for all g ∈ G. This function is injective, and its image is the conjugacy class of h. The result follows. 21

Let H be a subgroup of a group G. One can easily verify that gHg −1 is also a subgroup of G for all g ∈ G, where gHg −1 = {ghg −1 : h ∈ H}. Definition Two subgroups H and K of a group G are said to be conjugate if K = gHg −1 for some g ∈ G. The relation of conjugacy is an equivalence relation on the collection of subgroups of a given group G.

2.16

Permutations and the Symmetric Groups

A permutation of a set S is a bijective function p: S → S from S to itself. The identity permutation of a set S is the permutation that fixes every element of S. Permutations of a finite set S are conveniently represented in a two row form   x1 x2 ... xn , p(x1 ) p(x2 ) . . . p(xn ) where x1 , x2 , . . . , xn are the elements of the set S and p(x1 ), p(x2 ), . . . , p(xn ) are the images of these elements under the permutation p being represented. Thus for example   1 2 3 2 3 1 represents the permutation of the set {1, 2, 3} that sends 1 to 2, sends 2 to 3, and sends 3 to 1. Example There are two permutations ofa set {a, b} with two elements.    a b a b These are the identity permutation and the transposition a b b a that interchanges the elements a and b. Example There are six permutations These are    a b c a b , a b c a c    a b c a b , b c a c a

of a set {a, b, c}   c a b , b b a   c a b , b c b

with three elements.  c , c  c . a

Let S be a set. Then the composition of any two permutations of S is itself a permutation of S (since the composition of two bijections is a bijection). Also any permutation p of S has a well-defined inverse p−1 . (This follows 22

from the fact that the inverse of a bijection is itself a bijection.) Composition of permutations is associative: (p ◦ q) ◦ r = p ◦ (q ◦ r) for all permutations p, q and r of S. (This can be verified by noting that ((p◦q)◦r)(x) = p(q(r(x))) = (p ◦ (q ◦ r))(x) for all elements x of S.) It follows from this that the set of all permutations of a set S is a group, where the group operation is composition of permutations. Definition For each natural number n, the symmetric group Σn is the group of permutations of the set {1, 2, . . . , n}. Let S be a set, and let a1 , a2 , . . . , an be distinct elements of S. We denote by (a1 a2 · · · an ) the permutation of S that sends ai to ai+1 for i = 1, 2, . . . , n − 1, sends an to a1 , and fixes all other elements of S. Such a permutation is called a cycle of order n, or n-cycle. A cycle of length 2 is also called a transposition. (Note that evaluating a composition of cycles, we shall compose them from right to left, in accordance with standard practice when composing functions.) Example There are 24 permutations of a set {a, b, c, d} with exactly four elements. These are the following: the identity permutation that fixes every element of the set; the six transpositions (a b), (a c), (a d), (b c), (b d) and (c d); the eight 3-cycles (b c d), (b d c), (a c d), (a d c), (a b d), (a d b), (a b c) and (a c b); the six 4-cycles (a b c d), (a b d c), (a c b d), (a c d b), (a d b c) and (a d c b); and three further permutations (a b)(c d), (a c)(b d) and (a d)(b c). Two cycles (a1 a2 · · · am ) and (b1 b2 · · · bn ) are said to be disjoint when the elements a1 , a2 , . . . , am and b1 , b2 , . . . , bn are distinct (i.e., no pair of these elements coincide). It is easy to see that if (a1 a2 · · · am ) and (b1 b2 · · · bn ) are disjoint cycles then (a1 a2 · · · am )(b1 b2 · · · bn ) = (b1 b2 · · · bn )(a1 a2 · · · am ). Proposition 2.28 Any permutation of a finite set S is the identity permutation, a cycle, or a composition of two or more disjoint cycles. Proof We prove the result by induction on the number of elements in the set S. The result is trivially true if S has only one element, since in this case the only permutation of S is the identity permutation. Suppose that the result is known to be true for all permutations of sets with fewer than k elements. We show that the result then holds for all permutations of sets with k elements. 23

Let S be a set with k elements and let p be a permutation of S. Choose an element a1 of S, and let elements a2 , a3 , a4 , . . . of S be defined by the requirement that p(ai ) = ai+1 for all positive integers i. Let n be the largest positive integer for which the elements a1 , a2 , . . . , an of S are distinct. We claim that p(an ) = a1 . Now the choice of n ensures that the elements a1 , a2 , . . . , an , an+1 are not distinct. Therefore an+1 = aj for some positive integer j between 1 and n. If j were greater than one then we would have aj = p(aj−1 ) and aj = p(an ), which is impossible since if p is a permutation of S then exactly one element of S must be sent to aj by p. Therefore j = 1, and thus p(an ) = a1 . Let σ1 = (a1 a2 · · · an ). Let T be the set S \ {a1 , a2 , . . . , an } consisting of all elements of S other than a1 , a2 , . . . , an . Now a1 = p(an ), and ai = p(ai−1 ) for i = 2, 3, . . . , n. Thus if x ∈ T then p(x) 6= ai for i = 1, 2, . . . , n (since the function p: S → S is injective), and therefore p(x) ∈ T . We can therefore define a function q: T → T , where q(x) = p(x) for all x ∈ T . This function has a welldefined inverse q −1 : T → T where q −1 (x) = p−1 (x) for all x ∈ T . It follows that q: T → T is a permutation of T . The induction hypothesis ensures that this permutation is the identity permutation of T , or is a cycle, or can be expressed as a composition of two or more disjoint cyles. These cycles extend to permutations of S that fix the elements a1 , a2 , . . . , an , and these permutations of S are also cycles. It follows that either p = σ1 (and q is the identity permutation of T ), or else p = σ1 σ2 . . . σm , where σ2 , σ3 , . . . , σm are disjoint cycles of S that fix a1 , a2 , . . . , an and correspond to cycles of T . Thus if the result holds for permutations of sets with fewer than k elements, then it holds for permutations of sets with k elements. It follows by induction on k that the result holds for permutations of finite sets. Recall that a transposition is a permutation (a b) of a set S that interchanges two elements a and b of S and fixes the remaining elements. Lemma 2.29 Every permutation of a finite set with more than one element can be expressed as a finite composition of transpositions. Proof Each cycle can be expressed as a composition of transpositions. Indeed if a1 , a2 , . . . , an are distinct elements of a finite set S then (a1 a2 · · · an ) = (a1 a2 )(a2 a3 ) · · · (an−1 an ). It follows from Proposition 2.28 that a permutation of S that is not the identity permutation can be expressed as a finite composition of transpositions. Moreover the identity permutation of S can be expressed as the composition 24

of any transposition with itself, provided that S has more than one element. The result follows. Theorem 2.30 A permutation of a finite set cannot be expressed in one way as a composition of an odd number of transpositions and in another way as a composition of an even number of transpositions. Proof We can identify the finite set with the set {1, 2, . . . , n}, where n is the number of elements in the finite set. Let F : Zn → Z be theQ function sending each n-tuple (m1 , m2 , . . . , mn ) of integers to the product (mk − mj ) of 1≤j
the quantities mk − mj for all pairs (j, k) of integers satisfying 1 ≤ j < k ≤ n. Note that F (m1 , m2 , . . . , mn ) 6= 0 whenever the integers m1 , m2 , . . . , mn are distinct. If we transpose two of the integers m1 , m2 , . . . , mn then this changes the sign of the function F , since the number of factors of the product Q (mk − mj ) that change sign is odd. (Indeed if we transpose ms and 1≤j
mt , where 1 ≤ s < t < n then the factor mt − ms changes sign, the factor mt − mi becomes −(mi − ms ) and the factor mi − ms becomes −(mt − mi ) for each integer i for which s < i < t.) But any permutation σ of the set {1, 2, . . . , n} is a composition of transpositions. It follows that to each permutation σ of {1, 2, . . . , n} there corresponds a number σ , where σ = +1 or −1, such that F (mσ(1) , mσ(2) , . . . , mσ(n) ) = σ F (m1 , m2 , . . . , mn ) for all integers m1 , m2 , . . . , mn . Moreover στ = σ τ for all permutations σ and τ of the set {1, 2, . . . , n}. Also τ = −1 if the permutation τ is a transposition. It follows that if σ is expressible as a composition of r transpositions then σ = (−1)r . If σ is also expressible as a composition of s transpositions then σ = (−1)s , and hence (−1)r = (−1)s . But then r − s must be divisible by 2. The result follows. A permutation of a finite set is said to be even if it is expressible as the composition of an even number of transpositions. A permutation of a finite set is said to be odd if it is expressible as the composition of an odd number of transpositions. Any permutation of a finite set is expressible as a composition of transpositions (Lemma 2.29) and must therefore be either even or odd. However Theorem 2.30 ensures that a permutation of a finite set cannot be both even and odd. Lemma 2.31 An n-cycle is even if n is odd, and is odd if n is even. Proof An n-cycle (a1 , a2 , . . . , an ) is expressible as a composition of n − 1 transpositions, since (a1 a2 · · · an ) = (a1 a2 )(a2 a3 ) · · · (an−1 an ). 25

Thus an n-cycle is even if n − 1 is even, and is odd if n − 1 is odd. Example Let us classify the permutations of a set {a, b, c, d} of 4 elements into even and odd permutations. The identity permutation is even. The six transpositions are all odd. The eight 3-cycles are all even. The six 4cycles are all odd. The three remaining permutations (a b)(c d), (a c)(b d) and (a d)(b c) are all even. Note that there are 12 even permutations and 12 odd permutations of a set with 4 elements.

2.17

The Alternating Groups

A permutation of a finite set X is said to be even if it is the product of an even number of transpositions; it is said to be odd if it is the product of an odd number of transpositions. Note that the inverse of an even transposition and all products of even transpositions are themselves even transpositions. Definition For each integer n satisfying n > 1, the alternating group An is the subgroup of the symmetric group Σn consisting of all even permutations of the set {1, 2, . . . , n}. Note that, for each integer n satisfying n > 1, the alternating group An is a normal subgroup of Σn of index 2. Example The alternating group A3 consists of the identity permutation and the cycles (1 2 3) and (1 3 2), and is thus isomorphic to the cyclic group C3 of order 3. Lemma 2.32 Every even permutation of a finite set can be expressed as a product of cycles of order 3. Proof Let X be a finite set. Then (a b)(b c) = (a b c) and (a b)(c d) = (c a d)(a b c) for all distinct elements a, b, c and d of X. Therefore the product of any two transpositions can be expressed as a product of cycles of order 3. The result thus follows from the fact that an even permutation is the product of an even number of transpositions. Lemma 2.33 All cycles of order k in the alternating group An are conjugate to one another, provided that k ≤ n − 2. Proof Let (m1 m2 · · · mk ) be a cycle of order k in An . Then there exists a permutation ρ of {1, 2, . . . , n} with the property that ρ(i) = mi for i = 1, 2, . . . , k. If k ≤ n − 2 then any odd permutation with this property can 26

be composed with the transposition that interchanges n − 1 and n to obtain an even permutation ρ with the required property. Then (m1 m2 · · · mk ) = ρ(1 2 · · · k)ρ−1 . Thus if k ≤ n−2 then all cycles of order k in An are conjugate to (1 2 · · · k) and are therefore conjugate to one another, as required. Example We find all normal subgroups of the alternating group A4 . Let V4 = {ι, (1 2)(3 4), (1 3)(2 4), (1 4)(2 3)}, where ι is the identity permutation. If ρ is an even permutation sending i to mi for i = 1, 2, 3, 4 then ρ(1 2)(3 4)ρ−1 = (m1 m2 )(m3 m4 ). Therefore the permutations (1 2)(3 4), (1 3)(2 4) and (1 4)(2 3) are conjugate to one another, and hence V4 is a normal subgroup of A4 of order 4. The group V4 is referred to as the Klein Viergruppe. It is isomorphic to the direct product C2 × C2 of two cyclic groups of order 2. Let N be a normal subgroup of A4 that contains a cycle (m1 m2 m3 ) of order 3. Now ρ(m1 m2 m3 )ρ−1 = (ρ(m1 ) ρ(m2 ) ρ(m3 )) for all ρ ∈ A4 . Therefore any cycle in A4 of order 3 is conjugate to either (m1 m2 m3 ) or to (m1 m3 m2 ). But (m1 m3 m2 ) ∈ N , since (m1 m3 m2 ) = (m1 m2 m3 )2 . Therefore every cycle of order 3 in A4 belongs to the normal subgroup N . But then N = A4 , since A4 is generated by cycles of order 3 (Lemma 2.32). We have thus shown that if a normal subgroup N of A4 contains a cycle of order 3 then N = A4 . Now let N be a normal subgroup of A4 that does not contain any cycle of order 3. Then N ⊂ V4 , since all elements of A4 \ V4 are cycles of order 3. But the only normal subgroups of A4 that are contained in V4 are {ι} and V4 itself, since the three elements of V4 \ {ι} are conjugate to one another. We conclude that the normal subgroups of A4 are the trivial group {ι}, the Klein Viergruppe V4 and A4 itself. We recall that a group G is simple if and only if the only normal subgroups of G are G itself and the trivial subgroup whose only element is the identity element of G. The alternating group A4 is not simple. We shall prove that An is simple when n ≥ 5. Lemma 2.34 Let N be a non-trivial normal subgroup of the alternating group An , where n ≥ 5. Then there exists σ ∈ N , where σ is not the identity permutation, and a ∈ {1, 2, . . . , n} such that σ(a) = a. Proof Let X = {1, 2, . . . , n}. The proof divides into two cases, depending on whether or not the normal subgroup N contains a permutation ρ of X with the property that ρ2 is not the identity permutation. 27

Suppose that the normal subgroup N contains a permutation ρ of X with the property that ρ2 is not the identity permutation. Then there exists a ∈ X such that ρ(ρ(a)) 6= a. Let b = ρ(a) and c = ρ(b). Then the elements a, b and c are distinct. Choose elements d and e of X such that a, b, c, d and e are distinct. (This is possible since the set X has n elements, where n ≥ 5.) Let ρ0 = (c d e)ρ(c d e)−1 . Then ρ0 ∈ N (since ρ ∈ N and N is a normal subgroup), ρ0 (a) = b and ρ0 (b) = d. Now ρ0 6= ρ, since ρ0 (b) 6= ρ(b). Thus if σ = ρ−1 ρ0 then σ ∈ N , σ(a) = a, and σ is not the identity permutation. It remains to prove the result in the case where ρ2 is the identity permutation for all ρ ∈ N . In this case choose ρ ∈ N , where ρ is not the identity permutation, let a be an element of X for which ρ(a) 6= a, and let b = ρ(a). The permutation ρ is even (since it belongs to the alternating group An ), and therefore ρ cannot be the transposition (a b). It follows that there exists an element c, distinct from a and b, such that ρ(c) 6= c. Let d = ρ(c). Then the elements a, b, c and d of X are distinct. Choose an element e of X which is distinct from a, b, c and d. (This is possible since the set X has n elements, where n ≥ 5.) Let ρ0 = (c d e)ρ(c d e)−1 . Then ρ0 (a) = b and ρ0 (d) = e. Now ρ0 6= ρ, since ρ0 (d) 6= ρ(d). Thus if σ = ρ−1 ρ0 then σ ∈ N , σ(a) = a, and σ is not the identity permutation. Lemma 2.35 Let N be a normal subgroup of An , where n ≥ 5. If N contains a 3-cycle then N = An . Proof Suppose that N contains a 3-cycle. Then N contains every 3-cycle of An , since all 3-cycles in An are conjugate (Lemma 2.33). But then N contains every even permutation, since every even permutation is the identity permutation, a 3-cycle or a finite product of 3-cycles (Lemma 2.32). Thus N = An . Theorem 2.36 The alternating group An is simple when n ≥ 5. Proof First we prove that A5 is simple. Let N be a non-trivial normal subgroup of A5 . We shall show that N ∩ H is non-trivial, where H = {ρ ∈ A5 : ρ(5) = 5}. Then H is a subgroup of A5 that is isomorphic to A4 . It follows from Lemma 2.34 that there exists σ ∈ N , where σ is not the identity permutation, and a ∈ {1, 2, 3, 4, 5} such that σ(a) = a. Choose ρ ∈ A5 such that ρ(a) = 5, and let σ 0 = ρσρ−1 . Then σ 0 ∈ N and σ 0 (5) = 5, and therefore σ 0 ∈ H ∩ N . But σ 0 is not the identity permutation. Thus H ∩ N is a non-trivial normal subgroup of H. But the subgroup H of A5 is isomorphic to A4 (since each permutation of {1, 2, 3, 4} can be regarded as a permutation of {1, 2, 3, 4, 5} that fixes 5). It follows from this that H ∩ N 28

must contain the permutations (1 2)(3 4), (1 3)(2 4) and (1 4)(2 3) since the two non-trivial normal subgroups of A4 each contain these permutations. But then the normal subgroup N of A5 contains also the permutation (1 2)(4 5), since (1 2)(4 5) = (3 4 5)(1 2)(3 4)(3 4 5)−1 . It follows that N contains the cycle (3 4 5), since (3 4 5) = (1 2)(3 4)(1 2)(4 5). It follows from Lemma 2.35 that N = A5 . Thus the group A5 is simple. We now prove that An is simple for n > 5 by induction on n. Thus suppose that n > 5 and the group An−1 is simple. Let N be a non-trivial normal subgroup of An , and let H = {ρ ∈ An : ρ(n) = n}. It follows from Lemma 2.34 that there exists σ ∈ N , where σ is not the identity permutation, and a ∈ {1, 2, . . . , n} such that σ(a) = a. Choose ρ ∈ An such that ρ(a) = n, and let σ 0 = ρσρ−1 . Then σ 0 ∈ N and σ 0 (n) = n, and therefore σ 0 ∈ H ∩ N . But σ 0 is not the identity permutation. Thus H ∩ N is a non-trivial normal subgroup of H. But the subgroup H of An is simple, since it is isomorphic to An−1 . It follows that N ∩ H = H, and thus H ⊂ N . But then N contains a 3-cycle, and therefore N = An (Lemma 2.35). Thus the group An is simple. We conclude by induction on n that the group An is simple whenever n ≥ 5, as required.

2.18

Normal Subgroups of the Symmetric Groups

We can now find all normal subgroups of the symmetric groups Σn . If N is a normal subgroup of Σn then N ∩ An is a normal subgroup of An . Moreover it follows from the First Isomorphism Theorem (Theorem 2.23) that N/(N ∩ An ) ∼ = N An /An . But N An /An is a subgroup of Σn /An , and |Σn /An | = 2. Therefore either N ⊂ An or else N ∩ An is a subgroup of N of index 2. Example We show that if n ≥ 5 then the only normal subgroups of Σn are the trivial subgroup, the alternating group An and Σn itself. Now these subgroups are all normal subgroups of Σn . Moreover the trivial subgroup and An are the only normal subgroups of Σn contained in An , since An is simple when n ≥ 5 (Theorem 2.36). Let N be a normal subgroup of Σn that is not contained in An . Then N ∩ An is a normal subgroup of An . Now if N ∩ An were the trivial subgroup then N would be a subgroup of Σn of order 2. But one can readily verify that Σn contains no normal subgroup of order 2 unless n = 2, in which case A2 is itself the trivial group. It follows that N ∩ An = An , and hence N = Σn . We have therefore shown that if n ≥ 5 then the only normal subgroups of Σn are the trivial subgroup, the alternating group An and Σn itself. Example We now show that the only normal subgroups of the symmetric 29

group Σ4 are the trivial subgroup, the Klein Viergruppe V4 , the alternating group A4 and Σ4 itself. The trivial group and the groups V4 and A4 are normal subgroups of Σ4 . Moreover they are the only normal subgroups of Σ4 contained in A4 , since they are the only normal subgroups of A4 . Let N be a normal subgroup of Σ4 that is not contained in A4 . Then N ∩ A4 is a normal subgroup of A4 . One can readily verify that Σ4 contains no normal subgroup of order 2. It follows that V4 ⊂ N , since only normal subgroups of A4 other than the trivial subgroup are the groups V4 and A4 . Now the only odd permutations in Σ4 are transpositions and cycles of order 4. Moreover if N contains a cycle of order 4 then N contains a transposition, since V4 ⊂ N and (m1 m2 )(m3 m4 )(m1 m2 m3 m4 ) = (m2 m4 ) for all cycles (m1 m2 m3 m4 ) of order 4. It follows that if N is a normal subgroup of Σ4 that is not contained in A4 then N must contain at least one transposition. But then N contains all transpositions, and therefore N = Σ4 . This shows that the only normal subgroups of Σ4 are the trivial group, the Klein Viergruppe V4 , the alternating group A4 and Σ4 itself.

2.19

Finitely Generated Abelian Groups

Let H be a subgroup of the additive group Zn consisting of all n-tuples of integers, with the operation of (vector) addition. A list b1 , b2 , . . . , br of elements of Zn is said to constitute an integral basis (or Z-basis) of H if the following conditions are satisfied: • the element m1 b1 + m2 b2 + · · · + mr br belongs to H for all integers m1 , m 2 , . . . , m r ; • given any element h of H, there exist uniquely determined integers m1 , m2 , . . . , mr such that h = m1 b1 + m2 b2 + · · · + mr br . Note that elements b1 , b2 , . . . , bn of Zn constitute an integral basis of Zn if and only if every element of Zn is uniquely expressible as a linear combination of b1 , b2 , . . . , bn with integer coefficients. It follows from basic linear algebra that the rows of an n × n matrix of integers constitute an integral basis of Zn if and only if the determinant of that matrix is ±1. Theorem 2.37 Let H be a non-trivial subgroup of Zn . Then there exists an integral basis b1 , b2 , . . . , bn of Zn , a positive integer s, where s ≤ n, and positive integers k1 , k2 , . . . , ks for which k1 b1 , k2 b2 , . . . , ks bs is an integral basis of H. 30

Proof We prove the result by induction on n. The result is clearly true when n = 1, since every non-trivial subgroup of Z is of the form kZ for some positive integer k. Suppose therefore that n > 1 and that the result holds for all subgroups of Zn−1 . We must show that the result then holds for all subgroups H of Zn . Let k1 be the smallest strictly positive integer for which there exists some integral basis u1 , u2 , . . . , un of Zn and some element of H of the form m1 u1 + m2 u2 + · · · + mn un where m1 , m2 , . . . , mn are integers and mi = k1 for some integer i satisfying 1 ≤ i ≤ n. Let u1 , u2 , . . . , un be such a basis, with i = 1, and let h0 be an element of H for which h0 = m1 u1 + m2 u2 + · · · + mn un , where m1 , m2 , . . . , mn are integers and m1 = k1 . We show that each coefficient mi is divisible by k1 . Now, for each i, there exist P integers qi and ri such that mi = qi k1 + ri and 0 ≤ ri < k1 . Let b1 = u1 + ni=2 qi ui . Then b1 , u2 , . . . , un is an integral basis of Zn and h0 = k1 b1 +

n X

ri ui .

i=2

The choice of k1 now ensures that the coefficients ri cannot be strictly positive (as they are less than k1 ), and therefore ri = 0 and mi = qi k1 for i = 2, 3, . . . , n. Moreover h0 = k1 b1 . Now let ϕ: Zn−1 → Zn be the injective homomorphism sending each elePn n−1 ˜ = ϕ−1 (H). Then, ment (m2 , m3 , . . . , mn ) of Z to i=2 mi ui , and let H ˜ of Zn−1 given any element h of H, there exist an integer m and an element h ˜ Moreover m and h ˜ are uniquely determined by such that h = mb1 + ϕ(h). h, since b1 , u2 , . . . , un is an integral basis of Zn . Let m = qk1 + r, where q ˜ where ϕ(h) ˜ and r are integers and 0 ≤ r < k1 . Then h − qh0 = rb1 + ϕ(h), is expressible as a linear combination of u2 , . . . , un with integer coefficients. The choice of k1 now ensures that r cannot be strictly positive, and therefore ˜ ∈ H, and hence h ˜ ∈ H. ˜ We conclude from this that, given r = 0. Then ϕ(h) ˜ of H ˜ such any element h of H, there exist an integer q and an element h ˜ Moreover q and h ˜ are uniquely determined by h. that h = qk1 b1 + ϕ(h). Now the induction hypothesis ensures the existence of an integral basis ˜ ˜ 3, . . . , b ˜ n of Zn−1 for which there exist positive integers k2 , k3 , . . . , ks such b2 , b ˜ 2 , k3 b ˜ 3 , . . . , ks b ˜ s is an integral basis of H. ˜ i ) for each ˜ Let bi = ϕ(b that k2 b integer i between 2 and n. One can then readily verify that b1 , b2 , . . . , bn is an integral basis of Zn and k1 b1 , k2 b2 , . . . , ks bs is an integral basis of H, as required. An Abelian group G is generated by elements g1 , g2 , . . . , gn if and only if every element of G is expressible in the form g1m1 g2m2 · · · gnmn for some integers m1 , m 2 , . . . , m n . 31

Lemma 2.38 A non-trivial Abelian group G is finitely generated if and only if there exists a positive integer n and some surjective homomorphism θ: Zn → G. Proof Let e1 , e2 , . . . , en be the integral basis of Zn with e1 = (1, 0, . . . , 0), e2 = (0, 1, 0, . . . , 0), . . . , en = (0, . . . , 0, 1). If there exists a surjective homomorphism θ: Zn → G then G is generated by g1 , g2 , . . . , gn , where gi = θ(ei ) for i = 1, 2, . . . , n. Conversely if G is generated by g1 , g2 , . . . , gn then there is a surjective homomorphism θ: Zn → G that sends (m1 , m2 , . . . , mn ) ∈ Zn to g1m1 g2m2 · · · gnmn . Theorem 2.39 Let G be a non-trivial finitely generated Abelian group. Then there exist a positive integer n and a non-negative integer s between 0 and n, such that if s = 0 then G ∼ = Zn , and if s > 0 then there exist positive integers k1 , k2 , . . . , ks such that G∼ = Ck1 × Ck2 × · · · × Cks × Zn−s , where Cki is a cyclic group of order ki for i = 1, 2, . . . , s. Proof There exists a positive integer n and some surjective homomorphism θ: Zn → G, since G is finitely-generated. Let H be the kernel of θ. If H is trivial then the homomorphism θ is an isomorphism between Zn and G. If H is non-trivial then G is isomorphic to Zn /H, and there exists an integral basis b1 , b2 , . . . , bn of Zn , a positive integer s, where s ≤ n, and positive integers k1 , k2 , . . . , ks for which k1 b1 , k2 b2 , . . . , ks bs is an integral basis of H (Theorem 2.37). Then the group Zn /H, and thus G, is isomorphic to Ck1 × Ck2 × · · · × Cks × Zn−s , where Ci is a cyclic group of order ki for i = 1, 2, . . . , s. Indeed there is a well-defined homomorphism ϕ: Zn → Ck1 × Ck2 × · · · × Cks × Zn−s which sends each element m1 b1 + m2 b2 + · · · + mn bn m2 ms 1 of Zn to (am 1 , a2 , . . . , as , ms+1 , . . . , mn ), where ai is a generator of the cyclic group Ci for i = 1, 2, . . . , s. The homomorphism ϕ is surjective, and its kernel is the subgroup H. Therefore G ∼ = Zn /H ∼ = Ck1 ×Ck2 ×· · ·×Cks ×Zn−s , as required.

Corollary 2.40 Let G be a non-trivial finite Abelian group. Then there exist positive integers k1 , k2 , . . . , kn such that G ∼ = Ck1 × Ck2 × · · · × Ckn , where Cki is a cyclic group of order ki for i = 1, 2, . . . , n.

32

With some more work it is possible to show that the positive integers k1 , k2 , . . . , ks in Theorem 2.39 may be chosen such that k1 > 1 and ki−1 divides ki for i = 2, 3, . . . , s, and that the Abelian group is then determined up to isomorphism by the integer n and the sequence of positive integers k1 , k2 , . . . , k s .

2.20

The Class Equation of a Finite Group

Definition The centre Z(G) of a group G is the subgroup of G defined by Z(G) = {g ∈ G : gh = hg for all h ∈ G}. One can verify that the centre of a group G is a normal subgroup of G. Let G be a finite group, and let Z(G) be the centre of G. Then G \ Z(G) is a disjoint union of conjugacy classes. Let r be the number of conjugacy classes contained in G\Z(G), and let n1 , n2 , . . . , nr be the number of elements in these conjugacy classes. Then ni > 1 for all i, since the centre Z(G) of G is the subgroup of G consisting of those elements of G whose conjugacy class contains just one element. Now the group G is the disjoint union of its conjugacy classes, and therefore |G| = |Z(G)| + n1 + n2 + · · · + nr . This equation is referred to as the class equation of the group G. Definition Let g be an element of a group G. The centralizer C(g) of g is the subgroup of G defined by C(g) = {h ∈ G : hg = gh}. Proposition 2.41 Let G be a finite group, and let p be a prime number. Suppose that pk divides the order of G for some positive integer k. Then either pk divides the order of some proper subgroup of G, or else p divides the order of the centre of G. Proof Choose elements g1 , g2 , . . . , gr of G\Z(G), where Z(G) is the centre of G, such that each conjugacy class included in G \ Z(G) contains exactly one of these elements. Let ni be the number of elements in the conjugacy class of gi and let C(gi ) be the centralizer of gi for each i. Then C(gi ) is a proper subgroup of G, and |G| = ni |C(gi )|. Thus if pk divides |G| but does not divide the order of any proper subgroup of G then p must divide ni for i = 1, 2, . . . , r. Examination of the class equation |G| = |Z(G)| + n1 + n2 + · · · + nr now shows that p divides |Z(G)|, as required.

33

2.21

Cauchy’s Theorem

Theorem 2.42 (Cauchy) Let G be an finite group, and let p be a prime number that divides the order of G. Then G contains an element of order p. Proof We prove the result by induction on the order of G. Thus suppose that every finite group whose order is divisible by p and less than |G| contains an element of order p. If p divides the order of some proper subgroup of G then that subgroup contains the required element of order p. If p does not divide the order of any proper subgroup of G then Proposition 2.41 ensures that p divides the order of the centre Z(G) of G, and thus Z(G) cannot be a proper subgroup of G. But then G = Z(G) and the group G is Abelian. Thus let G be an Abelian group whose order is divisible by p, and let H be a proper subgroup of G that is not contained in any larger proper subgroup. If |H| is divisible by p then the induction hypothesis ensures that H contains the required element of order p, since |H| < |G|. Suppose then that |H| is not divisible by p. Choose g ∈ G \ H, and let C be the cyclic subgroup of G generated by g. Then HC = G, since HC 6= H and HC is a subgroup of G containing H. It follows from the First Isomorphism Theorem (Theorem 2.23) that G/H ∼ = C/H ∩ C. Now p divides |G/H|, since |G/H| = |G|/|H| and p divides |G| but not |H|. Therefore p divides |C|. Thus if m = |C|/p then g m is the required element of order p. This completes the proof of Cauchy’s Theorem.

2.22

The Structure of p-Groups

Definition Let p be a prime number. A p-group is a finite group whose order is some power pk of p. Lemma 2.43 Let p be a prime number, and let G be a p-group. Then there exists a normal subgroup of G of order p that is contained in the centre of G. Proof Let |G| = pk . Then pk divides the order of G but does not divide the order of any proper subgroup of G. It follows from Proposition 2.41 that p divides the order of the centre of G. It then follows from Cauchy’s Theorem (Theorem 2.42) that the centre of G contains some element of order p. This element generates a cyclic subgroup of order p, and this subgroup is normal since its elements commute with every element of G. Proposition 2.44 Let G be a p-group, where p is some prime number, and let H be a proper subgroup of G. Then there exists some subgroup K of G such that H / K and K/H is a cyclic group of order p. 34

Proof We prove the result by induction on the order of G. Thus suppose that the result holds for all p-groups whose order is less than that of G. Let Z be the centre of G. Then ZH is a well-defined subgroup of G, since Z is a normal subgroup of G. Suppose that ZH 6= H. Then H is a normal subgroup of ZH. The quotient group ZH/H is a p-group, and contains a subgroup K1 of order p (Lemma 2.43). Let K = {g ∈ ZH : gH ∈ K1 }. Then H / K and K/H ∼ = K1 , and therefore K is the required subgroup of G. Finally suppose that ZH = H. Then Z ⊂ H. Let H1 = {hZ : h ∈ H}. Then H1 is a subgroup of G/Z. But G/Z is a p-group, and |G/Z| < |G|, since |Z| > p (Lemma 2.43). The induction hypothesis ensures the existence of a subgroup K1 of G/Z such that H1 / K1 and K1 /H1 is cyclic of order p. Let K = {g ∈ G : gZ ∈ K1 }. Then H / K and K/H ∼ = K1 /H1 . Thus K is the required subgroup of G. Repeated applications of Proposition 2.44 yield the following result. Corollary 2.45 Let G be a finite group whose order is a power of some prime number p. Then there exist subgroups G0 , G1 , . . . , Gn of G, where G0 is the trivial subgroup and Gn = G, such that Gi−1 / Gi and Gi /Gi−1 is a cyclic group of order p for i = 1, 2, . . . , n.

2.23

The Sylow Theorems

Definition Let G be a finite group, and let p be a prime number dividing the order |G| of G. A p-subgroup of G is a subgroup whose order is some power of p. A Sylow p-subgroup of G is a subgroup whose order is pk , where k is the largest natural number for which pk divides |G|. Theorem 2.46 (First Sylow Theorem) Let G be a finite group, and let p be a prime number dividing the order of G. Then G contains a Sylow p-subgroup. Proof We prove the result by induction on the order of G. Thus suppose that all groups whose order is less than that of G contain the required Sylow p-subgroups. Let k be the largest positive integer for which pk divides |G|. If pk divides the order of some proper subgroup H of G then the induction hypothesis ensures that H contains the required Sylow p-subgroup of order pk . If pk does not divide the order of any proper subgroup of G then p divides the order of the centre Z(G) of G (Proposition 2.41). It follows from Cauchy’s Theorem (Theorem 2.42) that Z(G) contains an element of order p, and this element generates a normal subgroup N of G of order p. The induction hypothesis then ensures that G/N has a Sylow p-subgroup L of 35

order pk−1 , since |G/N | = |G|/p. Let K = {g ∈ G : gN ∈ L}. Then |K| = p|L| = pk , and thus K is the required Sylow p-subgroup of G. Theorem 2.47 (Second Sylow Theorem) Let G be a finite group, and let p be a prime number dividing the order of G. Then all Sylow p-subgroups of G are conjugate, and any p-subgroup of G is contained in some Sylow psubgroup of G. Moreover the number of Sylow p-subgroups in G divides the order of |G| and is congruent to 1 modulo p. Proof Let K be a Sylow p-subgroup of G, and let X be the set of left cosets of K in G. Let H be a p-subgroup of G. Then H acts on X on the left, where h(gK) = hgK for all h ∈ H and g ∈ G. Moreover h(gK) = gK if and only if g −1 hg ∈ K. Thus an element gK of X is fixed by H if and only if g −1 Hg ⊂ K. Let |G| = pk m, where k and m are positive integers and m is coprime to p. Then |K| = pk . Now the number of left cosets of K in G is |G|/|K|. Thus the set X has m elements. Now the number of elements in any orbit for the action of H on X divides the order of H, since it is the index in H of the stabilizer of some element of that orbit (Lemma 2.26). But then the number of elements in each orbit must be some power of p, since H is a p-group. Thus if an element of X is not fixed by H then the number of elements in its orbit is divisible by p. But X is a disjoint union of orbits under the action of H on X. Thus if m0 denotes the number of elements of X that are fixed by H then m − m0 is divisible by p. Now m is not divisible by p. It follows that m0 6= 0, and m0 is not divisible by p. Thus there exists at least one element g of G such that g −1 Hg ⊂ K. But then H is contained in the Sylow p-subgroup gKg −1 . Thus every p-subgroup is contained in a Sylow p-subgroup of K, and this Sylow p-subgroup is a conjugate of the given Sylow p-subgroup K. In particular any two Sylow p-subgroups are conjugate. It only remains to show that the number of Sylow p-subgroups in G divides the order of |G| and is congruent to 1 modulo p. Now choosing the p-subgroup H of G to be the Sylow p-subgroup K itself enables us to deduce that g −1 Kg = K for some g ∈ G if and only if gK is a fixed point for the action of K on X. But the number of elements g of G for which gK is a fixed point is m0 |K|, where m0 is the number of fixed points in X. It follows that the number of elements g of G for which g −1 Kg = K is pk m0 . But every Sylow p-subgroup of G is of the form g −1 Kg for some g ∈ G. It follows that the number n of Sylow p-subgroups in G is given by n = |G|/pk m0 = m/m0 . In particular n divides |G|. Now we have already shown that m − m0 is divisible by p. It follows that m0 is coprime to p, since m is coprime to p. 36

Also m − m0 is divisible by m0 , since (m − m0 )/m0 = n − 1. Putting these results together, we see that m − m0 is divisible by m0 p, and therefore n − 1 is divisible by p. Thus n divides |G| and is congruent to 1 modulo p, as required.

2.24

Solvable Groups

Definition A group G is said to be solvable (or soluble) if there exists a finite sequence G0 , G1 , . . . , Gn of subgroups of G, where G0 = {1} and Gn = G, such that Gi−1 is normal in Gi and Gi /Gi−1 is Abelian for i = 1, 2, . . . , n. Example The symmetric group Σ4 is solvable. Indeed let V4 be the Klein Viergruppe consisting of the identity permutation ι and the permutations (12)(34), (13)(24) and (14)(23), and let A4 be the alternating group consisting of all even permutations of {1, 2, 3, 4}. Then {ι} / V4 / A4 / Σ4 , V4 is Abelian, A4 /V4 is cyclic of order 3, and Σ4 /A4 is cyclic of order 2. Lemma 2.48 Let G be a group, let H1 and H2 be subgroups of G, where H1 / H2 , and let J1 = H1 ∩ N , J2 = H2 ∩ N , K1 = H1 N/N and K2 = H2 N/N , where N is some normal subgroup of G. Then J1 / J2 and K1 / K2 . Moreover there exists a normal subgroup of H2 /H1 isomorphic to J2 /J1 , and the quotient of H2 /H1 by this normal subgroup is isomorphic to K2 /K1 . Proof It is a straightforward exercise to verify that J1 / J2 and K1 / K2 . Let θ: H2 → K2 be the surjective homomorphism sending h ∈ H2 to the coset hN . Now θ induces a well-defined surjective homomorphism ψ: H2 /H1 → K2 /K1 , since θ(H1 ) ⊂ K1 . Also θ−1 (K1 ) = H2 ∩ (H1 N ). But H2 ∩ (H1 N ) = H1 (H2 ∩ N ), for if a ∈ H1 , b ∈ N and ab ∈ H2 then b ∈ H2 ∩ N . Therefore ker ψ = θ−1 (K1 )/H1 = H1 (H2 ∩ N )/H1 ∼ = H2 ∩ N/H1 ∩ N = J2 /J1 by the First Isomorphism Theorem (Theorem 2.23). Moreover the quotient of H2 /H1 by the normal subgroup ker ψ is isomorphic to the image K2 /K1 of ψ. Thus ker ψ is the required normal subgroup of H2 /H1 . Proposition 2.49 Let G be a group, and let H be a subgroup of G. Then (i) if G is solvable then any subgroup H of G is solvable; (ii) if G is solvable then G/N is solvable for any normal subgroup N of G; (iii) if N is a normal subgroup of G and if both N and G/N are solvable then G is solvable. 37

Proof Suppose that G is solvable. Let G0 , G1 , . . . , Gm be a finite sequence of subgroups of G, where G0 = {1}, Gn = G, and Gi−1 / Gi and Gi /Gi−1 is Abelian for i = 1, 2, . . . , m. We first show that the subgroup H is solvable. Let Hi = H ∩ Gi for i = 0, 1, . . . , m. Then H0 = {1} and Hm = H. If u ∈ Hi and v ∈ Hi−1 then uvu−1 ∈ H, since H is a subgroup of G. Also uvu−1 ∈ Gi−1 , since u ∈ Gi−1 , v ∈ Gi and Gi−1 is normal in Gi . Therefore uvu−1 ∈ Hi−1 . Thus Hi−1 is a normal subgroup of Hi for i = 1, 2, . . . , m. Moreover Gi ∩ H Gi−1 (Gi ∩ H) Hi = = Hi−1 Gi−1 ∩ (Gi ∩ H) Gi−1 by the First Isomorphism Theorem (Theorem 2.23), and thus Hi /Hi−1 is isomorphic to a subgroup of the Abelian group Gi /Gi−1 . It follows that Hi /Hi−1 must itself be an Abelian group. We conclude therefore that the subgroup H of G is solvable. Now let N be a normal subgroup of G, and let Ki = Gi N/N for all i. Then K0 is the trivial subgroup of G/N and Km = G/N . It follows from Lemma 2.48 that Ki−1 / Ki and Ki /Ki−1 is isomorphic to the quotient of Gi /Gi−1 by some normal subgroup. But a quotient of any Abelian group must itself be Abelian. Thus each quotient group Ki /Ki−1 is Abelian, and thus G/N is solvable. Finally suppose that G is a group, N is a normal subgroup of G and both N and G/N are solvable. We must prove that G is solvable. Now the solvability of N ensures the existence of a finite sequence G0 , G1 , . . . , Gm of subgroups of N , where G0 = {1}, Gm = N , and Gi−1 / Gi and Gi /Gi−1 is Abelian for i = 1, 2, . . . , m. Also the solvability of G/N ensures the existence of a finite sequence K0 , K1 , . . . , Kn of subgroups of G/N , where K0 = N/N , Kn = G/N , and Ki−1 / Ki and Ki /Ki−1 is Abelian for i = 1, 2, . . . , n. Let Gm+i be the preimage of Ki under the the quotient homomorphism ν: G → G/N , for i = 1, 2, . . . , n. The Second Isomorphism Theorem (Theorem 2.24) ensures that Gm+i /Gm+i−1 ∼ = Ki /Ki−1 for all i > 0. Therefore G0 , G1 , . . . , Gm+n is a finite sequence of subgroups of G, where G0 = {1}, Gn = G, and Gi−1 / Gi and Gi /Gi−1 is Abelian for i = 1, 2, . . . , m + n. Thus the group G is solvable, as required. Example The alternating group An is simple for n ≥ 5 (see Theorem 2.36). Moreover the definition of solvable groups ensures that that any simple solvable group is cyclic, and An is not cyclic when n ≥ 5. Therefore An is not solvable when n ≥ 5. It then follows from Proposition 2.49 that the symmetric group Σn is not solvable when n ≥ 5.

38

Course 311: Hilary Term 2000 Part III: Introduction to Galois Theory D. R. Wilkins

Contents 3 Introduction to Galois Theory 3.1 Rings and Fields . . . . . . . . . . . . . . . . . . . . 3.2 Ideals . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Quotient Rings and Homomorphisms . . . . . . . . . 3.4 The Characteristic of a Ring . . . . . . . . . . . . . . 3.5 Polynomial Rings . . . . . . . . . . . . . . . . . . . . 3.6 Gauss’s Lemma . . . . . . . . . . . . . . . . . . . . . 3.7 Eisenstein’s Irreducibility Criterion . . . . . . . . . . 3.8 Field Extensions and the Tower Law . . . . . . . . . 3.9 Algebraic Field Extensions . . . . . . . . . . . . . . . 3.10 Ruler and Compass Constructions . . . . . . . . . . . 3.11 Splitting Fields . . . . . . . . . . . . . . . . . . . . . 3.12 Normal Extensions . . . . . . . . . . . . . . . . . . . 3.13 Separability . . . . . . . . . . . . . . . . . . . . . . . 3.14 Finite Fields . . . . . . . . . . . . . . . . . . . . . . . 3.15 The Primitive Element Theorem . . . . . . . . . . . . 3.16 The Galois Group of a Field Extension . . . . . . . . 3.17 The Galois correspondence . . . . . . . . . . . . . . . 3.18 Quadratic Polynomials . . . . . . . . . . . . . . . . . 3.19 Cubic Polynomials . . . . . . . . . . . . . . . . . . . 3.20 Quartic Polynomials . . . . . . . . . . . . . . . . . . 3.21 The Galois group of the polynomial x4 − 2 . . . . . . 3.22 The Galois group of a polynomial . . . . . . . . . . . 3.23 Solvable polynomials and their Galois groups . . . . . 3.24 A quintic polynomial that is not solvable by radicals

1

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

2 2 4 5 7 7 10 12 12 14 16 21 24 25 27 30 31 33 35 35 36 37 39 39 43

3

Introduction to Galois Theory

3.1

Rings and Fields

Definition A ring consists of a set R on which are defined operations of addition and multiplication satisfying the following axioms: • x+y = y+x for all elements x and y of R (i.e., addition is commutative); • (x + y) + z = x + (y + z) for all elements x, y and z of R (i.e., addition is associative); • there exists an an element 0 of R (known as the zero element) with the property that x + 0 = x for all elements x of R; • given any element x of R, there exists an element −x of R with the property that x + (−x) = 0; • x(yz) = (xy)z for all elements x, y and z of R (i.e., multiplication is associative); • x(y + z) = xy + xz and (x + y)z = xz + yz for all elements x, y and z of R (the Distributive Law ). Lemma 3.1 Let R be a ring. Then x0 = 0 and 0x = 0 for all elements x of R. Proof The zero element 0 of R satisfies 0 + 0 = 0. Using the Distributive Law, we deduce that x0 + x0 = x(0 + 0) = x0 and 0x + 0x = (0 + 0)x = 0x. Thus if we add −(x0) to both sides of the identity x0 + x0 = x0 we see that x0 = 0. Similarly if we add −(0x) to both sides of the identity 0x + 0x = 0x we see that 0x = 0. Lemma 3.2 Let R be a ring. Then (−x)y = −(xy) and x(−y) = −(xy) for all elements x and y of R. Proof It follows from the Distributive Law that xy +(−x)y = (x+(−x))y = 0y = 0 and xy + x(−y) = x(y + (−y)) = x0 = 0. Therefore (−x)y = −(xy) and x(−y) = −(xy). A subset S of a ring R is said to be a subring of R if 0 ∈ S, a + b ∈ S, −a ∈ S and ab ∈ S for all a, b ∈ S. A ring R is said to be commutative if xy = yx for all x, y ∈ R. Not every ring is commutative: an example of a non-commutative ring is provided by the ring of n × n matrices with real or complex coefficients when n > 1. 2

A ring R is said to be unital if it possesses a (necessarily unique) non-zero multiplicative identity element 1 satisfying 1x = x = x1 for all x ∈ R. Definition A unital commutative ring R is said to be an integral domain if the product of any two non-zero elements of R is itself non-zero. Definition A field consists of a set K on which are defined operations of addition and multiplication satisfying the following axioms: • x+y = y+x for all elements x and y of K (i.e., addition is commutative); • (x + y) + z = x + (y + z) for all elements x, y and z of K (i.e., addition is associative); • there exists an an element 0 of K known as the zero element with the property that x + 0 = x for all elements x of K; • given any element x of K, there exists an element −x of K with the property that x + (−x) = 0; • xy = yx for all elements x and y of K (i.e., multiplication is commutative); • x(yz) = (xy)z for all elements x, y and z of K (i.e., multiplication is associative); • there exists a non-zero element 1 of K with the property that 1x = x for all elements x of K; • given any non-zero element x of K, there exists an element x−1 of K with the property that xx−1 = 1; • x(y + z) = xy + xz and (x + y)z = xz + yz for all elements x, y and z of K (the Distributive Law ). An examination of the relevant definitions shows that a unital commutative ring R is a field if and only if, given any non-zero element x of R, there exists an element x−1 of R such that xx−1 = 1. Moreover a ring R is a field if and only if the set of non-zero elements of R is an Abelian group with respect to the operation of multiplication. Lemma 3.3 A field is an integral domain.

3

Proof A field is a unital commutative ring. Let x and y be non-zero elements of a field K. Then there exist elements x−1 and y −1 of K such that xx−1 = 1 and yy −1 = 1. Then xyy −1 x−1 = 1. It follows that xy 6= 0, since 0(y −1 x−1 ) = 0 and 1 6= 0. The set Z of integers is an integral domain with respect to the usual operations of addition and multiplication. The sets Q, R and C of rational, real and complex numbers are fields.

3.2

Ideals

Definition Let R be a ring. A subset I of R is said to be an ideal of R if 0 ∈ I, a + b ∈ I, −a ∈ I, ra ∈ I and ar ∈ I for all a, b ∈ I and r ∈ R. An ideal I of R is said to be a proper ideal of R if I 6= R. Note that an ideal I of a unital ring R is proper if and only if 1 6∈ I. Indeed if 1 ∈ I then r ∈ I for all r ∈ R, since r = r1. Lemma 3.4 A unital commutative ring R is a field if and only if the only ideals of R are {0} and R. Proof Suppose that R is a field. Let I be a non-zero ideal of R. Then there exists x ∈ I satisfying x 6= 0. Moreover there exists x−1 ∈ R satisfying xx−1 = 1 = x−1 x. Therefore 1 ∈ I, and hence I = R. Thus the only ideals of R are {0} and R. Conversely, suppose that R is a unital commutative ring with the property that the only ideals of R are {0} and R. Let x be a non-zero element of R, and let Rx denote the subset of R consisting of all elements of R that are of the form rx for some r ∈ R. It is easy to verify that Rx is an ideal of R. (In order to show that yr ∈ Rx for all y ∈ Rx and r ∈ R, one must use the fact that the ring R is commutative.) Moreover Rx 6= {0}, since x ∈ Rx. We deduce that Rx = R. Therefore 1 ∈ Rx, and hence there exists some element x−1 of R satisfying x−1 x = 1. This shows that R is a field, as required. The intersection of any collection of ideals of a ring R is itself an ideal of R. For if a and b are elements of R that belong to all the ideals in the collection, then the same is true of 0, a + b, −a, ra and ar for all r ∈ R. Let X be a subset of the ring R. The ideal of R generated by X is defined to be the intersection of all the ideals of R that contain the set X. Note that this ideal is well-defined and is the smallest ideal of R containing the set X (i.e., it is contained in every other ideal that contains the set X). 4

We denote by (f1 , f2 , . . . , fk ) the ideal of R generated by any finite subset {f1 , f2 , . . . , fk } of R. We say that an ideal I of the ring R is finitely generated if there exists a finite subset of I which generates the ideal I. Lemma 3.5 Let R be a unital commutative ring, and let X be a subset of R. Then the ideal generated by X coincides with the set of all elements of R that can be expressed as a finite sum of the form r1 x1 + r2 x2 + · · · + rk xk , where x1 , x2 , . . . , xk ∈ X and r1 , r2 , . . . , rk ∈ R. Proof Let I be the subset of R consisting of all these finite sums. If J is any ideal of R which contains the set X then J must contain each of these finite sums, and thus I ⊂ J. Let a and b be elements of I. It follows immediately from the definition of I that 0 ∈ I, a + b ∈ I, −a ∈ I, and ra ∈ I for all r ∈ R. Also ar = ra, since R is commutative, and thus ar ∈ I. Thus I is an ideal of R. Moreover X ⊂ I, since the ring R is unital and x = 1x for all x ∈ X. Thus I is the smallest ideal of R containing the set X, as required. Each integer n generates an ideal nZ of the ring Z of integers. This ideal consists of those integers that are divisible by n. Lemma 3.6 Every ideal of the ring Z of integers is generated by some nonnegative integer n. Proof The zero ideal is of the required form with n = 0. Let I be some non-zero ideal of Z. Then I contains at least one strictly positive integer (since −m ∈ I for all m ∈ I). Let n be the smallest strictly positive integer belonging to I. If j ∈ I then we can write j = qn + r for some integers q and r with 0 ≤ r < n. Now r ∈ I, since r = j − qn, j ∈ I and qn ∈ I. But 0 ≤ r < n, and n is by definition the smallest strictly positive integer belonging to I. We conclude therefore that r = 0, and thus j = qn. This shows that I = nZ, as required.

3.3

Quotient Rings and Homomorphisms

Let R be a ring and let I be an ideal of R. If we regard R as an Abelian group with respect to the operation of addition, then the ideal I is a (normal) subgroup of R, and we can therefore form a corresponding quotient group R/I whose elements are the cosets of I in R. Thus an element of R/I is of the form I + x for some x ∈ R, and I + x = I + x0 if and only if x − x0 ∈ I. If

5

x, x0 , y and y 0 are elements of R satisfying I + x = I + x0 and I + y = I + y 0 then (x + y) − (x0 + y 0 ) = (x − x0 ) + (y − y 0 ), xy − x0 y 0 = xy − xy 0 + xy 0 − x0 y 0 = x(y − y 0 ) + (x − x0 )y 0 . But x − x0 and y − y 0 belong to I, and also x(y − y 0 ) and (x − x0 )y 0 belong to I, since I is an ideal. It follows that (x + y) − (x0 + y 0 ) and xy − x0 y 0 both belong to I, and thus I + x + y = I + x0 + y 0 and I + xy = I + x0 y 0 . Therefore the quotient group R/I admits well-defined operations of addition and multiplication, given by (I + x) + (I + y) = I + x + y,

(I + x)(I + y) = I + xy

for all I +x ∈ R/I and I +y ∈ R/I. One can readily verify that R/I is a ring with respect to these operations. We refer to the ring R/I as the quotient of the ring R by the ideal I. Example Let n be an integer satisfying n > 1. The quotient Z/nZ of the ring Z of integers by the ideal nZ generated by n is the ring of congruence classes of integers modulo n. This ring has n elements, and is a field if and only if n is a prime number. Definition A function ϕ: R → S from a ring R to a ring S is said to be a homomorphism (or ring homomorphism) if and only if ϕ(x+y) = ϕ(x)+ϕ(y) and ϕ(xy) = ϕ(x)ϕ(y) for all x, y ∈ R. If in addition the rings R and S are unital then a homomorphism ϕ: R → S is said to be unital if ϕ(1) = 1 (i.e., ϕ maps the identity element of R onto that of S). Let R and S be rings, and let ϕ: R → S be a ring homomorphism. Then the kernel ker ϕ of the homomorphism ϕ is an ideal of R, where ker ϕ = {x ∈ R : ϕ(x) = 0}. The image ϕ(R) of the homomorphism is a subring of S; however it is not in general an ideal of S. An ideal I of a ring R is the kernel of the quotient homomorphism that sends x ∈ R to the coset I + x. Definition An isomorphism ϕ: R → S between rings R and S is a homomorphism that is also a bijection between R and S. The inverse of an isomorphism is itself an isomorphism. Two rings are said to be isomorphic if there is an isomorphism between them. 6

The verification of the following result is a straightforward exercise. Proposition 3.7 Let ϕ: R → S be a homomorphism from a ring R to a ring S, and let I be an ideal of R satisfying I ⊂ ker ϕ. Then there exists a unique homomorphism ϕ: R/I → S such that ϕ(I + x) = ϕ(x) for all x ∈ R. Moreover ϕ: R/I → S is injective if and only if I = ker ϕ. Corollary 3.8 Let ϕ: R → S be ring homomorphism. Then ϕ(R) is isomorphic to R/ ker ϕ.

3.4

The Characteristic of a Ring

Let R be a ring, and let r ∈ R. We may define n.r for all natural numbers n by recursion on n so that 1.r = r and n.r = (n − 1).r + r for all n > 0. We define also 0.r = 0 and (−n).r = −(n.r) for all natural numbers n. Then (m + n).r = m.r + n.r, (mn).r = m.(n.r),

n.(r + s) = n.r + n.s, (m.r)(n.s) = (mn).(rs)

for all integers m an n and for all elements r and s of R. In particular, suppose that R is a unital ring. Then the set of all integers n satisfying n.1 = 0 is an ideal of Z. Therefore there exists a unique nonnegative integer p such that pZ = {n ∈ Z : n.1 = 0} (see Lemma 3.6). This integer p is referred to as the characteristic of the ring R, and is denoted by charR. Lemma 3.9 Let R be an integral domain. Then either charR = 0 or else charR is a prime number. Proof Let p = charR. Clearly p 6= 1. Suppose that p > 1 and p = jk, where j and k are positive integers. Then (j.1)(k.1) = (jk).1 = p.1 = 0. But R is an integral domain. Therefore either j.1 = 0, or k.1 = 0. But if j.1 = 0 then p divides j and therefore j = p. Similarly if k.1 = 0 then k = p. It follows that p is a prime number, as required.

3.5

Polynomial Rings

Let R be a ring. A polynomial in an indeterminate x with coefficients in the ring R is an expression f (x) of the form a0 + a1 x + a2 x 2 + a3 x 3 + · · · , 7

where the coefficients a0 , a1 , a2 , a3 , . . . of the polynomial are elements of the ring R and only finitely many of these coeffients are non-zero. If ak = 0 then the term ak xk may be omitted when writing down the expression defining the polynomial. Therefore every polynomial can therefore be represented by an expression of the form a0 + a1 x + a2 x 2 + · · · + am x m in which the number of terms is finite. If am 6= 0 then the polynomial a0 + a1 x + a2 x 2 + · · · + am x m is said to be of degree m, and the non-zero coefficient am is referred to as the leading coefficient of the polynomial. We see from the definition of a polynomial given above that each polynomial with coefficients in a ring R determines and is determined by an infinite sequence a0 , a1 , a2 , . . . of elements of the ring R, where ak is the coefficient of xk in the polynomial. An infinite sequence a0 , a1 , a2 , . . . of elements of R determines a polynomial a0 + a1 x + a2 x2 + · · · if and only if the number of values of k for which ak 6= 0 is finite. If the polynomial is non-zero then its degree is the largest value of m for which am 6= 0. One can add and multiply polynomials in the usual fashion. Thus if f (x) = a0 + a1 x + a2 x2 + a3 x3 + · · · and g(x) = b0 + b1 x + b2 x2 + b3 x3 + · · · then f (x) + g(x) = (a0 + b0 ) + (a1 + b1 )x + (a2 + b2 )x2 + (a3 + b3 )x3 + · · · , and f (x)g(x) = u0 + u1 x + u2 x2 + u3 x3 + · · · where, for each integer i, the coefficient ui of xi in f (x)g(x) is the sum of the products aj bk for all pairs (j, k) of non-negative integers satisfying j + k = i. (Thus u0 = a0 b0 , u1 = a0 b1 + a1 b0 , u2 = a0 b2 + a1 b1 + a2 b0 etc.). Straightforward calculations show that the set R[x] of polynomials with coefficients in a ring R is itself a ring with these operations of addition and multiplication. The zero element of this ring is the polynomial whose coefficients are all equal to zero. We now consider various properties of polynomials whose coefficients belong to a field K (such as the field of rational numbers, real numbers or complex numbers). 8

Lemma 3.10 Let K be a field, and let f ∈ K[x] be a non-zero polynomial with coefficients in K. Then, given any polynomial h ∈ K[x], there exist unique polynomials q and r in K[x] such that h = f q + r and either r = 0 or else deg r < deg f . Proof If deg h < deg f then we may take q = 0 and r = h. In general we prove the existence of q and r by induction on the degree deg h of h. Thus suppose that deg h ≥ deg f and that any polynomial of degree less than deg h can be expressed in the required form. Now there is some element c of K for which the polynomials h(x) and cf (x) have the same leading coefficient. Let h1 (x) = h(x) − cxm f (x), where m = deg h − deg f . Then either h1 = 0 or deg h1 < deg h. The inductive hypothesis then ensures the existence of polynomials q1 and r such that h1 = f q1 + r and either r = 0 or else deg r < deg f . But then h = f q + r, where q(x) = cxm + q1 (x). We now verify the uniqueness of q and r. Suppose that f q + r = f q + r, where q, r ∈ K[x] and either r = 0 or deg r < deg f . Then (q − q)f = r − r. But deg((q − q)f ) ≥ deg f whenever q 6= q, and deg(r − r) < deg f whenever r 6= r. Therefore the equality (q − q)f = r − r cannot hold unless q = q and r = r. This proves the uniqueness of q and r. Any polynomial f with coefficients in a field K generates an ideal (f ) of the polynomial ring K[x] consisting of all polynomials in K[x] that are divisible by f . Lemma 3.11 Let K be a field, and let I be an ideal of the polynomial ring K[x]. Then there exists f ∈ K[x] such that I = (f ), where (f ) denotes the ideal of K[x] generated by f . Proof If I = {0} then we can take f = 0. Otherwise choose f ∈ I such that f 6= 0 and the degree of f does not exceed the degree of any non-zero polynomial in I. Then, for each h ∈ I, there exist polynomials q and r in K[x] such that h = f q + r and either r = 0 or else deg r < deg f . (Lemma 3.10). But r ∈ I, since r = h − f q and h and f both belong to I. The choice of f then ensures that r = 0 and h = qf . Thus I = (f ). Definition Polynomials f1 , f2 , . . . , fk with coefficients in some field K. are said to be coprime if there is no non-constant polynomial that divides all of them. Theorem 3.12 Let f1 , f2 , . . . , fk be coprime polynomials with coefficients in some field K. Then there exist polynomials g1 , g2 , . . . , gk with coefficients in K such that f1 (x)g1 (x) + f2 (x)g2 (x) + · · · + fk (x)gk (x) = 1. 9

Proof Let I be the ideal in K[x] generated by f1 , f2 , . . . , fk . It follows from Lemma 3.11 that the ideal I is generated by some polynomial d. Then d divides all of f1 , f2 , . . . , fk and is therefore a constant polynomial, since these polynomials are coprime. It follows that I = K[x]. The existence of the required polynomials g1 , g2 , . . . , gk then follows using Lemma 3.5. Definition A non-constant polynomial f with coefficients in a ring K is said to be irreducible over K if there does not exist any non-constant polynomial that divides f whose degree is less than that of f . Proposition 3.13 Let f , g and h be polynomials with coefficients in some field K. Suppose that f is irreducible over K and that f divides the product gh. Then either f divides g or else f divides h. Proof Suppose that f does not divide g. We must show that f divides h. Now the only polynomials that divide f are constant polynomials and multiples of f . No multiple of f divides g. Therefore the only polynomials that divide both f and g are constant polynomials. Thus f and g are coprime. It follows from Proposition 3.12 that there exist polynomials u and v with coefficients in K such that 1 = ug + vf . Then h = ugh + vf h. But f divides ugh + vf h, since f divides gh. It follows that f divides h, as required. Proposition 3.14 Let K be a field, and let (f ) be the ideal of K[x] generated by an irreducible polynomial f with coefficients in K. Then K[x]/(f ) is a field. Proof Let I = (f ). Then the quotient ring K[x]/I is commutative and has a multiplicative identity element I +1. Let g ∈ K[x]. Suppose that I +g 6= I. Now the only factors of f are constant polynomials and constant multiples of f , since f is irreducible. But no constant multiple of f can divide g, since g 6∈ I. It follows that the only common factors of f and g are constant polynomials. Thus f and g are coprime. It follows from Proposition 3.12 that there exist polynomials h, k ∈ K[x] such that f h + gk = 1. But then (I +k)(I +g) = I +1 in K[x]/I, since f h ∈ I. Thus I +k is the multiplicative inverse of I + g in K[x]/I. We deduce that every non-zero element of K[x]/I is invertible, and thus K[x]/I is a field, as required.

3.6

Gauss’s Lemma

We shall show that a polynomial with integer coefficients is irreducible over Q if and only if it cannot be expressed as a product of polynomials of lower degree with integer coefficients. 10

Definition A polynomial with integer coefficients is said to be primitive if there is no prime number that divides all the coefficients of the polynomial Lemma 3.15 (Gauss’s Lemma) Let g and h be polynomials with integer coefficients. If g and h are both primitive then so is gh. Proof Let g(x) = b0 + b1 x + b2 x2 + · · · + br xr and h(x) = c0 + c1 x + c2 x2 + · · · + cs xs , and let g(x)h(x) = a0 + a1 x + a2 x2 + · · · + ar+s xr+s . Let p be a prime number. Then the polynomials g and h must both have at least one coefficient that is not divisible by p. Let j and k be the smallest values of i for which p does not divide bi and ci respectively. Then aj+k −bj ck is divisible j−1 k−1 P P by p, since aj+k − bj ck = bi cj+k−i + bj+k−i ci , where p divides bi for all i=0

i=0

i < j and p divides ci for all i < k. But p does not divide bj ck since p does not divide either bj or ck . Therefore p does not divide the coefficient aj+k of gh. This shows that the polynomial gh is primitive, as required. Proposition 3.16 A polynomial with integer coefficients is irreducible over the field Q of rational numbers if and only if it cannot be factored as a product of polynomials of lower degree with integer coefficients. Proof Let f be a polynomial with integer coefficients. If f is irreducible over Q then f clearly cannot be factored as a product of polynomials of lower degree with integer coefficients. Conversely suppose that f cannot be factored in this way. Let f (x) = g(x)h(x), where g and h are polynomials with rational coefficients. Then there exist positive integers r and s such that the polynomials rg(x) and sh(x) have integer coefficients. Let the positive integers u and v be the highest common factors of the coefficients of the polynomials rg(x) and sh(x) respectively. Then rg(x) = ug∗ (x) and sh(x) = vh∗ (x), where g∗ and h∗ are primitive polynomials with integer coefficients. Then (rs)f (x) = (uv)g∗ (x)h∗ (x). We now show that f (x) = mg∗ (x)h∗ (x) for some integer m. Let l be the smallest divisor of rs such that lf (x) = mg∗ (x)h∗ (x) for some integer m. We show that l = 1. Suppose that it were the case that l > 1. Then there would exist a prime factor p of l. Now p could not divide m, since otherwise (l/p)f (x) = (m/p)g∗ (x)h∗ (x), which contradicts the definition of l. Theorefore p would have to divide each coefficient of g∗ (x)h∗ (x), which is impossible, since it follows from Gauss’s Lemma (Lemma 3.15) that the product g∗ h∗ of the primitive polynomials g∗ and h∗ is itself a primitive polynomial. Therefore l = 1 and f (x) = mg∗ (x)h∗ (x). Now f does not factor as a product of polynomials of lower degree with integer coefficients. Therefore either deg f = deg g∗ = deg g, or else deg f = deg h∗ = deg h, Thus f is irreducible over Q, as required. 11

3.7

Eisenstein’s Irreducibility Criterion

Proposition 3.17 (Eisenstein’s Irreducibility Criterion) Let f (x) = a0 + a1 x + a2 x2 + · · · + an xn be a polynomial of degree n with integer coefficients, and let p be a prime number. Suppose that • p does not divide an , • p divides a0 , a1 , . . . , an−1 , • p2 does not divide a0 . Then the polynomial f is irreducible over the field Q of rational numbers. Proof Suppose that f (x) = g(x)h(x), where g and h are polynomials with integer coefficients. Let g(x) = b0 + b1 x + b2 x2 + · · · + br xr and h(x) = c0 +c1 x+c2 x2 +· · ·+cs xs . Then a0 = b0 c0 . Now a0 is divisible by p but is not divisible by p2 . Therefore exactly one of the coefficients b0 and c0 is divisible by p. Suppose that p divides b0 but does not divide c0 . Now p does not divide all the coefficients of g(x), since it does not divide all the coefficients of f (x). Let j be the smallest value of i for which p does not divide bi . Then p divides j−1 P bi cj−i and bi is divisible by p when i < j. But aj − bj c0 , since aj − bj c0 = i=0

bj c0 is not divisible by p, since p is prime and neither bj nor c0 is divisible by p. Therefore aj is not divisible by p, and hence j = n and deg g ≥ n = deg f . Thus deg g = deg f and deg h = 0. Thus the polynomial f does not factor as a product of polynomials of lower degree with integer coefficients, and therefore f is irreducible over Q (Proposition 3.16).

3.8

Field Extensions and the Tower Law

Let K be a field. An extension L: K of K is an embedding of K in some larger field L. Definition Let L: K and M : K be field extensions. A K-homomorphism θ: L → M is a homomorphism of fields which satisfies θ(a) = a for all a ∈ K. A K-monomorphism is an injective K-homomorphism. A K-isomorphism is a bijective K-homomorphism. A K-automorphism of L is a K-isomorphism mapping L onto itself. Two extensions L1 : K and L2 : K of a field K are said to be K-isomorphic (or isomorphic) if there exists a K-isomorphism ϕ: L1 → L2 between L1 and L2 . 12

If L: K is a field extension then we can regard L as a vector space over the field K. If L is a finite-dimensional vector space over K then we say that the extension L: K is finite. The degree [L: K] of a finite field extension L: K is defined to be the dimension of L considered as a vector space over K. Proposition 3.18 (The Tower Law) Let M : L and L: K be field extensions. Then the extension M : K is finite if and only if M : L and L: K are both finite, in which case [M : K] = [M : L][L: K]. Proof Suppose that M : K is a finite field extension. Then L, regarded as a vector space over K, is a subspace of the finite-dimensional vector space M , and therefore L is itself a finite-dimensional vector space over K. Thus L: K is finite. Also there exists a finite subset of M which spans M as a vector space over K, since M : K is finite, and this finite subset must also span M over L, and thus M : L must be finite. Conversely suppose that M : L and L: K are both finite extensions. Let x1 , x2 , . . . , xm be a basis for L, considered as a vector space over the field K, and let y1 , y2 , . . . , yn be a basis for M , considered as a vector space over the field L. Note that m = [L: K] and n = [M : L]. We claim that the set of all products xi yj with i = 1, 2, . . . , m and j = 1, 2, . . . , n is a basis for M , considered as a vector space over K. First we show that the elements xi yj are linearly independent over K. m P n P Suppose that λij xi yj = 0, where λij ∈ K for all i and j. Then i=1 j=1

m P

λij xi ∈ L for all j, and y1 , y2 , . . . , yn are linearly independent over L,

i=1

and therefore

m P

λij xi = 0 for j = 1, 2, . . . , n. But x1 , x2 , . . . , xm are linearly

i=1

independent over K. It follows that λij = 0 for all i and j. This shows that the elements xi yj are linearly independent over K. Now y1 , y2 , . . . , yn span M as a vector space over L, and therefore any n P element z of M can be written in the form z = µj yj , where µj ∈ L for j=1

all j. But each µj can be written in the form µj = for all i and j. But then z =

m P n P

m P

λij xi , where λij ∈ K

i=1

λij xi yj . This shows that the products

i=1 j=1

xi yj span M as a vector space over K, and thus {xi yj : 1 ≤ i ≤ m and 1 ≤ j ≤ n}

13

is a basis of M , considered as a vector space over K. We conclude that the extension M : K is finite, and [M : K] = mn = [M : L][L: K], as required. Let L: K be a field extension. If A is any subset of L, then the set K ∪ A generates a subfield K(A) of L which is the intersection of all subfields of L that contain K ∪ A. (Note that any intersection of subfields of L is itself a subfield of K.) We say that K(A) is the field obtained from K by adjoining the set A. We denote K({α1 , α2 , . . . , αk }) by K(α1 , α2 , . . . , αk ) for any finite subset {α1 , α2 , . . . , αk } of L. In particular K(α) denotes the field obtained by adjoining some element α of L to K. A field extension L: K is said to be simple if there exists some element α of L such that L = K(α).

3.9

Algebraic Field Extensions

Definition Let L: K be a field extension, and let α be an element of L. If there exists some non-zero polynomial f ∈ K[x] with coefficients in K such that f (α) = 0, then α is said to be algebraic over K; otherwise α is said to be transcendental over K. A field extension L: K is said to be algebraic if every element of L is algebraic over K. Lemma 3.19 A finite field extension is algebraic. Proof Let L: K be a finite field extension, and let n = [L: K]. Let α ∈ L. Then either the elements 1, α, α2 , . . . , αn are not all distinct, or else these elements are linearly dependent over the field K (since a linearly independent subset of L can have at most n elements.) Therefore there exist c0 , c1 , c2 , . . . , cn ∈ K, not all zero, such that c0 + c1 α + c2 α2 + · · · + cn αn = 0. Thus α is algebraic over K. This shows that the field extension L: K is algebraic, as required. Definition A polynomial f with coefficients in some field or unital ring is said to be monic if its leading coefficient (i.e., the coefficient of the highest power of x occurring in f (x) with a non-zero coefficient) is equal to 1.

14

Lemma 3.20 Let K be a field and let α be an element of some extension field L of K. Suppose that α is algebraic over K. Then there exists a unique irreducible monic polynomial m ∈ K[x], with coefficients in K, characterized by the following property: f ∈ K[x] satisfies f (α) = 0 if and only if m divides f in K[x]. Proof Let I = {f ∈ K[x] : f (α) = 0}. Then I is a non-zero ideal of K[x]. Now there exists some polynomial m with coefficients in K which generates the ideal I (Lemma 3.11). Moreover, by dividing m by its leading coefficient, if necessary, we can ensure that m is a monic polynomial. Then f ∈ K[x] satisfies f (α) = 0 if and only if m divides f . Suppose that m = gh where g, h ∈ K[x]. Then 0 = m(α) = g(α)h(α). But then either g(α) = 0, in which case m divides g, or else h(α) = 0, in which case m divides h. The polynomial m is thus irreducible over K. The polynomial m is uniquely determined since if some monic polynomial m also satisfies the required conditions then m and m divide one another and therefore m = m. Definition Let K be a field and let L be an extension field of K. Let α be an element of L that is algebraic over K. The minimum polynomial m of α over K is the unique irreducible monic polynomial m ∈ K[x] with coefficients in K characterized by the following property: f ∈ K[x] satisfies f (α) = 0 if and only if m divides f in K[x]. Note that if f ∈ K[x] is an irreducible monic polynomial, and if α is a root of f in some extension field L of K, then f is the minimum polynomial of α over K. Theorem 3.21 A simple field extension K(α): K is finite if and only if α is algebraic over K, in which case [K(α): K] is the degree of the minimum polynomial of α over K. Proof Suppose that the field extension K(α): K is finite. It then follows from Lemma 3.19 that α is algebraic over K. Conversely suppose that α is algebraic over K. Let R = {f (α) : f ∈ K[x]}. Now f (α) = 0 if and only if the minimum polynomial m of α over K divides f . It follows that f (α) = 0 if and only if f ∈ (m), where (m) is the ideal of K[x] generated by m. The ring homomorphism from K[x] to R that sends f ∈ K[x] to f (α) therefore induces an isomorphism between the quotient ring K[x]/(m) and the ring R. But K[x]/(m) is a field, since m is irreducible (Proposition 3.14). Therefore R is a subfield of K(α) containing K ∪ {α}, and hence R = K(α). 15

Let z ∈ K(α). Then z = g(α) for some g ∈ K[x]. But then there exist polynomials l and f belonging to K[x] such that g = lm + f and either f = 0 or deg f < deg m (Lemma 3.10). But then z = f (α) since m(α) = 0. Suppose that z = h(α) for some polynomial h ∈ K[x], where either h = 0 or deg h < deg m. Then m divides h−f , since α is a zero of h−f . But if h−f were non-zero then its degree would be less than that of m, and thus h − f would not be divisible by m. We therefore conclude that h = f . Thus any element z of K(α) can be expressed in the form z = f (α) for some uniquely determined polynomial f ∈ K[x] satisfying either f = 0 or deg f < deg m. Thus if n = deg m then 1, α, α2 . . . , αn−1 is a basis of K(α) over K. It follows that the extension K(α): K is finite and [K(α): K] = deg m, as required. Corollary 3.22 A field extension L: K is finite if and only if there exists a finite subset {α1 , α2 , . . . , αk } of L such that αi is algebraic over K for i = 1, 2, . . . , k and L = K(α1 , α2 , . . . , αk ). Proof Suppose that the field extension L: K is a finite. Then it is algebraic (Lemma 3.19). Thus if {α1 , α2 , . . . , αk } is a basis for L, considered as a vector space over K, then each αi is algebraic and L = K(α1 , α2 , . . . , αk ). Conversely suppose that L = K(α1 , α2 , . . . , αk ), where αi is algebraic over K for i = 1, 2, . . . , k. Let Ki = K(α1 , α2 , . . . , αi ) for i = 1, 2, . . . , k. Clearly Ki−1 (αi ) ⊂ Ki for all i > 1, since Ki−1 ⊂ Ki and αi ∈ Ki . Also Ki ⊂ Ki−1 (αi ), since Ki−1 (αi ) is a subfield of L containing K ∪ {α1 , α2 , . . . , αi } We deduce that Ki = Ki−1 (αi ) for i = 2, 3, . . . , k. Moreover αi is clearly algebraic over Ki−1 since it is algebraic over K, and K ⊂ Ki−1 . It follows from Theorem 3.21 that the field extension Ki : Ki−1 is finite for each i. Using the Tower Law (Proposition 3.18), we deduce that L: K is a finite extension, as required.

3.10

Ruler and Compass Constructions

One can make use of the Tower Law in order to prove the impossibility of performing a number of geometric constructions in a finite number of steps using straightedge and and compasses alone. These impossible constructions include the following: • the trisection of an arbitrary angle; • the construction of the edge of a cube having twice the volume of some given cube; • the construction of a square having the same area as a given circle. 16

Definition Let P0 and P1 be the points of the Euclidean plane given by P0 = (0, 0) and P1 = (1, 0). We say that a point P of the plane is constructible using straightedge and compasses alone if P = Pn for some finite sequence P0 , P1 , . . . , Pn of points of the plane, where P0 = (0, 0), P1 = (1, 0) and, for each j > 1, the point Pj is one of the following:— • the intersection of two distinct straight lines, each passing through at least two points belonging to the set {P0 , P1 , . . . , Pj−1 }; • the point at which a straight line joining two points belonging to the set {P0 , P1 , . . . , Pj−1 } intersects a circle which is centred on a point of this set and passes through another point of the set; • the point of intersection of two distinct circles, where each circle is centred on a point of the set {P0 , P1 , . . . , Pj−1 } and passes through another point of the set. Constructible points of the plane are those that can be constructed from the given points P0 and P1 using straightedge (i.e., unmarked ruler) and compasses alone. Theorem 3.23 Let (x, y) be a constructible point of the Euclidean plane. Then [Q(x, y): Q] = 2r for some non-negative integer r. Proof Let P = (x, y) and let P0 , P1 , . . . , Pn be a finite sequence of points of the plane with the properties listed above. Let K0 = K1 = Q and Kj = Kj−1 (xj , yj ) for j = 2, 3, . . . , n, where Pj = (xj , yj ). Straightforward coordinate geometry shows that, for each j, the real numbers xj and yj are both roots of linear or quadratic polynomials with coefficients in Kj−1 . It follows that [Kj−1 (xj ): Kj−1 ] = 1 or 2 and [Kj−1 (xj , yj ): Kj−1 (xj )] = 1 or 2 for each j. It follows from the Tower Law (Proposition 3.18) that [Kn : Q] = 2s for some non-negative integer s. But [Kn : Q] = [Kn : Q(x, y)][Q(x, y): Q]. We deduce that [Q(x, y): Q] divides 2s , and therefore [Q(x, y): Q] = 2r for some non-negative integer r. One can apply this criterion to show that there is no geometrical construction that enables one to trisect an arbitrary angle using straightedge and compasses alone. The same method can be used to show the impossibility of ‘duplicating a cube’ or ‘squaring a circle’ using straightedge and compasses alone.

17

Example We show that there is no geometrical construction for the trisection of an angle of π3 radians (i.e., 60◦ ) using straightedge and compasses alone. Let a = cos π9 and b = sin π9 . Now the point (cos π3 , sin π3 ) (i.e, the √ point ( 12 , 12 3)) is constructible. Thus if an angle of π3 radians could be trisected using straightedge and compasses alone, then the point (a, b) would be constructible. Now cos 3θ = cos θ cos 2θ − sin θ sin 2θ = cos θ(cos2 θ − sin2 θ) − 2 sin2 θ cos θ = 4 cos3 θ − 3 cos θ for any angle θ. On setting θ = π9 we deduce that 4a3 − 3a = 12 and thus 8a3 − 6a − 1 = 0. Now 8a3 − 6a − 1 = f (2a − 1), where f (x) = x3 + 3x2 − 3. An immediate application of Eisenstein’s criterion for irreducibility shows that the polynomial f is irreducible over the field Q of rational numbers, and thus [Q(a): Q] = [Q(2a − 1): Q] = 3. It now follows from Theorem 3.23 that the point (cos π9 , sin π9 ) is not constructible using straightedge and compasses alone. Therefore it is not possible to trisect an angle of π3 radians using straightedge and compasses alone. It follows that there is no geometrical construction for the trisection of an arbitrary angle using straightedge and compasses alone. Example It is not difficult to see that if it were possible to construct two √ √ 3 3 points in the plane a distance 2 apart, then the point ( 2, 0) would be constructible. But it follows from Theorem 3.23 that this is impossible, √ 3 since 2 is a root of the irreducible monic polynomial x3 − 2, and therefore √ 3 [Q( 2), Q] = 3. We conclude that there is no geometric construction using straightedge and compasses alone that will construct from a line segment in the plane a second line segment such that a cube with the second line segment as an edge will have twice the volume of a cube with the first line segment as an edge. Example It can be shown that π is not algebraic over the field Q of rational √ numbers. Therefore π is not algebraic over Q. It then follows from Theorem 3.23 it is not possible to give a geometrical construction for obtaining a square with the same area as a given circle, using straightedge and compasses alone. (Thus it is not possible to ‘square the circle’ using straightedge and compasses alone.) Lemma 3.24 If the endpoints of any line segment in the plane are constructible, then so is the midpoint.

18

Proof Let P and Q be constructible points in the plane. Let S and T be the points where the circle centred on P and passing through Q intersects the circle centred on Q and passing through P . Then S and T are constructible points in the plane, and the point R at which the line ST intersects the line P Q is the midpoint of the line segment P Q. Thus this midpoint is a constructible point. Lemma 3.25 If any three vertices of a parallelogram in the plane are constructible, then so is the fourth vertex. Proof Let the vertices of the parallelogram listed in anticlockwise (or in clockwise) order be A, B, C and D, where A, B and D are constructible points. We must show that C is also constructible. Now the midpoint E of the line segment BD is a constructible point, and the circle centred on E and passing though A will intersect the line AE in the point C. Thus C is a constructible point, as required. Theorem 3.26 Let K denote the set of all real numbers x for which the point (x, 0) is constructible using straightedge and compasses alone. Then K is a subfield of the field of real numbers, and a point (x, y) of the plane is constructible using straightedge and compass √ alone if and only if x ∈ K and y ∈ K. Moreover if x ∈ K and x > 0 then x ∈ K. Proof Clearly 0 ∈ K and 1 ∈ K. Let x and y be real numbers belonging to K. Then (x, 0) and (y, 0) are constructible points of the plane. Let M be the midpoint of the line segment whose endpoints are (x, 0) and (y, 0). Then M is constructible (Lemma 3.24), and M = ( 21 (x + y), 0). The circle centred on M and passing through the origin intersects the x-axis at the origin and at the point (x + y, 0). Therefore (x + y, 0) is a constructible point, and thus x + y ∈ K. Also the circle centred on the origin and passing through (x, 0) intersects the x-axis at (−x, 0). Thus (−x, 0) is a constructible point, and thus −x ∈ K. We claim that if x ∈ K then the point (0, x) is constructible. Now if x ∈ K and x 6= 0 then (x, 0) and (−x, 0) are constructible points, and the circle centred on (x, 0) and passing through (−x, 0) intersects the circle centred on (−x, 0) and passing through (x, 0) in two √ √ points that lie on the y-axis. These two points (namely (0, 3x) and (0, − 3x)) are constructible, and therefore the circle centred on the origin and passing though (x, 0) intersects the y-axis in two constructible points which are (0, x) and (0, −x). Thus if x ∈ K then the point (0, x) is constructible. Let x and y be real numbers belonging to K. Then the points (x, 0), (0, y) and (0, 1) are constructible. The point (x, y − 1) is then constructible, 19

since it is the fourth vertex of a parallelogram which has three vertices at the constructible points (x, 0), (0, y) and (0, 1) (Lemma 3.25). But the line which passes through the two constructible points (0, y) and (x, y − 1) intersects the x-axis at the point (xy, 0). Therefore the point (xy, 0) is constructible, and thus xy ∈ K. Now suppose that x ∈ K, y ∈ K and y 6= 0. The point (x, 1 − y) is constructible, since it is the fourth vertex of a parallelogram with vertices at the constructible points (x, 0), (0, y) and (0, 1). The line segment joining the constructible points (0, 1) and (x, 1 − y) intersects the x-axis at the point (xy −1 , 0). Thus xy −1 ∈ K. The above results show that K is a subfield of the field of real numbers. Moreover if x ∈ K and y ∈ K then the point (x, y) is constructible, since it is the fourth vertex of a rectangle with vertices at the constructible points (0, 0), (x, 0) and (0, y). Conversely, suppose that the point (x, y) is constructible. We claim that the point (x, 0) is constructible and thus x ∈ K. This result is obviously true if y = 0. If y 6= 0 then the circles centred on the points (0, 0) and (1, 0) and passing through (x, y) intersect in the two points (x, y) and (x, −y). The point (x, 0) is thus the point at which the line passing through the constructible points (x, y) and (x, −y) intersects the x-axis, and is thus itself constructible. The point (0, y) is then the fourth vertex of a rectangle with vertices at the constructible points (0, 0), (x, 0) and (x, y), and thus is itself constructible. The circle centred on the origin and passing though (0, y) intersects the x-axis at (y, 0). Thus (y, 0) is constructible, and thus y ∈ K. We have thus shown that a point (x, y) is constructible using straightedge and compasses alone if and only if x ∈ K and y ∈ K. Suppose that x ∈ K and that x > 0. Then 21 (1 − x) ∈ K. Thus if C = (0, 12 (1 − x)) then C is a constructible point. Let (u, 0) be the point at which the circle centred on C and passing through the constructible point (0, 1) intersects the x-axis. (The circle does intersect the x-axis since it passes through (0, 1) and (0, −x), and x > 0.) The radius of this circle is 12 (1 + x)), and therefore 14 (1 − x)2 + u2 = 14 (1 + x)2 (Pythagoras’ Theorem.) But then 2 u √ = x. But (u, 0) is a constructible point. Thus if x ∈ K and x > 0 then x ∈ K, as required. The above theorems can be applied to the problem of determining whether or not it is possible to construct a regular n-sided polygon with a straightedge and compass, given its centre and one of its vertices. The impossibility of trisecting an angle of 60◦ shows that a regular 18-sided polygon is not constructible using straightedge and compass. Now if one can construct a regular n-sided polygon then one can easily construct a regular 2n-sided polygon by bisecting the angles of the n-sided polygon. Thus the problem 20

reduces to that of determining which regular polygons with an odd number of sides are constructible. Moreover it is not difficult to reduce down to the case where n is a power of some odd prime number. Gauss discovered that a regular 17-sided polygon was constructible in 1796, when he was 19 years old. Techniques of Galois Theory show that the regular n-sided polygon is constructible using straightedge and compass if and only if n = 2s p1 p2 · · · pt , where p1 , p2 , . . . , pt are distinct Fermat primes: a Fermat prime is a prime number that is of the form 2k +1 for some integer k. If k = uv, where u and v are positive integers and v is odd, then 2k + 1 = wv + 1 = (w + 1)(wv−1 − wv−2 + · · · − w + 1), where w = 2u , and hence m 2k + 1 is not prime. Thus any Fermat prime is of the form 22 + 1 for some non-negative integer m. Fermat observed in 1640 that Fm is prime when m ≤ 4. These Fermat primes have the values F0 = 3, F1 = 5, F2 = 17, F3 = 257 and F4 = 65537. Fermat conjectured that all the numbers Fm were prime. However it has been shown that Fm is not prime for any integer m between 5 and 16. Moreover F16 = 265536 + 1 ≈ 1020000 . Note that the five Fermat primes 3, 5, 17, 257 and 65537 provide only 32 constructible regular polygons with an odd number of sides. It is not difficult to see that the geometric problem of constructing a regular n-sided polygon using straightedge and compasses is equivalent to the algebraic problem of finding a formula to express the nth roots of unity in the complex plane in terms of integers or rational numbers by means of algebraic formulae which involve finite addition, subtraction, multiplication, division and the successive extraction of square roots. Thus the problem is closely related to that of expressing the roots of a given polynomial in terms of its coefficients by means of algebraic formulae which involve only finite addition, subtraction, multiplication, division and the successive extraction of pth roots for appropriate prime numbers p.

3.11

Splitting Fields

Definition Let L: K be a field extension, and let f ∈ K[x] be a polynomial with coefficients in K. The polynomial f is said to split over L if f is a constant polynomial or if there exist elements α1 , α2 , . . . , αn of L such that f (x) = c(x − α1 )(x − α2 ) · · · (x − αn ), where c ∈ K is the leading coefficient of f . We see therefore that a polynomial f ∈ K[x] splits over an extension field L of K if and only if f factors in L[x] as a product of constant or linear factors. 21

Definition Let L: K be a field extension, and let f ∈ K[x] be a polynomial with coefficients in K. The field L is said to be a splitting field for f over K if the following conditions are satisfied:— • the polynomial f splits over L; • the polynomial f does not split over any proper subfield of L that contains the field K. Lemma 3.27 Let M : K be a field extension, and let f ∈ K[x] be a polynomial with coefficients in K. Suppose that the polynomial f splits over M . Then there exists a unique subfield L of M which is a splitting field for f over K. Proof Let L be the intersection of all subfields M 0 of M containing K with the property that the polynomial f splits over M 0 . One can readily verify that L is the unique splitting field for f over K contained in M . The Fundamental Theorem of Algebra ensures that a polynomial f ∈ Q[x] with rational coefficients always splits over the field C of complex numbers. Thus some unique subfield L of C is a splitting field for f over Q. Note that if the polynomial f ∈ K[x] splits over an extension field M of K, and if α1 , α2 , . . . , αn are the roots of the polynomial f in M , then the unique splitting field of f over K contained in M is the field K(α1 , α2 , . . . , αn ) obtaining on adjoining the roots of f to K. √ Example The field Q( 2) is a splitting field for the polynomial x2 − 2 over Q. We shall prove below that splitting fields always exist and that any two splitting field extensions for a given polynomial over a field K are isomorphic. Given any homomorphism σ: K → M of fields, we define σ∗ (a0 + a1 x + · · · + an xn ) = σ(a0 ) + σ(a1 )x + · · · + σ(an )xn for all polynomials a0 + a1 x + · · · + an xn with coefficients in K. Note that σ∗ (f + g) = σ∗ (f ) + σ∗ (g) and σ∗ (f g) = σ∗ (f )σ∗ (g) for all f, g ∈ K[x]. Theorem 3.28 (Kronecker) Let K be a field, and let f ∈ K[x] be a nonconstant polynomial with coefficients in K. Then there exists an extension field L of K and an element α of L for which f (α) = 0.

22

Proof Let g be an irreducible factor of f , and let L = K[x]/(g), where (g) is the ideal of K[x] generated by g. For each a ∈ K let i(a) = a + (g). Then i: K → L is a monomorphism. We embed K in L on identifying a ∈ K with i(a). Now L is a field, since g is irreducible (Proposition 3.14). Let α = x+(g). Then g(α) is the image of the polynomial g under the quotient homomorphism from K[x] to L, and therefore g(α) = 0. But g is a factor of the polynomial f . Therefore f (α) = 0, as required. Corollary 3.29 Let K be a field and let f ∈ K[x]. Then there exists a splitting field for f over K. Proof We use induction on the degree deg f of f . The result is trivially true when deg f = 1 (since f then splits over K itself). Suppose that the result holds for all fields and for all polynomials of degree less than deg f . Now it follows from Theorem 3.28 that there exists a field extension K1 : K of K and an element α of K1 satisfying f (α) = 0. Moreover f (x) = (x − α)g(x) for some polynomial g with coefficients in K(α). Now deg g < deg f . It follows from the induction hypothesis that there exists a splitting field L for g over K(α). Then f splits over L. Suppose that f splits over some field M , where K ⊂ M ⊂ L. Then α ∈ M and hence K(α) ⊂ M . But M must also contain the roots of g, since these are roots of f . It follows from the definition of splitting fields that M = L. Thus L is the required splitting field for the polynomial f over K. Any two splitting fields for a given polynomial with coefficients in a field K are K-isomorphic. This result is a special case of the following theorem. Theorem 3.30 Let K1 and K2 be fields, and let σ: K1 → K2 be an isomorphism between K1 and K2 . Let f ∈ K1 [x] be a polynomial with coefficients in K1 , and let L1 and L2 be splitting fields for f and σ∗ (f ) over K1 and K2 respectively. Then there exists an isomorphism τ : L1 → L2 which extends σ: K1 → K2 . Proof We prove the result by induction on [L1 : K1 ]. The result is trivially true when [L1 : K1 ] = 1. Suppose that [L1 : K1 ] > 1 and the result holds for splitting field extensions of lower degree. Choose a root α of f in L1 \K1 , and let m be the minimum polynomial of α over K1 . Then m divides f and σ∗ (m) divides σ∗ (f ), and therefore σ∗ (m) splits over L2 . Moreover the polynomial σ∗ (m) is irreducible over K2 , since σ: K1 → K2 induces an isomorphism between the polynomial rings K1 [x] and K2 [x]. Choose a root β of σ∗ (m). 23

Let g and h be polynomials with coefficients in K1 . Now g(α) = h(α) if and only if m divides g − h. Similarly σ∗ (g)(β) = σ∗ (h)(β) if and only if σ∗ (m) divides σ∗ (g) − σ∗ (h). Therefore σ∗ (g)(β) = σ∗ (h)(β) if and only if g(α) = h(α), and thus there is a well-defined isomorphism ϕ: K1 (α) → K2 (β) which sends g(α) to σ∗ (g)(β) for any polynomial g with coefficients in K. Now L1 and L2 are splitting fields for the polynomials f and σ∗ (f ) over the fields K1 (α) and K2 (β) respectively, and [L1 : K1 (α)] < [L1 : K1 ]. The induction hypothesis therefore ensures the existence of an isomorphism τ : L1 → L2 extending ϕ: K1 (α) → K2 (β). Then τ : L1 → L2 is the required extension of σ: K1 → K2 . Corollary 3.31 Let L: K be a splitting field extension, and let α and β be elements of L. Then there exists a K-automorphism of L sending α to β if and only if α and β have the same minimum polynomial over K. Proof Suppose that there exists a K-automorphism σ of L which sends α to β. Then h(β) = σ(h(α)) for all polynomials h ∈ K[x] with coefficients in K. Therefore h(α) = 0 if and only if h(β) = 0. It follows that α and β must have the same minimum polynomial over K. Conversely suppose that α and β are elements of L that have the same minimum polynomial m over K. Let h1 and h2 be polynomials with coefficients in K. Now h1 (α) = h2 (α) if and only if h1 − h2 is divisible by the minimum polynomial m. It follows that h1 (α) = h2 (α) if and only if h1 (β) = h2 (β). Therefore there is a well-defined K-isomorphism ϕ: K(α) → K(β) that sends h(α) to h(β) for all polynomials h with coefficients in K. Then ϕ(α) = β. Now L is the splitting field over K for some polynomial f with coefficients in K. The field L is then a splitting field for f over both K(α) and K(β). It follows from Theorem 3.30 that the K-isomorphism ϕ: K(α) → K(β) extends to a K-automorphism τ of L that sends α to β, as required.

3.12

Normal Extensions

Definition A field extension L: K is said to be normal if every irreducible polynomial in K[x] with at least one root in L splits over L. Note that a field extension L: K is normal if and only if, given any element α of L, the minimum polynomial of α over K splits over L. Theorem 3.32 Let K be a field, and let L be an extension field of K. Then L is a splitting field over K for some polynomial with coefficients in K if and only if the field extension L: K is both finite and normal. 24

Proof Suppose that L: K is both finite and normal. Then there exist algebraic elements α1 , α2 , . . . , αn of L such that L = K(α1 , α2 , . . . , αn ) (Corollary 3.22). Let f (x) = m1 (x)m2 (x) · · · mn (x), where mj ∈ K[x] is the minimum polynomial of αj over K for j = 1, 2, . . . , n. Then mj splits over L since mj is irreducible and L: K is normal. Thus f splits over L. It follows that L is a splitting field for f over K, since L is obtained from K by adjoining roots of f . Conversely suppose that L is a splitting field over K for some polynomial f ∈ K[x]. Then L is obtained from K by adjoining the roots of f , and therefore the extension L: K is finite. (Corollary 3.22). Let g ∈ K[x] be irreducible, and let M be a splitting field for the polynomial f g over L. Then L ⊂ M and the polynomials f and g both split over M . Let β and γ be roots of g in M . Now the polynomial f splits over the fields L(β) and L(γ). Moreover if f splits over any subfield of M containing K(β) then that subfield must contain L (since L is a splitting field for f over K) and thus must contain L(β). We deduce that L(β) is a splitting field for f over K(β). Similarly L(γ) is a splitting field for f over K(γ). Now there is a well-defined K-isomorphism σ: K(β) → K(γ) which sends h(β) to h(γ) for all polynomials h with coefficients in K, since two such polynomials h1 and h2 take the same value at a root of the irreducible polynomial g if and only if their difference h1 −h2 is divisible by g. This isomorphism σ: K(β) → K(γ) extends to an K-isomorphism τ : L(β) → L(γ) between L(β) and L(γ), since L(β) and L(β) are splitting fields for f over the field K(β) and K(γ) respectively (Theorem 3.30). Thus the extensions L(β): K and L(γ): K are isomorphic, and [L(β): K] = [L(γ): K]. But [L(β): K] = [L(β): L][L: K] and [L(γ): K] = [L(γ): L][L: K] by the Tower Law (Theorem 3.18). It follows that [L(β): L] = [L(γ): L]. In particular β ∈ L if and only if γ ∈ L. This shows that that any irreducible polynomial with a root in L must split over L, and thus L: K is normal, as required.

3.13

Separability

Let K be a field. We recall that nk is defined inductively for all integers n and for all elements k of K so that 0k = 0 and (n + 1)k = nk + k for all n ∈ Z and k ∈ K. Thus 1k = k, 2k = k + k, 3k = k + k + k etc., and (−n)k = −(nk) for all n ∈ Z. Definition Let K be a field, and let f ∈ K[x] be a polynomial with coeffin P cients c0 , c1 , . . . , cn in K, where f (x) = cj xj . The formal derivative Df j=0

25

of f is defined by the formula (Df )(x) =

n P

jcj xj−1 .

j=1

(The definition of formal derivative given above is a purely algebraic definition, applying to polynomials with coefficients in any field whatsoever, which corresponds to the formula for the derivative of a polynomial with real coefficients obtained by elementary calculus.) Let K be a field. One can readily verify by straightforward calculation that D(f + g) = Df + Dg and D(f g) = (Df )g + f (Dg) for all f ∈ K[x]. If f is a constant polynomial then Df = 0. Let K be a field, and let f ∈ K[x]. An element α of an extension field L of K is said to be a repeated zero if (x − α)2 divides f (x). Proposition 3.33 Let K be a field, and let f ∈ K[x]. The polynomial f has a repeated zero in a splitting field for f over K if and only if there exists a non-constant polynomial with coefficients in K that divides both f and its formal derivative Df in K[x]. Proof Suppose that f ∈ K[x] has a repeated root α in a splitting field L. Then f (x) = (x − α)2 h(x) for some polynomial h ∈ L[x]. But then (Df )(x) = 2(x − α)h(x) + (x − α)2 (Dh)(x) and hence (Df )(α) = 0. It follows that the minimum polynomial of α over K is a non-constant polynomial with coefficients in K which divides both f and Df . Conversely let f ∈ K[x] be a polynomial with the property that f and Df are both divisible by some non-constant polynomial g ∈ K[x]. Let L be a splitting field for f over K. Then g splits over L (since g is a factor of f ). Let α ∈ L be a root of g. Then f (α) = 0, and hence f (x) = (x − α)e(x) for some polynomial e ∈ L[x]. On differentiating, we find that (Df )(x) = e(x) + (x − α)De(x). But (Df )(α) = 0, since g(α) = 0 and g divides Df in K[x]. It follows that e(α) = (Df )(α) = 0, and thus e(x) = (x − α)h(x) for some polynomial h ∈ L[x]. But then f (x) = (x − α)2 h(x), and thus the polynomial f has a repeated root in the splitting field L, as required. Definition Let K be a field. An irreducible polynomial in K[x] is said to be separable over K if it does not have repeated roots in a splitting field. A polynomial in K[x] is said to separable over K if all its irreducible factors are separable over K. A polynomial is said to be inseparable if it is not separable.

26

Corollary 3.34 Let K be a field. An irreducible polynomial f is inseparable if and only if Df = 0. Proof Let f ∈ K[x] be an irreducible polynomial. Suppose that f is inseparable. Then f has a repeated root in a splitting field, and it follows from Proposition 3.33 that there exists a non-constant polynomial g in K[x] dividing both f and its formal derivative Df . But then g = cf for some non-zero element c of K, since f is irreducible, and thus f divides Df . But if Df were non-zero then deg Df < deg f , and thus f would not divide Df . Thus Df = 0. Conversely if Df = 0 then f divides both f and Df . It follows from Proposition 3.33 that f has a repeated root in a splitting field, and is thus inseparable. Definition A field extension L: K is said to be separable over K if the minimum polynomial of each element of L is separable over K. Suppose that K is a field of characteristic zero. Then n.k 6= 0 for all n ∈ Z and k ∈ K satisfying n 6= 0 and k 6= 0. It follows from the definition of the formal derivative that Df = 0 if and only if f ∈ K[x] is a constant polynomial. The following result therefore follows immediately from Corollary 3.34. Corollary 3.35 Suppose that K is a field of characteristic zero. Then every polynomial with coefficients in K is separable over K, and thus every field extension L: K of K is separable.

3.14

Finite Fields

Lemma 3.36 Let K be a field of characteristic p, where p > 0. Then (x + y)p = xp + y p and (xy)p = xp y p for all x, y ∈ K. Thus the function x 7→ xp is a monomorphism mapping the field K into itself. p

Proof The Binomial Theorem tells us that (x + y) =

p   X p

j

xj y p−j , where

j=0     p p p(p − 1) · · · (p − j + 1) for j = 1, 2, . . . , p. The de= 1 and = j! 0 j nominator of each binomial coefficient must divide the numerator, since this coefficient is an integer. Now the characteristic p of K is a prime number. Moreover if 0 < j < p then p is a factor of the numerator but is not a factor of the denominator. It follows from the Fundamental Theorem of Arithmetic

27

  p that p divides for all j satisfying 0 < j < p. But px = 0 for all x ∈ K, j since charK = p. Therefore (x + y)p = xp + y p for all x, y ∈ K. The identity (xy)p = xp y p is immediate from the commutativity of K. Let K be a field of characteristic p, where p > 0. The monomorphism x 7→ xp is referred to as the Frobenius monomorphism of K. If K is finite then this monomorphism is an automorphism of K, since any injection mapping a finite set into itself must be a bijection. Theorem 3.37 A field K has pn elements if and only if it is a splitting field n for the polynomial xp − x over its prime subfield Fp , where Fp ∼ = Z/pZ. Proof Suppose that K has q elements, where q = pn . If α ∈ K \ {0} then αq−1 = 1, since the set of non-zero elements of K is a group of order q − 1 with respect to multiplication. It follows that αq = α for all α ∈ K. Thus all elements of K are roots of the polynomial xq − x. This polynomial must therefore split over K, since its degree is q and K has q elements. Moreover the polynomial cannot split over any proper subfield of K. Thus K is a splitting field for this polynomial. Conversely suppose that K is a splitting field for the polynomial f over Fp , where f (x) = xq − x and q = pn . Let σ(α) = αq for all α ∈ K. Then σ: K → K is a monomorphism, being the composition of n successive applications of the Frobenius monomorphism of K. Moreover an element α of K is a root of f if and only if σ(α) = α. It follows from this that the roots of f constitute a subfield of K. This subfield is the whole of K, since K is a splitting field. Thus K consists of the roots of f . Now Df (x) = qxq−1 − 1 = −1, since q is divisible by the characteristic p of Fp . It follows from Proposition 3.33 that the roots of f are distinct. Therefore f has q roots, and thus K has q elements, as required. Let K be a finite field of characteristic p. Then K has pn elements, where n = [K: Fp ], since any vector space of dimension n over a field of order p must have exactly pn elements. The following result is now a consequence of the existence of splitting fields (Corollary 3.29) and the uniqueness of splitting fields up to isomorphism (Theorem 3.30) Corollary 3.38 There exists a finite field GF(pn ) of order pn for each prime number p and positive integer n. Two finite fields are isomorphic if and only if they have the same number of elements.

28

The field GF(pn ) is referred to as the Galois field of order pn . The non-zero elements of a field constitute a group under multiplication. We shall prove that all finite subgroups of the group of non-zero elements of a field are cyclic. It follows immediately from this that the group of non-zero elements of a finite field is cyclic. For each positive integer n, we denote by ϕ(n) the number of integers x X satisfying 0 ≤ x < n that are coprime to n. We show that the sum ϕ(d) d|n

of ϕ(d) taken over all divisors of a positive integer n is equal to n. Lemma 3.39 Let n be a positive integer. Then

X

ϕ(d) = n.

d|n

Proof If x is an integer satisfying X0 ≤ x < n then (x, n) = n/d for some divisor d of n. It follows that n = nd , where nd is the number of integers x d|n

satisfying 0 ≤ x < n for which (x, n) = n/d. Thus it suffices to show that nd = ϕ(d) for each divisor d of n. Let d be a divisor of n, and let a = n/d. Given any integer x satisfying 0 ≤ x < n that is divisible by a, there exists an integer y satisfying 0 ≤ y < d such that x = ay. Then (x, n) = (ay, ad) = a(y, d). It follows that the integers x satisfying 0 ≤ x < n for which (x, n) = a are those of the form ay, where y is an integer, 0 ≤ y < d and (y, d) = 1. It follows that there are exactly ϕ(d) integersX x satisfying 0 ≤ x < n for which (x, n) = n/d, and thus nd = ϕ(d) and n = ϕ(d), as required. d|n

The set of all non-zero elements of a field is a group with respect to the operation of multiplication. Theorem 3.40 Let G be a finite subgroup of the group of non-zero elements of a field. Then the group G is cyclic. Proof Let n be the order of the group G. It follows from Lagrange’s Theorem that the order of every element of G divides n. For each divisor dX of n, let ψ(d) denote the number of elements of G that are of order d. Clearly ψ(d) = n. d|n

Let g be an element of G of order d, where d is a divisor of n. The elements 1, g, g 2 , . . . , g d−1 are distinct elements of G and are roots of the polynomial xd − 1. But a polynomial of degree d with coefficients in a field has at most d roots in that field. Therefore every element x of G satisfying xd = 1 is g k 29

for some uniquely determined integer k satisfying 0 ≤ k < d. If k is coprime to d then g k has order d, for if (g k )n = 1 then d divides kn and hence d divides n. Conversely if g k has order d then d and k are coprime, for if e is a common divisor of k and d then (g k )d/e = g d(k/e) = 1, and hence e = 1. Thus if there exists at least one element g of G that is of order d then the elements of G that are of order d are the elements g k for those integers k satisfying 0 ≤ k < d that are coprime to d. It follows that if ψ(d) > 0 then ψ(d) = ϕ(d), where ϕ(d) is the number of integers k satisfying 0 ≤ k < d that are coprime to d. X Now 0 ≤ ψ(d) ≤ ϕ(d) for each divisor d of n. But ψ(d) = n and d|n

X

ϕ(d) = n. It follows that ψ(d) = φ(d) for each divisor d of n. In

d|n

particular ψ(n) = ϕ(n) ≥ 1. Thus there exists an element of G whose order is the order n of G. This element generates G, and thus G is cyclic, as required. Corollary 3.41 The group of non-zero elements of a finite field is cyclic.

3.15

The Primitive Element Theorem

Theorem 3.42 (Primitive Element Theorem) Every finite separable field extension is simple. Proof Let L: K be a finite separable field extension. Suppose that K is a finite field. Then L is also a finite field, since it is a finite-dimensional vector space over K. The group of non-zero elements of L is therefore generated by a single non-zero element θ of L (Corollary 3.41). But then L = K(θ) and thus L: K is simple. This proves the Primitive Element Theorem in the case where the field K is finite. Next suppose that L = K(β, γ), where K is infinite, β and γ are algebraic over K and L: K is separable. Let N be a splitting field for the polynomial f g, where f and g are the minimum polynomials of β and γ respectively over K. Then f and g both split over N . Let β1 , β2 , . . . , βq be the roots of f in N , and let γ1 , γ2 , . . . , γr be the roots of g in N , where β1 = β and γ1 = γ. The separability of L: K ensures that γk 6= γj when k 6= j. Now K is infinite. We can therefore choose c ∈ K so that c 6= (βi − β)/(γ − γj ) for any i and j with j 6= 1. Let h(x) = f (θ − cx), where θ = β + cγ. Then h is a polynomial in the indeterminate x with coefficients in K(θ) which satisfies h(γ) = f (β) = 0. Moreover h(γj ) 6= 0 whenever j 6= 1, since θ − cγj 6= βi for all i and j with j 6= 1. Thus γ is the only 30

common root of g and h. It follows that x − γ is a highest common factor of g and h in the polynomial ring K(θ)[x], and therefore γ ∈ K(θ). But then β ∈ K(θ), since β = θ − cγ and c ∈ K. It follows that L = K(θ). It now follows by induction on m that if L = K(α1 , α2 , . . . , αm ), where K is infinite, α1 , α2 , . . . , αm are algebraic over K, and L: K is separable, then the extension L: K is simple. Thus all finite separable field extensions are simple, as required.

3.16

The Galois Group of a Field Extension

Definition The Galois group Γ(L: K) of a field extension L: K is the group of all automorphisms of the field L that fix all elements of the subfield K. Lemma 3.43 If L: K is a finite separable field extension then |Γ(L: K)| ≤ [L: K]. Proof It follows from the Primitive Element Theorem (Theorem 3.42) that there exists some element α of L such that L = K(α). Let λ be an element of L. Then λ = g(α) for some polynomial g with coefficients in K. But then σ(λ) = g(σ(α)) for all σ ∈ Γ(L: K), since the coefficients of G are fixed by σ. It follows that each automorphism σ in Γ(L: K) is uniquely determined once σ(α) is known If f be the minimum polynomial of α over K then f (σ(α)) = σ(f (α)) = 0 for all σ ∈ Γ(L: K) since the coefficients of f are in K and are therefore fixed by σ. Thus σ(α) is a root of f . It follows that the order |Γ(L: K)| of the Galois group is bounded above by the number of roots of f that belong to L, and is thus bounded above by the degree deg f of f . But deg f = [L: K] (Theorem 3.21). Thus |Γ(L: K)| ≤ [L: K], as required. Definition Let L be a field, and let G be a group of automorphisms of L. The fixed field of G is the subfield K of L defined by K = {a ∈ L : σ(a) = a for all σ ∈ G}. Proposition 3.44 Let L be a field, let G be a finite group of automorphisms of L, and let K be the fixed field of G. Then each element α of L is algebraic over K, and the minimum polynomial of α over K is the polynomial (x − α1 )(x − α2 ) · · · (x − αk ), where α1 , α2 , . . . , αk are distinct and are the elements of the orbit of α under the action of G on L. 31

Proof Let f (x) = (x − α1 )(x − α2 ) · · · (x − αm ). Then the polynomial f is invariant under the action of G, since each automorphism in the group G permutes the elements α1 , α2 , . . . , αk and therefore permutes the factors of f amongst themselves. It follows that the coefficients of the polynomial f belong to the fixed field K of G. Thus α is algebraic over K, as it is a root of the polynomial f . Now, given any root αi of f , there exists some σ ∈ G such that αi = σ(α). Thus if g ∈ K[x] is a polynomial with coefficients in K which satisfies g(α) = 0 then g(αi ) = σ(g(α)) = 0, since the coefficients of g are fixed by σ. But then f divides g. Thus f is the minimum polynomial of α over K, as required. Definition A field extension is said to be a Galois extension if it is finite, normal and separable. Theorem 3.45 Let L be a field, let G be a finite subgroup of the group of automorphisms of L, and let K be the fixed field of G. Then the field extension L: K is a Galois extension. Moreover G is the Galois group Γ(L: K) of L: K and |G| = [L: K]. Proof It follows from Proposition 3.44 that, for each α ∈ L, the minimum polynomial of α over K splits over L and has no multiple roots. Thus the extension L: K is both normal and separable. Let M be any field satisfying K ⊂ M ⊂ L for which the extension M : K is finite. The extension M : K is separable, since L: K is separable. It follows from the Primitive Element Theorem (Theorem 3.42) that the extension M : K is simple. Thus M = K(α) for some α ∈ L. But then [M : K] is equal to the degree of the minimum polynomial of α over K (Theorem 3.21). It follows from Proposition 3.44 that [M : K] is equal to the number of elements in the orbit of α under the action of G on L. Therefore [M : K] divides |G| for any intermediate field M for which the extension M : K is finite. Now let the intermediate field M be chosen so as to maximize [M : K]. If λ ∈ L then λ is algebraic over K, and therefore [M (λ): M ] is finite. It follows from the Tower Law (Theorem 3.18) that [M (λ): K] is finite, and [M (λ): K] = [M (λ): M ][M : K]. But M has been chosen so as to maximize [M : K]. Therefore [M (λ): K] = [M : K], and [M (λ): M ] = 1. Thus λ ∈ M . We conclude that M = L. Thus L: K is finite and [L: K] divides |G|. The field extension L: K is a Galois extension, since it has been shown to be finite, normal and separable. Now G ⊂ Γ(L: K) and |Γ(L: K)| ≤ [L: K] (Lemma 3.43). Therefore |Γ(L: K)| ≤ [L: K] ≤ |G| ≤ |Γ(L: K)|, and thus G = Γ(L: K) and |G| = [L: K], as required. 32

Theorem 3.46 Let Γ(L: K) be the Galois group of a finite field extension L: K. Then |Γ(L: K)| divides [L: K]. Moreover |Γ(L: K)| = [L: K] if and only if L: K is a Galois extension, in which case K is the fixed field of Γ(L: K). Proof Let M be the fixed field of Γ(L: K). It follows from Theorem 3.45 that L: M is a Galois extension and |Γ(L: K)| = [L: M ]. Now [L: K] = [L: M ][M : K] by the Tower Law (Theorem 3.18). Thus |Γ(L: K)| divides [L: K]. If |Γ(L: K)| = [L: K] then M = K. But then L: K is a Galois extension and K is the fixed field of Γ(L: K). Conversely suppose that L: K is a Galois extension. We must show that |Γ(L: K)| = [L: K]. Now the extension L: K is both finite and separable. It follows from the Primitive Element Theorem (Theorem 3.42) that there exists some element θ of L such that L = K(θ). Let f be the minimum polynomial of θ over K. Then f splits over L, since f is irreducible and the extension L: K is normal. Let θ1 , θ2 , . . . , θn be the roots of f in L, where θ1 = θ and n = deg f . If σ is a K-automorphism of L then f (σ(θ)) = σ(f (θ)) = 0, since the coefficients of the polynomial f belong to K and are therefore fixed by σ. Thus σ(θ) = θj for some j. We claim that, for each root θj of f , there is exactly one K-automorphism σj of L satisfying σj (θ) = θj . Let g(x) and h(x) be polynomials with coefficients in K. Suppose that g(θ) = h(θ). Then g − h is divisible by the minimum polynomial f of θ. It follows that g(θj ) = h(θj ) for any root θj of f . Now every element of L is of the form g(θ) for some g ∈ K[x], since L = K(θ). We deduce therefore that there is a well-defined function σj : L → L with the property that σj (g(θ)) = g(θj ) for all g ∈ K[x]. The definition of this function ensures that it is the unique automorphism of the field L that fixes each element of K and sends θ to θj . Now the roots of the polynomial f in L are distinct, since f is irreducible and L: K is separable. Moreover the order of the Galois group Γ(L: K) is equal to the number of roots of f , since each root determines a unique element of the Galois group. Therefore |Γ(L: K)| = deg f . But deg f = [L: K] since L = K(θ) and f is the minimum polynomial of θ over K (Theorem 3.21). Thus |Γ(L: K)| = [L: K], as required.

3.17

The Galois correspondence

Proposition 3.47 Let K, L and M be fields satisfying K ⊂ M ⊂ L. Suppose that L: K is a Galois extension. Then so is L: M . If in addition M : K is normal, then M : K is a Galois extension. Proof Let α ∈ L and let fK ∈ K[x] and fM ∈ M [x] be the minimum polyomials of α over K and M respectively. Then fK splits over L, since fK 33

is irreducible over K and L: K is a normal extension. Also the roots of fK in L are distinct, since L: K is a separable extension. But fM divides fK , since fK (α) = 0 and the coefficients of fK belong to M . It follows that fM also splits over L, and its roots are distinct. We deduce that the finite extension L: M is both normal and separable, and is therefore a Galois extension. The finite extension M : K is clearly separable, since L: K is separable. Thus if M : K is a normal extension then it is a Galois extension. Theorem 3.48 (The Galois Correspondence) Let L: K be a Galois extension of a field K. Then there is a natural bijective correspondence between fields M satisfying K ⊂ M ⊂ L and subgroups of the Galois group Γ(L: K) of the extension L: K. If M is a field satisfying K ⊂ M ⊂ L then the subgroup of Γ(L: K) corresponding to M is the Galois group Γ(L: M ) of the extension L: M . If G is a subgroup of Γ(L: K) then the subfield of L corresponding to G is the fixed field of G. Moreover the extension M : K is normal if and only if Γ(L: M ) is a normal subgroup of the Galois group Γ(L: K), in which case Γ(M : K) ∼ = Γ(L: K)/Γ(L: M ). Proof Let M be a subfield of L containing K. Then L: M is a Galois extension (Proposition 3.47). The existence of the required bijective correspondence between fields M satisfying K ⊂ M ⊂ L and subgroups of the Galois group Γ(L: K) follows immediately from Theorem 3.45 and Theorem 3.46. Let M be a field satisfying K ⊂ M ⊂ L. Now the extension M : K is normal if and only if, for each α ∈ M , the minimum polynomial of α over K splits over M . But K is the fixed field of the Galois group Γ(L: K), and therefore the roots of the minimum polynomial of α over K are the elements of the orbit of α under the action of Γ(L: K) on L (Proposition 3.44). Thus M : K is normal if and only if σ(M ) = M for all σ ∈ Γ(L: K). Let H = Γ(L: M ). Then M = σ(M ) if and only if H = σHσ −1 , since M and σ(M ) are the fixed fields of H and σHσ −1 respectively. Thus the extension M : K is normal if and only if Γ(L: M ) is a normal subgroup of Γ(L: K). Finally suppose that M : K is a normal extension. For each σ ∈ Γ(L: K), let ρ(σ) be the restriction σ|M of σ to M . Then ρ: Γ(L: K) → Γ(M : K) is a group homomorphism whose kernel is Γ(L: M ). We can apply Theorem 3.45 to the extension M : K to deduce that ρ(Γ(L: K)) = Γ(M : K), since the fixed field of ρ(Γ(L: K)) is K. Therefore the homomorphism ρ: Γ(L: K) → Γ(M : K) induces the required isomorphism between Γ(L: K)/Γ(L: M ) and Γ(M : K).

34

3.18

Quadratic Polynomials

We consider the problem of expressing the roots of a polynomial of low degree in terms of its coefficients. Then the well-known procedure for locating the roots of a quadratic polynomial with real or complex coefficients generalizes to quadratic polynomials with coefficients in a field K whose characteristic does not equal 2. Given a quadratic polynomial ax2 + bx + c with coefficients a and b belonging to some such field K, let us adjoin to K an element δ satisfying δ 2 = b2 − 4ac. Then the polynomial splits over K(δ), and its roots are (−b ± δ)/(2a). We shall describe below analogous procedures for expressing the roots of cubic and quartic polynomials in terms of their coefficients.

3.19

Cubic Polynomials

Consider a cubic polynomial x3 + ax2 + bx + c, where the coefficients a, b and c belong to some field K of characteristic zero. If f (x) = x3 + ax2 + bx + c 2 3 then f (x − 31 a) = x3 − px − q, where p = 13 a2 − b and q = 13 ba − 27 a − c. It therefore suffices to restrict our attention to cubic polynomials of the form x3 − px − q, where p and q belong to K. Let f (x) = x3 − px − q, and let u and v be elements of some splitting field for f over Q. Then f (u + v) = u3 + v 3 + (3uv − p)(u + v) − q. Suppose that 3uv = p. Then f (u + v) = u3 + p3 /(27u3 ) − q. Thus f (u + p/(3u)) = 0 if and only if u3 is a root of the quadratic polynomial x2 − xu + p3 /27. Now the roots of this quadratic polynomial are r q q2 p3 ± − , 2 4 27 and the product of these roots is p3 /27. Thus if one of these roots is equal to u3 then the other is equal to v 3 , where v = p/(3u). It follows that the roots of the cubic polynomial f are s s r r 2 3 3 q 3 q q p q2 p3 + − + − − 2 4 27 2 4 27 where the two cube roots must be chosen so as to ensure that their product is equal to 13 p. It follows that the cubic polynomial x3 − px − q splits over the 1 3 field K(, ξ, ω), where 2 = 14 q 2 − 27 p and ξ 3 = 12 q +  and where ω satisfies

35

ω 3 = 1 and ω 6= 1. The roots of the polynomial in this extension field are α, β and γ, where p p p α=ξ+ , β = ωξ + ω 2 , γ = ω2ξ + ω3 . 3ξ 3ξ 3ξ Now let us consider the possibilities for the Galois group Γ(L: K), where L is a splitting field for f over K. Now L = K(α, β, γ), where α, β and γ are the roots of f . Also a K-automorphism of L must permute the roots of f amongst themselves, and it is determined by its action on these roots. Therefore Γ(L: K) is isomorphic to a subgroup of the symmetric group Σ3 (i.e., the group of permutations of a set of 3 objects), and thus the possibilities for the order of Γ(L: K) are 1, 2, 3 and 6. It follows from Corollary 3.31 that f is irreducible over K if and only if the roots of K are distinct and the Galois group acts transitively on the roots of K. By considering all possible subgroups of Σ3 it is not difficult to see that f is irreducible over K if and only if |Γ(L: K)| = 3 or 6. If f splits over K then |Γ(L: K)| = 1. If f factors in K[x] as the product of a linear factor and an irreducible quadratic factor then |Γ(L: K)| = 2. Let δ = (α−β)(α−γ)(β −γ). Then δ 2 is invariant under any permutation of α β and γ, and therefore δ 2 is fixed by all automorphisms in the Galois group Γ(L: K). Therefore δ 2 ∈ K. The element δ 2 of K is referred to as the discriminant of the polynomial f . A straightforward calculation shows that if f (x) = x3 − px − q then δ 2 = 4p3 − 27q 2 . Now δ changes sign under any permutation of the roots α, β and γ that transposes two of the roots whilst leaving the third root fixed. But δ ∈ K if and only if δ is fixed by all elements of the Galois group Γ(L: K), in which case the Galois group must induce only cyclic permutations of the roots α, β and γ. Therefore Γ(L: K) is isomorphic to the cyclic group of order 3 if and only if f is irreducible and the discriminant 4p3 − 27q 2 of f has a square root in the field K. If f is irreducible but the discriminant does not have a square root in K then Γ(L: K) is isomorphic to the symmetric group Σ3 , and |Γ(L: K)| = 6.

3.20

Quartic Polynomials

We now consider how to locate the roots of a quartic polynomial with coefficients in a field K of characteristic zero. A substitution of the form x 7→ x−c, where c ∈ K, will reduce the problem to that of locating the roots α, β, γ and δ of a quartic polynomial f of the form f (x) = x4 − px2 − qx − r in some splitting field L. These roots satisfy α + β + γ + δ = 0, since the coefficient of x3 in f (x) equals zero. Define λ = (α + β)(γ + δ) = −(α + β)2 , 36

µ = (α + γ)(β + δ) = −(α + γ)2 , ν = (α + δ)(β + γ) = −(α + δ)2 .

A straightforward, if tedious, calculation shows that (α+β)(α+γ)(α+δ) √ √ = q. √ 1 One can then verify that the roots of f take the form 2 ( −λ+ −µ+ −ν), √ √ √ where these square roots are chosen to ensure that −λ −µ −ν = q. (It should be noted that there are four possible ways in which the square roots can be chosen to satisfy this condition; these yield all four roots of the polynomial f .) We can therefore determine the roots of f in an appropriate splitting field once we have expressed the quantities λ, µ and ν in terms of the coefficients of the polynomial. Let the cubic polynomial g be given by g(x) = (x − λ)(x − µ)(x − ν). (This polynomial g is referred to as the resolvent cubic of the given quartic polynomial.) Now any permutation of the roots of the given quartic will permute the quantities λ, µ and ν amonst themselves and will therefore permute the factors of g. Therefore the coefficients of g are fixed by all elements of the Galois group Γ(L: K) and therefore belong to the ground field K. Straightforward calculations show that λ + µ + ν = −2p,

λµ + λν + µν = p2 + 4r,

λµν = −q 2 .

It follows that g(x) = x3 + 2px2 + (p2 + 4r)x + q 2 . We can use the formulae for the roots of a cubic polynomial to express the roots λ, µ and ν of g in terms of the coefficients of f , and thus determine the roots α, β, γ and δ of f in terms of the coefficients of f .

3.21

The Galois group of the polynomial x4 − 2

We shall apply the Galois correspondence to investigate the structure of the splitting field for the polynomial x4 − 2 over the field Q of rational numbers. A straightforward application of Eisenstein’s Irreducibility Criterion (Proposition 3.17) shows that the polynomial x4 − 2 is irreducible over Q. Let ξ be 4 the unique positive real number satisfying ξ 4 = 2. Then the roots of x√ −2 in the field C of complex numbers are ξ, iξ, −ξ and −iξ, where i = −1. Thus if L = Q(ξ, i) then L is a splitting field for the polynomial x4 − 2 over Q. Now the polynomial x4 − 2 is the minimum polynomial of ξ over Q, since this polynomial is irreducible. We can therefore apply Theorem 3.21 to deduce that [Q(ξ): Q] = 4. Now i does not belong to Q(ξ), since Q(ξ) ⊂ R. Therefore the polynomial x2 + 1 is the minimum polynomial of i over 37

Q(ξ). Another application of Theorem 3.21 now shows that [L: Q(ξ)] = [Q(ξ, i): Q(ξ)] = 2. It follows from the Tower Law (Theorem 3.18) that [L: Q] = [L: Q(ξ)][Q(ξ): Q] = 8. Moreover the extension L: Q is a Galois extension, and therefore its Galois group Γ(L: Q) is a group of order 8 (Theorem 3.46). Another application of the Tower Law now shows that [L: Q(i)] = 4, since [L: Q] = [L: Q(i)][Q(i): Q] and [Q(i): Q] = 2. Therefore the minimum polynomial of ξ over Q(i) is a polynomial of degree 4 (Theorem 3.21). But ξ is a root of x4 −2. Therefore x4 −2 is irreducible over Q(i), and is the minimum polynomial of ξ over Q(i). Corollary 3.31 then ensures the existence of an automorphism σ of L that sends ξ ∈ L to iξ and fixes each element of Q(i). Similarly there exists an automorphism τ of L that sends i to −i and fixes each element of Q(ξ). (The automorphism τ is in fact the restriction to L of the automorphism of C that sends each complex number to its complex conjugate.) Now the automorphisms σ, σ 2 , σ 3 and σ 4 fix i and therefore send ξ to iξ, −ξ, −iξ and ξ respectively. Therefore σ 4 = ι, where ι is the identity automorphism of L. Similarly τ 2 = ι. Straightforward calculations show that τ σ = σ 3 τ , and (στ )2 = (σ 2 τ )2 = (σ 3 τ )2 = ι. It follows easily from this that Γ(L: Q) = {ι, σ, σ 2 , σ 3 , τ, στ, σ 2 τ, σ 3 τ }, and Γ(L: Q) is isomorphic to the dihedral group of order 8 (i.e., the group of symmetries of a square in the plane). The Galois correspondence is a bijective correspondence between the subgroups of Γ(L: Q) and subfields of L that contain Q. The subfield of L corresponding to a given subgroup of Γ(L: Q) is set of all elements of L that are fixed by all the automorphisms in the subgroup. One can verify that the correspondence between subgroups of Γ(L: Q) and their fixed fields is as follows:— Subgroup of Γ(L: Q) Fixed field Γ(L: K) {ι, σ, σ 2 , σ 3 } {ι, σ 2 , τ, σ 2 τ } {ι, σ 2 , στ, σ 3 τ } {ι, σ 2 } {ι, τ } {ι, σ 2 τ } {ι, στ } {ι, σ 3 τ } {ι}

38

Q Q(i) √ Q( √2) Q(i √ 2) Q( 2, i) Q(ξ) Q(iξ) Q((1 − i)/ξ) Q((1 + i)/ξ) Q(ξ, i)

3.22

The Galois group of a polynomial

Definition Let f be a polynomial with coefficients in some field K. The Galois group ΓK (f ) of f over K is defined to be the Galois group Γ(L: K) of the extension L: K, where L is some splitting field for the polynomial f over K. We recall that all splitting fields for a given polynomial over a field K are K-isomorphic (see Theorem 3.30), and thus the Galois groups of these splitting field extensions are isomorphic. The Galois group of the given polynomial over K is therefore well-defined (up to isomorphism of groups) and does not depend on the choice of splitting field. Lemma 3.49 Let f be a polynomial with coefficients in some field K and let M be an extension field of K. Then ΓM (f ) is isomorphic to a subgroup of ΓK (f ). Proof Let N be a splitting field for f over M . Then N contains a splitting field L for f over K. Each K-automorphism of N must map the field L into itself. Therefore there is an injective homomorphism from Γ(N : M ) to Γ(L: K) which sends an automorphism σ ∈ Γ(N : M ) to its restriction σ|L to L. The result then follows from the definition of the Galois group of a polynomial. Let f be a polynomial with coefficients in some field K and let the roots of f is some splitting field L be α1 , α2 , . . . , αn . An element σ of Γ(L: K) is a K-automorphism of L, and therefore σ permutes the roots of f . Moreover two automorphism σ and τ in the Galois group Γ(L: K) are equal if and only if σ(αj ) = τ (αj ) for j = 1, 2, . . . , n, since L = K(α1 , α2 , . . . , αn ). Thus the Galois group of a polynomial can be represented as a subgroup of the group of permutations of its roots. We deduce immediately the following result. Lemma 3.50 Let f be a polynomial with coefficients in some field K. Then the Galois group of f over K is isomorphic to a subgroup of the symmetric group Σn , where n is the degree of f .

3.23

Solvable polynomials and their Galois groups

Definition We say that a polynomial with coefficients in a given field is solvable by radicals if the roots of the polynomial in a splitting field can be constructed from its coefficients in a finite number of steps involving only the operations of addition, subtraction, multiplication, division and extraction of nth roots for appropriate natural numbers n. 39

It follows from the definition above that a polynomial with coefficients in a field K is solvable by radicals if and only if there exist fields K0 , K1 , . . . , Km such that K0 = K, the polynomial f splits over Km , and, for each integer i between 1 and m, the field Ki is obtained on adjoining to Ki−1 an element αi with the property that αipi ∈ Ki−1 for some positive integer pi . Moreover we can assume, without loss of generality that p1 , p2 , . . . , pm are prime numbers, since an nth root α of an element of a given field can be adjoined that field by successively adjoining powers αn1 , αn2 , . . . , αnk of α chosen such that n/n1 is prime, ni /ni−1 is prime for i = 2, 3, . . . , k, and nk = 1. We shall prove that a polynomial with coefficients in a field K of characteristic zero is solvable by radicals if and only if its Galois group ΓK (f ) over K is a solvable group. Let L be a field, and let p be a prime number that is not equal to the characteristic of L. Suppose that the polynomial xp − 1 splits over L. Then the polynomial xp − 1 has distinct roots, since its formal derivative pxp−1 is non-zero at each root of xp − 1. An element ω of L is said to be a primitive pth root of unity if ω p = 1 and ω 6= 1. The primitive pth roots of unity are the roots of the polynomial xp−1 +xp−2 +· · ·+1, since xp −1 = (x −1)(xp−1 + xp−2 + · · · + 1). Also the group of pth roots of unity in L is a cyclic group over order p which is generated by any primitive pth root of unity. Lemma 3.51 Let K be a field, and let p be a prime number that is not equal to the characteristic of K. If ω is a primitive pth root of unity in some extension field of K then the Galois group of the extension K(ω): K is Abelian. Proof Let L = K(ω). Then L is a splitting field for the polynomial xp − 1. Let σ and τ be K-automorphisms of L. Then σ(ω) and τ (ω) are roots of xp −1 (since the automorphisms σ and τ permute the roots of this polynomial) and therefore there exist non-negative integers q and r such that σ(ω) = ω q and τ (ω) = ω r . Then σ(τ (ω)) = ω qr = τ (σ(ω)). But there is at most one K-automorphism of L sending ω to ω qr . It follows that σ ◦ τ = τ ◦ σ. Thus the Galois group Γ(L: K) is Abelian, as required. Lemma 3.52 Let K be a field of characteristic zero and let M be a splitting field for the polynomial xp − c over K, where p is some prime number and c ∈ K. Then the Galois group Γ(M : K) of the extension M : K is solvable. Proof The result is trivial when c = 0, since M = K in this case. Suppose c 6= 0. The roots of the polynomial xp − c are distinct, and each pth root of unity is the ratio of two roots of xp − c. Therefore M = K(α, ω), 40

where αp = c and ω is some primitive pth root of unity. Now K(ω): K is a normal extension, since K(ω) is a splitting field for the polynomial xp − 1 over K (Theorem 3.32). On applying the Galois correspondence (Theorem 3.48), we see that Γ(M : K(ω)) is a normal subgroup of Γ(M : K), and Γ(M : K)/Γ(M : K(ω)) is isomorphic to Γ(K(ω): K). But Γ(K(ω): K) is Abelian (Lemma 3.51). It therefore suffices to show that Γ(M : K(ω)) is also Abelian. Now the field M is obtained from K(ω) by adjoining an element α satisfying αp = c. Therefore each automorphism σ in Γ(M : K(ω)) is uniquely determined by the value of σ(α). Moreover σ(α) is also a root of xp − c, and therefore σ(α) = αω j for some integer j. Thus if σ and τ are automorphisms of M belonging to Γ(M : K(ω)), and if σ(α) = αω j and τ (α) = αω k , then σ(τ (α)) = τ (σ(α)) = αω j+k , since σ(ω) = τ (ω) = ω. Therefore σ ◦ τ = τ ◦ σ. We deduce that Γ(M : K(ω)) is Abelian, and thus Γ(M : K) is solvable, as required. Lemma 3.53 Let f be a polynomial with coefficients in a field K of characteristic zero, and let K 0 = K(α), where α ∈ K 0 satisfies αp ∈ K for some prime number p. Then ΓK (f ) is solvable if and only if ΓK 0 (f ) is solvable. Proof Let N be a splitting field for the polynomial f (x)(xp − c) over K, where c = αp . Then N contains a splitting field L for f over K and a splitting field M for xp − c over K. Then N : K, L: K and M : K are Galois extensions. The Galois correspondence (Theorem 3.48) ensures that Γ(N : L) and Γ(N : M ) are normal subgroups of Γ(N : K). Moreover Γ(L: K) is isomorphic to Γ(N : K)/Γ(N : L), and Γ(M : K) is isomorphic to Γ(N : K)/Γ(N : M ). Now M and N are splitting fields for the polynomial xp − c over the fields K and L respectively. It follows from Lemma 3.52 that Γ(M : K) and Γ(N : L) are solvable. But if H is a normal subgroup of a finite group G then G is solvable if and only both H and G/H are solvable (Proposition 2.49). Therefore Γ(N : K) is solvable if and only if Γ(N : M ) is solvable. Also Γ(N : K) is solvable if and only if Γ(L: K) is solvable. It follows that Γ(N : M ) is solvable if and only if Γ(L: K) is solvable. But Γ(N : M ) ∼ = ΓM (f ) and Γ(L: K) ∼ = ΓK (f ), since L and N are splitting fields for f over K and M respectively. Thus ΓM (f ) is solvable if and only if ΓK (f ) is solvable. Now M is also a splitting field for the polynomial xp − c over K 0 , since K 0 = K(α), where α is a root of the polynomial xp − c. The above argument therefore shows that ΓM (f ) is solvable if and only if ΓK 0 (f ) is solvable. Therefore ΓK (f ) is solvable if and only if ΓK 0 (f ) is solvable, as required.

41

Theorem 3.54 Let f be a polynomial with coefficients in a field K of characteristic zero. Suppose that f is solvable by radicals. Then the Galois group ΓK (f ) of f is a solvable group. Proof The polynomial f is solvable by radicals. Therefore there exist fields K0 , K1 , . . . , Km such that K0 = K, the polynomial f splits over Km , and, for each integer i between 1 and m, the field Ki is obtained on adjoining to Ki−1 an element αi with the property that αipi ∈ Ki−1 for some prime number pi . Now ΓKm (f ) is solvable, since it is the trivial group consisting of the identity automorphism of Km only. Also Lemma 3.53 ensures that, for each i > 0, ΓKi (f ) is solvable if and only if ΓKi−1 (f ) is solvable. It follows that ΓK (f ) is solvable, as required. Lemma 3.55 Let p be a prime number, let K be a field whose characteristic is not equal to p, and let L: K be a Galois extension of K of degree p. Suppose that the polynomial xp − 1 splits over K. Then there exists α ∈ L such that L = K(α) and αp ∈ K. Proof The Galois group Γ(L: K) is a cyclic group of order p, since its order is equal to the degree p of the extension L: K. Let σ be a generator of Γ(L: K), let β be an element of L \ K, and let αj = β0 + ω j β1 + ω 2j β2 + · · · + ω (p−1)j βp−1 for j = 0, 1, . . . , p − 1, where β0 = β, βi = σ(βi−1 ) for i = 1, 2, . . . , p − 1, and ω is a primitive pth root of unity contained in K. Now σ(αj ) = ω −j αj for j = 0, 1, . . . , p − 1, since σ(ω) = ω, σ(βp−1 ) = β0 and ω p = 1. Therefore σ(αjp ) = αjp and hence αjp ∈ K for j = 0, 1, 2, . . . , p − 1. But α0 + α1 + α2 + · · · + αp−1 = pβ, since ω j is a root of the polynomial 1 + x + x2 + · · · + xp−1 for all integers j that are not divisible by p. Moreover pβ ∈ L \ K, since β ∈ L \ K and p 6= 0 in K. Therefore at least one of the elements α0 , α1 , . . . , αp−1 belongs to L \ K. Let α = αj , where αj ∈ L \ K. It follows from the Tower Law (Theorem 3.18) that [K(α), K] divides [L: K]. But [L: K] = p and p is prime. It follows that L = K(α). Moreover αp ∈ K, as required. Theorem 3.56 Let f be a polynomial with coefficients in a field K of characteristic zero. Suppose that the Galois group ΓK (f ) of f over K is solvable. Then f is solvable by radicals.

42

Proof Let ω be a primitive pth root of unity. Then ΓK(ω) (f ) is isomorphic to a subgroup of ΓK (f ) (Lemma 3.49) and is therefore solvable (Proposition 2.49). Moreover f is solvable by radicals over K if and only if f is solvable by radicals over K(ω), since K(ω) is obtained from K by adjoining an element ω whose pth power belongs to K. We may therefore assume, without loss of generality, that K contains a primitive pth root of unity for each prime p that divides |ΓK (f )|. The result is trivial when |ΓK (f )| = 1, since the polynomial f splits over K. We prove the result by induction on the degree |ΓK (f )| of the Galois group. Thus suppose that the result holds when the order of the Galois group is less than |ΓK (f )|. Let L be a splitting field for f over K. Then L: K is a Galois extension and Γ(L: K) ∼ = ΓK (f ). Now the solvable group Γ(L: K) contains a normal subgroup H for which the corresponding quotient group Γ(L: K)/H is a cyclic group of order p for some prime number p dividing Γ(L: K). Let M be the fixed field of H. Then Γ(L: M ) = H and Γ(M : K) ∼ = Γ(L: K)/H. (Theorem 3.48), and therefore [M : K] = |Γ(L: K)/H| = p. It follows from Lemma 3.55 that M = K(α) for some element α ∈ M satisfying αp ∈ K. Moreover ΓM (f ) ∼ = H, and H is solvable, since any subgroup of a solvable group is solvable (Proposition 2.49). The induction hypothesis ensures that f is solvable by radicals when considered as a polynomial with coefficients in M , and therefore the roots of f lie in some extension field of M obtained by successively adjoining radicals. But M is obtained from K by adjoining the radical α. Therefore f is solvable by radicals, when considered as a polynomial with coefficients in K, as required. On combining Theorem 3.54 and Theorem 3.56, we see that a polynomial with coefficients in a field K of characteristic zero is solvable by radicals if and only if its Galois group ΓK (f ) over K is a solvable group.

3.24

A quintic polynomial that is not solvable by radicals

Lemma 3.57 Let p be a prime number and let f be a polynomial of order p with rational coefficients. Suppose that f has exactly p − 2 real roots and is irreducible over the field Q of rational numbers. Then the Galois group of f over Q is isomorphic to the symmetric group Σp . Proof If α is a root of f then [Q(α): Q] = p since f is irreducible and deg f = p (Theorem 3.21). Thus if L is a splitting field extension for f over Q then [L: Q] = [L: Q(α)][Q(α): Q] by the Tower Law (Proposition 3.18) and therefore [L: Q] is divisible by p. But [L: Q] is the order of the Galois group G 43

of f , and therefore |G| is divisible by p. It follows from a theorem of Cauchy (Theorem 2.42) that G has an element of order p. Moreover an element of G is determined by its action on the roots of f . Thus an element of G is of order p if and only if it cyclically permutes the roots of f . The irreducibility of f ensures that f has distinct roots (Corollary 3.35). Let α1 and α2 be the two roots of f that are not real. Then α1 and α2 are complex conjugates of one another, since f has real coefficients. We have already seen that G contains an element of order p which cyclically permutes the roots of f . On taking an appropriate power of this element, we obtain an element σ of G that cyclically permutes the roots of f and sends α1 to α2 . We label the real roots α3 , α4 , . . . , αp of f so that αj = σ(αj−1 ) for j = 2, 3, 4, . . . , p. Then σ(αp ) = α1 . Now complex conjugation restricts to a Q-automorphism τ of L that interchanges α1 and α2 but fixes αj for j > 2. But if 2 ≤ j ≤ p then σ 1−j τ σ j−1 transposes the roots αj−1 and αj and fixes the remaining roots. But transpositions of this form generate the whole of the group of permutations of the roots. Therefore every permutation of the roots of f is realised by some element of the Galois group G of f , and thus G∼ = Σp , as required. Example Consider the quintic polynomial f where f (x) = x5 − 6x + 3. Eisenstein’s Irreducibility Criterion (Proposition 3.17) can be used to show that f is irreducible over Q. Now f (−2) = −17, f (−1) = 8, f (1) = −2 and f (2) = 23. The Intermediate Value Theorem ensures that f has at least 3 distinct real roots. If f had at least 4 distinct real roots then Rolle’s Theorem would ensure that the number of distinct real roots of f 0 and f 00 would be at least 3 and 2 respectively. But zero is the only root of f 00 since f 00 (x) = 20x3 . Therefore f must have exactly 3 distinct real roots. It follows from Lemma 3.57 that the Galois group of f is isomorphic to the symmetric group Σ5 . This group is not solvable. Theorem 3.54 then ensures that the polynomial f is not solvable by radicals over the field of rational numbers. The above example demonstrates that there cannot exist any general formula for obtaining the roots of a quintic polynomial from its coefficients in a finite number of steps involving only addition, subtraction, multiplication, division and the extraction of nth roots. For if such a general formula were to exist then every quintic polynomial with rational coefficients would be solvable by radicals.

44