Fermat's little theorem

Fermat's little theorem (not to be confused with Fermat's last theorem) states that if p is a prime number, then for any integer a,

Related Topics:
Fermat's last theorem - Prime number - Integer

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:a^p equiv a pmod{p},!

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

This means that if you take some number a, multiply it by itself p times and subtract a, the result is divisible by p (see modular arithmetic).

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The theorem is often stated in the following equivalent form: if p is a prime and a is an integer coprime to p, then

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:a^{p-1} equiv 1 pmod{p},!

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Fermat's little theorem is the basis for the Fermat primality test.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~