283 Use Fermats little theorem to show that for p a prime ev

28.3

Use Fermat\'s little theorem to show that for p a prime, every integer a with a not identical to 0 (mod p) has a reciprocal modulo p. In Problem 28.3 above you proved that if p is a prime, then every

Solution

The definition of a reciprocal is: for a,b,nZ with n1 we call b, a reciprocal of a if ab1(modn).

Fermat’s Little Theorem states Let p be a prime. Then n^p n mod p for any integer n 1.

There\'s a corollary to Fermat’s Little Theorem which states:

Let p be a prime. Then n ^p1 1 mod p for any integer n 1 with (n, p) = 1

Now, for any integer a with a 0(mod p) => (a,p) =1

applying the corollary to Fermat’s Little Theorem,

   a ^p1 1 mod p

=> a. a^p-2 1 mod p

hence a has reciprocal a^p-2 modulo p.