Fermat's little theorem

Fermat is among the most prominent figures in the history of number theory.  One of the elegant properties about numbers he discovered is known as Fermat's little theorem, which states that if p is a prime number, then for any integer a, the number a ^p − a is divisible by p:

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.