ℕ
Fermat's Little Theorem
Undergraduate
Definition
If p is prime and a is not divisible by p, then a^(p-1) ≡ 1 (mod p).
Formulas
a^p-1 ≡ 1 ±odp
Fermat's Little Theorem
a^p ≡ a ±odp
Fermat's Little Theorem (variant)
Examples
Example 1
Find 2^10 mod 11 using Fermat's Little Theorem.
Example 2
Find 3^100 mod 7.
History
Discovered by: Pierre de Fermat (1640)
First mentioned in a letter to Mersenne; proved by Euler.
Applications
Cryptography
RSA, primality testing
Algorithms
Fast exponentiation
Related Documents
Was this page helpful?