If p is a prime number and a is a positive integer not divisible by p, then ap1 1(mod p)

Chapter 5, Problem 39

(choose chapter or problem)

If p is a prime number and a is a positive integer not divisible by p, then ap1 1(mod p) 444 Relations, Functions, and Matrices Section 5.6 The Mighty Mod Function 445 This result is known as Fermats little theorem (as opposed to the very famous Fermats last theorem mentioned in Section 2.4). Let S = 50, a, 2a, ,(p 1)a6, T = 50, 1, 2, , (p 1)6. Let f be given by f(ka) = (ka) mod p; that is, f computes the residue modulo p. a. Prove that f is a one-to-one function from S to T. b. Prove that f is an onto function. c. Prove that 3a # 2a c(p 1)a4 mod p = (p 1)! mod p d. Prove that ap1 1 (mod p) e. Let a = 4 and p = 7. Compute the set of residues modulo p of 54, 8, 12, , 246. f. Let a = 4 and p = 7. Show by direct computation that 46 1(mod 7).