《Discrete Mathematics II教学-华南理工》Section 17 Fermats and Eulers Theorem.pdfVIP

IV.20 Fermat’s and Euler’s Theorems 1 Section IV.20. Fermat’s and Euler’s Theorems Note. The results of this section really belong in a class on number theory. The results relate to modular arithmetic. We have seen that the cyclic groups Zn and the fields Zp where p is prime, are of particular interest, so the relevance of modular arithmetic should not be a huge surprise. Exercise 18.37. Let R, +, · be a ring with unity and let U be the set of all units in R. Then U, · is a group. Proof. First, we show that U is closed under ·. Let u, v ∈ U . Then for some u , v ∈ U we have u · u = u · u = 1 and v · v = v · v = 1. Then (v · u ) · (u · v) = v (u u)v = v 1v = v v = 1, and (u · v) · (v · u ) = u(vv )u = u1u = uu = 1. So uv ∈ U and U is closed under ·. Associativity of · is inherited from R (G1). Since 1 · 1 = 1, then 1 ∈ U (G ). For u ∈ U , there is u ∈ U as above where u ·u = 1 2 (G ). Therefore, U, · is a group. 2 Corollary. For any field, the nonzero elements form a group under the field mul- tiplication. Proof. In a field, all nonzero elements are units. So this follows from Exercise 18.37. IV.20 Fermat’s and Euler’s Theorems 2 Theorem 20.1. Little Theorem of Fermat. If a ∈ Z and p is a prime not dividing a, then p divides ap −1 − 1. That is, ap −1 ≡ 1 (mod p) for a = 0 (mod p). Corollary 20.2. If a ∈ Z, then ap ≡ a (mod p) for any prime p . Exercise 20.4. Use Fermat’s theorem to find the remainder of 347 when it is divided by 23. Solution. Since p = 23 is prime, we use Fermat’s