Fermat's Little Theorem
Verify Fermat's Little Theorem for any base a and prime modulus p. Compute a^p mod p using modular exponentiation. Free online number theory tool.
About This Calculator
Fermat's Little Theorem Calculator verifies the congruence a^p ≡ a (mod p) for any non-negative integer base a and prime modulus p. The theorem is a cornerstone of number theory and modern cryptography, first stated by Pierre de Fermat in 1640 and later proved by Leonhard Euler (who generalized it as Euler's theorem).
The calculator uses fast modular exponentiation (exponentiation by squaring) to compute a^p mod p efficiently, even for large values. It also checks whether the given modulus p is actually prime and warns the user if it is not, since the theorem only guarantees correctness for prime moduli. The verification section shows both a^p mod p and a mod p side by side.
Example: For a = 3 and p = 7: 3^7 = 2187, and 2187 mod 7 = 3 (since 2187 = 7 x 312 + 3). Meanwhile, 3 mod 7 = 3, confirming 3^7 ≡ 3 (mod 7). The theorem holds ✓.
Applications: RSA encryption, primality testing (Fermat primality test), key exchange protocols, and digital signatures all rely on Fermat's Little Theorem or its generalizations.
Frequently Asked Questions
What is Fermat's Little Theorem?
Fermat's Little Theorem states that if p is a prime number and a is any integer not divisible by p, then a^(p-1) ≡ 1 (mod p). An equivalent formulation is a^p ≡ a (mod p) for all integers a. The theorem is named after Pierre de Fermat and was first stated in 1640.
How is Fermat's Little Theorem used in cryptography?
Fermat's Little Theorem is fundamental to RSA encryption, where it underpins the correctness of the algorithm. It is also used in primality testing (the Fermat primality test), key exchange protocols, and digital signatures. The theorem's efficiency stems from being able to compute a^p mod p quickly using modular exponentiation.
What is the difference between Fermat's Little Theorem and Fermat's Last Theorem?
Fermat's Little Theorem (a^p ≡ a mod p for prime p) is a fundamental result about modular arithmetic, proven by Euler and widely used in cryptography. Fermat's Last Theorem (no integer solutions to a^n + b^n = c^n for n > 2) is a vastly different problem about Diophantine equations, proven by Andrew Wiles in 1994.
Does Fermat's Little Theorem work for composite p?
No, Fermat's Little Theorem only guarantees a^p ≡ a (mod p) when p is prime. For composite numbers, the congruence may still hold for some values of a (these are called Fermat pseudoprimes or Carmichael numbers), but it is not guaranteed. This calculator warns when the modulus is not prime.
What are Carmichael numbers?
Carmichael numbers are composite numbers n for which a^n ≡ a (mod n) holds for all integers a coprime to n. They are also called Fermat pseudoprimes. The smallest Carmichael number is 561 = 3 x 11 x 17. They are important in cryptography because they pass the Fermat primality test despite being composite.
How is modular exponentiation computed efficiently?
Modular exponentiation uses the method of exponentiation by squaring (also called binary exponentiation). Instead of multiplying a by itself p times (O(p) operations), the algorithm processes the binary representation of p, squaring at each step and multiplying when the bit is 1. This takes only O(log p) steps, making it efficient even for large exponents.