Fermat’s Little
Theorem
If p is a prime and a is an integer and a is not divisible by p, then
a p−1 ≡1 ( mod p )
Furthermore, for every integer a, we get
p
a ≡ a ( mod p )
Example: Find 7 222
mod 11.
Solution: Given,
222
7 mod 11
Here, 7 is not divisible by 11 so
According to Fermat’s Little Theorem,
a p−1 ≡1 ( mod p )
By comparing these two we get,
a=7, p=11.
Now,
11−1
7 ≡1 ( mod 11 )
→ 710 ≡ 1 ( mod 11 )
Theorem
If p is a prime and a is an integer and a is not divisible by p, then
a p−1 ≡1 ( mod p )
Furthermore, for every integer a, we get
p
a ≡ a ( mod p )
Example: Find 7 222
mod 11.
Solution: Given,
222
7 mod 11
Here, 7 is not divisible by 11 so
According to Fermat’s Little Theorem,
a p−1 ≡1 ( mod p )
By comparing these two we get,
a=7, p=11.
Now,
11−1
7 ≡1 ( mod 11 )
→ 710 ≡ 1 ( mod 11 )
