Fermat’s Little Theorem

← Back to Number Theory

If p is prime and a is not divisible by p, then a^(p-1) is congruent to 1 (mod p). Used in primality testing (Fermat test), modular arithmetic optimizations, and the RSA cryptosystem. Generalizes to Euler’s theorem using Euler’s totient function.

mathematics-for-cs discrete-mathematics number-theory fermats