**Fermat’s theorem:**

It states that if p is a prime no. and a is a positive integer not divisible by p then

ap-1 = I mod p

If p is a prime no. and n is a positive integer not divisible by p then according to the modular arithmetic the set of numbers {0 mod p, a mod p, 2a mod p,…., (p-1)a mod p} is identical to set {0, 1, 2, …., p-1}

Since 0 mod p = 0, the first element of two sets are equal.

Now, multiplying the remaining elements of two sets and taking modulus, we get

[(1a mod p)(2a mod p)….((p-1)a mod p)]

Using product rule on RHS

ap-1 (p-1) 1 mod p = (p-1) 1 mod p

Cancelling (p-1) 1 on both sides

ap-1 mod p = 1 mod p

or

ap-1 ≡ 1 mod p

**Euler’s theorem:**

It states that for every a and n that are relatively prime

aϕ(n) ≡ 1 mod n

e.g. a = 3, n = 10, ϕ(n) = 4

34 = 1 mod 10

81 = 1 mod 10