Fermat’s Little Theorem Calculator

How to use the calculator

1. Enter the base \(a\) in the Base (a) field. It must satisfy \(1 \le a < p\).
2. Enter a prime number in the Prime modulus (p) field (e.g. 2, 3, 5, 7, 11…).
3. Read the Result of a^(p−1) mod p — the remainder of \(a^{p-1}\) divided by \(p\).
4. Check Theorem holds? — it shows "Yes" when the remainder equals 1, which is the case for every valid input.

If you enter a non-prime modulus, a base outside the allowed range, or \(a \ge p\), the calculator shows an error message instead of a result.

What Fermat's Little Theorem means

Fermat's Little Theorem, stated by Pierre de Fermat in 1640, is one of the cornerstones of elementary number theory. It says that prime numbers impose a remarkably regular structure on powers: no matter which base \(a\) you choose (as long as \(p\) does not divide \(a\)), the power \(a^{p-1}\) always reduces to exactly 1 modulo \(p\). In other words, \(a^{p-1}\) is always a multiple of \(p\) plus one.

Why does this matter? First, it is a powerful computational shortcut. Instead of computing a huge power like \(3^{100}\) directly, you can reduce the exponent modulo \(p-1\) and work with much smaller numbers — a technique used constantly in modular arithmetic. Second, it underlies primality testing: if \(a^{p-1} \bmod p \ne 1\) for some \(a\), then \(p\) is definitely not prime. This is the idea behind Fermat's test and, in refined form, the Miller–Rabin test used to find large primes.

Third, the theorem is essential in cryptography. RSA encryption and decryption are essentially modular exponentiations, and Fermat's Little Theorem (together with its generalization, Euler's Theorem) is what guarantees that decrypting a message recovers the original. It also leads directly to the formula for finding multiplicative inverses modulo a prime: since \(a^{p-1} \equiv 1 \pmod{p}\), the inverse of \(a\) is simply \(a^{p-2} \bmod p\).

How to interpret the result

For any valid input — a prime \(p\) and a base \(a\) with \(1 \le a < p\) — the calculator will always return 1 and "Yes". That is precisely the content of the theorem: it is a statement about all such pairs, not just some. If you want to see why it fails for non-primes, try \(a = 2\), \(p = 9\): \(2^8 = 256\) and \(256 \bmod 9 = 4 \ne 1\). The theorem is a one-way test — a non-prime always fails for at least one base, while a pass does not by itself prove primality (see the note on Carmichael numbers below).

Assumptions, limitations and tips

• The modulus must be prime. The theorem does not hold for composite moduli in general. For composite \(n\), use Euler's Theorem with \(a^{\varphi(n)} \equiv 1 \pmod{n}\) instead, where \(\varphi\) is Euler's totient function and \(\gcd(a, n) = 1\).
• The base must not be divisible by \(p\). If \(a \equiv 0 \pmod{p}\), then \(a^{p-1} \equiv 0\), not 1. The equivalent form \(a^p \equiv a \pmod{p}\) still holds in that case.
• Fermat tests can be fooled. There exist composite numbers called Carmichael numbers (the smallest is 561) that satisfy \(a^{n-1} \equiv 1 \pmod{n}\) for every \(a\) coprime to \(n\). A single passing test is therefore not proof of primality.
• Work with reduced exponents. In hand calculations, combine the theorem with successive squaring: reduce exponents modulo \(p-1\) and intermediate products modulo \(p\) to keep numbers small.
• Related tools. For systems of congruences, see the Chinese Remainder Theorem calculator; for division in modular arithmetic, the multiplicative inverse modulo calculator is a natural companion.