a p ≡ a (mod p).
An alternative version of Fermat's little theorem states that if a is not divisible by p, then the number a p − 1 − 1 is a multiple of p:
a p − 1 ≡ 1 (mod p).
Fermat's little theorem was proved by Euler and can be generalized by Euler's theorem: if a and n are relatively prime, then
a φ(n) ≡ 1 (mod n),
where φ(n) is the number of integers between 1 and n that are relatively prime with n. Euler's theorem form the basis of the RSA encryption system.