What Is Fermat's Little Theorem?
Fermat's Little Theorem is a cornerstone of number theory. It states that if p is a prime number and a is an integer not divisible by p (so gcd(a, p) = 1), then a raised to the power (p − 1) leaves a remainder of 1 when divided by p. In symbols: \(a^{p-1} \equiv 1 \pmod{p}\). A more general version holds for every integer a: \(a^{p} \equiv a \pmod{p}\).
$$a^{\,p-1} \equiv 1 \pmod{p}$$
How to Use This Calculator
Enter a base value a and a value p. The calculator checks whether p is prime, computes gcd(a, p), and evaluates both \(a^{p-1} \bmod p\) and \(a^{p} \bmod p\) using fast modular exponentiation. When p is prime and gcd(a, p) = 1, the first result will always be 1 — confirming the theorem. If those conditions are not met, the \(a^{p-1}\) result is shown as n/a because the theorem does not guarantee a value of 1.
The Formula Explained
Modular exponentiation repeatedly squares the base while reducing modulo p, so even large exponents stay manageable. The theorem is the basis of primality tests (the Fermat test), RSA encryption key math, and computing modular inverses, since \(a^{p-2} \bmod p\) gives the inverse of a modulo a prime p.
Worked Example
Let a = 2 and p = 7. Since 7 is prime and gcd(2, 7) = 1, we expect $$2^{6} \bmod 7 = 64 \bmod 7 = 1.$$ ✔ The general form gives $$2^{7} \bmod 7 = 128 \bmod 7 = 2,$$ which equals \(a \bmod 7 = 2\). ✔
FAQ
What if p is not prime? The theorem may fail. The calculator flags p as not prime and only the general \(a^{p} \bmod p\) value is meaningful, not necessarily equal to a.
What if a is a multiple of p? Then gcd(a, p) ≠ 1, so \(a^{p-1} \bmod p\) will not be 1 (it is 0). The general form \(a^{p} \equiv a\) still holds.
Can I use it to find modular inverses? Yes — for a prime p, \(a^{p-2} \bmod p\) is the multiplicative inverse of a modulo p.
