36 Chapter 1. Groups I Proof. If a G and a = 1, then a has order d 1, and d is a divisor of p. Since p is prime, d = p, and so G = a . In Example 1.45(iii), we saw that the additive group Im is cyclic of order m. Now multiplication Im × Im Im, given by [a][b] = [ab], is also a binary operation on Im (which is well-defined, by FCAA, Proposition 1.60) it is associative, commutative, and [1] is an identity element. However, Im is not a group under this operation because inverses may not exist for example, [0] has no multiplicative inverse. Proposition 1.52. The set U(Im), defined by U(Im) = {[r] Im : (r, m) = 1}, is a multiplicative group of order φ(m), where φ is the Euler φ-function. In partic- ular, if p is prime, then U(Ip) is a multiplicative group of order p 1. Remark. Theorem 2.46 says that U(Ip) is a cyclic group for every prime p. Proof. If (r, m) = 1 = (r , m), then (rr , m) = 1: if sr +tm = 1 and s r +t m = 1, then (sr + tm)(s r + t m) = 1 = (ss )rr + (st r + ts r + tt m)m hence U(Im) is closed under multiplication. We have already mentioned that mul- tiplication is associative and that [1] is the identity. If (a, m) = 1, then [a][x] = [1] can be solved for [x] in Im. Now (x, m) = 1, for rx + sm = 1 for some integer s, and so (x, m) = 1. Hence, [x] U(Im), and so each [r] U(Im) has an inverse in U(Im). Therefore, U(Im) is a group, and the definition of the Euler φ-function shows that |U(Im)| = φ(m). The last statement follows because φ(p) = p 1 when p is prime. Here is a group-theoretic proof of Fermat’s Theorem. Corollary 1.53 (Fermat). If p is prime and a Z, then ap a mod p. Proof. It suffices to show that [ap] = [a] in Ip. If [a] = [0], then [ap] = [a]p = [0]p = [0] = [a]. If [a] = [0], then [a] Ip ×, the multiplicative group of nonzero elements in Ip. By Corollary 1.50 to Lagrange’s Theorem, [a]p−1 = [1], because |Ip ×| = p−1. Multiplying by [a] gives the desired result: [ap] = [a]p = [a]. Therefore, ap a mod p. Euler generalized Fermat’s Theorem. Theorem 1.54 (Euler). If (r, m) = 1, then rφ(m) 1 mod m. Proof. Since |U(Im)| = φ(m), Corollary 1.50 gives [r]φ(m) = [1] for all [r] U(Im). In congruence notation, this says that if (r, m) = 1, then rφ(m) 1 mod m.
Previous Page Next Page