Enter an integer (a) and a prime number (p) to apply Fermat's Little Theorem. The calculator computes a^(p-1) mod p, verifies whether the result equals 1, and shows the multiplicative inverse of a modulo p. You also get a step-by-step breakdown confirming whether the theorem holds for your chosen values.
a^(p−1) mod p
--
Theorem Holds?
--
p is Prime?
--
a mod p
--
Multiplicative Inverse of a mod p
--
Exponent Used (p−1)
--
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). In other words, raising a to the power (p−1) and dividing by p always leaves a remainder of 1. It was first stated by Pierre de Fermat in 1640 and later proved by Leonhard Euler.
When p is prime and gcd(a, p) = 1, the multiplicative inverse of a modulo p is a^(p−2) mod p. This works because Fermat's Little Theorem guarantees a^(p−1) ≡ 1 (mod p), so a × a^(p−2) ≡ 1 (mod p), making a^(p−2) the inverse of a.
To test if n is prime, pick a random integer a and compute a^(n−1) mod n. If the result is not 1, then n is definitely composite. If the result is 1, n is probably prime (but not guaranteed — numbers that pass for all a are called Carmichael numbers). This is known as the Fermat primality test.
Since 11 is prime and 19 is not divisible by 11, Fermat's Little Theorem tells us 19^(11−1) = 19^10 ≡ 1 (mod 11). For 19^11 mod 11, we write 19^11 = 19^10 × 19 ≡ 1 × 19 ≡ 19 mod 11 ≡ 8 (mod 11). So 19^11 mod 11 = 8.
Pierre de Fermat stated the theorem in 1640 in a letter, but did not provide a proof. The first known proof was given by Gottfried Wilhelm Leibniz around 1683, and a more celebrated proof was published by Leonhard Euler in 1736 using what is now known as Euler's theorem.
Fermat's Little Theorem is foundational in modern cryptography, particularly in RSA encryption, where modular exponentiation with large primes secures internet communications. It is also used in primality testing algorithms, pseudorandom number generation, and computing modular inverses in hash functions.
If a is divisible by p, Fermat's Little Theorem does not apply in its standard form (a^(p−1) ≡ 1 mod p). Instead, the more general statement is a^p ≡ a (mod p), which holds even when p divides a. In this case, a mod p = 0 and no multiplicative inverse exists.
Fermat's Little Theorem is a special case of Euler's Theorem. Euler's Theorem states a^φ(n) ≡ 1 (mod n) for any n where gcd(a, n) = 1, where φ(n) is Euler's totient function. When n = p (a prime), φ(p) = p−1, which reduces Euler's Theorem exactly to Fermat's Little Theorem.