Fermat's Little Theorem Calculator
Enter an integer a and a prime number p to verify Fermat's Little Theorem. The calculator checks that a^(p-1) mod p = 1 (when gcd(a, p) = 1), computes a^p mod p, finds the modular multiplicative inverse of a (mod p), and shows every step of the calculation. Switch between the two standard forms of the theorem using the mode selector.
What is Fermat's Little Theorem?
Fermat's Little Theorem, published by Pierre de Fermat in 1640, is one of the most useful results in number theory. It states that if p is a prime number and a is any integer not divisible by p, then a raised to the power (p-1) is congruent to 1 modulo p, written as a^(p-1) ≡ 1 (mod p). An equivalent general form, which holds for every integer a (including multiples of p), says that a^p ≡ a (mod p). The theorem provides a fast way to reduce huge exponents, test whether a number might be prime, and compute modular multiplicative inverses, all of which are fundamental to modern cryptographic systems such as RSA.
The two forms of the theorem
The coprime form, a^(p-1) ≡ 1 (mod p), requires gcd(a, p) = 1, meaning a and p share no common factor other than 1. This is automatic whenever p is prime and a is not a multiple of p. The general form, a^p ≡ a (mod p), needs no such restriction: it works even when p divides a, in which case both sides equal 0. The coprime form is the one most commonly quoted, and it is the version used to derive the modular inverse formula below.
How to compute a^n mod p using Fermat
Suppose you want 3^100 mod 7. Because 7 is prime and gcd(3, 7) = 1, Fermat tells you 3^6 ≡ 1 (mod 7). Write 100 = 6 x 16 + 4. Then 3^100 = (3^6)^16 x 3^4 ≡ 1^16 x 81 ≡ 81 mod 7. Since 81 = 11 x 7 + 4, the answer is 4. This exponent-reduction technique is the heart of RSA decryption: when the exponent is a multiple of (p-1), the whole expression collapses to 1, making calculations that would otherwise require millions of multiplications almost instant.
Modular multiplicative inverse
The modular inverse of a modulo p is the integer x such that a x x ≡ 1 (mod p). Fermat's theorem gives a clean formula: since a^(p-1) ≡ 1, multiply both sides by a^(-1) to get a^(p-2) ≡ a^(-1) (mod p). Therefore, the modular inverse is just a^(p-2) mod p, which this calculator computes using fast modular exponentiation. The inverse exists if and only if gcd(a, p) = 1. Modular inverses are used to solve linear congruences (ax ≡ b mod p means x ≡ b x a^(-1) mod p) and appear throughout cryptographic key scheduling.
Fermat primality test and Carmichael numbers
Because a^(p-1) mod p = 1 for every prime p and every valid base a, you can test whether a candidate number n is prime by picking a random base and checking whether a^(n-1) mod n equals 1. If it does not, n is definitely composite. If it does, n is probably prime, but not certainly: composite numbers called Carmichael numbers (for example 561 = 3 x 11 x 17) pass the Fermat test for every base coprime to them. A more robust alternative is the Miller-Rabin test, which eliminates Carmichael numbers by checking additional conditions. For everyday use, the Fermat test with several random bases gives very strong probabilistic confidence.
Fermat primality test results for small bases
| Prime p | Base a | a^(p-1) mod p | Theorem holds? |
|---|---|---|---|
| 5 | 2 | 1 | Yes |
| 5 | 3 | 1 | Yes |
| 7 | 2 | 1 | Yes |
| 7 | 3 | 1 | Yes |
| 11 | 2 | 1 | Yes |
| 11 | 5 | 1 | Yes |
| 13 | 2 | 1 | Yes |
| 13 | 6 | 1 | Yes |
| 17 | 3 | 1 | Yes |
| 23 | 5 | 1 | Yes |
Examples of a^(p-1) mod p for small primes p and bases a. All entries equal 1, confirming the theorem. A composite passing the test for all bases shown is a Carmichael number.
Frequently asked questions
What is Fermat's Little Theorem in simple terms?
If you pick any prime number p and any integer a that is not a multiple of p, then raising a to the power (p-1) and dividing by p always leaves a remainder of 1. For example, 3^6 mod 7 = 729 mod 7 = 1. The theorem works because the remainders 1, 2, ..., (p-1) cycle through all non-zero values under repeated multiplication, and the cycle length must divide (p-1).
What is the difference between the two forms of the theorem?
The coprime form, a^(p-1) ≡ 1 (mod p), applies only when gcd(a, p) = 1 (a is not divisible by p). It is the most useful form in calculations. The general form, a^p ≡ a (mod p), holds for every integer a including multiples of p. When p divides a, both sides are 0 mod p. When p does not divide a, the two forms say the same thing after multiplying the coprime form by a.
How do I use Fermat's theorem to simplify a large exponent?
Divide the exponent by (p-1) and keep the remainder (call it r). Then a^exponent ≡ a^r (mod p), because every full block of (p-1) contributes a factor of 1. For instance, 2^1000 mod 13: since 13 is prime, 2^12 ≡ 1 (mod 13). Divide 1000 by 12: 1000 = 83 x 12 + 4, so 2^1000 ≡ 2^4 = 16 ≡ 3 (mod 13).
What does it mean when gcd(a, p) is not 1?
It means a and p share a common factor. Because p is prime, the only way gcd(a, p) > 1 is if p divides a exactly. In that case a^(p-1) mod p = 0, not 1, so the coprime form of the theorem does not hold. The general form a^p ≡ a (mod p) still works: both sides equal 0. The modular inverse of a does not exist when gcd(a, p) > 1.
Why does the Fermat primality test sometimes give wrong answers?
Some composite numbers, called Carmichael numbers, satisfy a^(n-1) ≡ 1 (mod n) for every base a coprime to n, even though n is not prime. The smallest is 561. The test can also fail for bases that share a factor with the composite n. Using multiple random bases dramatically reduces the false-positive rate, but to eliminate it entirely you need the Miller-Rabin primality test.
How is Fermat's Little Theorem used in RSA encryption?
RSA chooses a modulus n = p x q (product of two large primes) and uses Euler's theorem (a generalization of Fermat's) to guarantee that decryption undoes encryption. For each prime factor, Fermat ensures that a^(p-1) ≡ 1 (mod p), which means encrypting then decrypting a message recovers the original. The modular inverse formula (a^(-1) = a^(p-2) mod p) is also used to compute private keys from public exponents.
What are Carmichael numbers?
Carmichael numbers are composite integers n such that a^(n-1) ≡ 1 (mod n) for every integer a coprime to n. They are the false positives of the Fermat primality test. The smallest is 561 = 3 x 11 x 17. A positive integer n is a Carmichael number if and only if it is square-free and, for every prime factor p of n, (p-1) divides (n-1). There are infinitely many Carmichael numbers, but they are rare enough that probabilistic Fermat testing with random bases is still highly reliable in practice.