Let p be a prime number and let a be an integer that is not

Let p be a prime number, and let a be an integer that is not divisible by p. Prove that the congruence equation ax = 1 mod p has a solution epsilon Z.

Solution

a and p are coprime

By Fermat\'s Little theorem

a^{p-1}=1 mod p

Case 1. p=2

Then, x=1

ie a=1 mod p

Case 2.p>2

a^{p-1}=1 mod p

a*a^{p-2}=1 mod p

HEnce, x=a^{p-2}