Fermat's Little Theorem - Generalizations

Generalizations

A slight generalization of the theorem, which immediately follows from it, is: if p is prime and m and n are positive integers such that

then for every integer a we have .

This follows as m is of the form, so

In this form, the theorem is used to justify the RSA public key encryption method.

Fermat's little theorem is generalized by Euler's theorem: for any modulus n and any integer a coprime to n, we have

where φ(n) denotes Euler's totient function (which counts the integers between 1 and n that are coprime to n). This is indeed a generalization, because if n = p is a prime number, then φ(p) = p − 1.

This can be further generalized to Carmichael's theorem.

Fermat's little theorem also has a nice generalization in finite fields.