Fermat's Little Theorem Calculator

Calculate fermat's little theorem — enter your values and get an accurate result with the underlying formula.

Quick Facts

Fermat's Little Theorem
a^(p-1) ≡ 1 (mod p)
Holds whenever p is prime and p does not divide a.
General form
a^p ≡ a (mod p)
True for every integer a, including multiples of p.
Modular inverse
a^(p-2) ≡ a^(-1) (mod p)
Valid when p is prime and p does not divide a.

Your Results

Calculated
a^(p-1) mod p
-
Fermat's Little Theorem result
a mod p
-
Reduced base
a^p mod p
-
General form, should equal a mod p
Modular inverse a^(-1) mod p
-
a^(p-2) mod p

Ready

Enter an integer a and a prime modulus p, then press Calculate.

How Fermat's Little Theorem Works

Fermat's Little Theorem is a foundational result in number theory: if p is a prime number and a is any integer not divisible by p, then ap-1 ≡ 1 (mod p) — meaning ap-1 leaves a remainder of exactly 1 when divided by p. This calculator raises your chosen base a to the power p-1, reduces it modulo p using fast modular exponentiation, and reports whether the congruence holds, along with two closely related quantities: the general form ap ≡ a (mod p), and the modular inverse ap-2 ≡ a-1 (mod p).

Formula and method

The calculator first checks that p is prime (trial division up to √p) — the theorem only holds for a prime modulus. It then computes ap-1 mod p using repeated squaring: instead of multiplying a by itself p-2 times, it squares the running result at each step and reduces mod p along the way, which keeps every intermediate number small and the computation exact even for large exponents. If p does not divide a, the result must equal 1; this is the theorem's classic statement. The calculator also evaluates ap mod p (the more general form, true for every integer a, even multiples of p) and ap-2 mod p, which is exactly the modular inverse of a when p is prime — a direct consequence of a · ap-2 ≡ ap-1 ≡ 1 (mod p).

Common sources of error

  • Using a composite modulus: Fermat's Little Theorem requires p to be prime. For composite p, a^(p-1) mod p is generally not 1 (this failure is the basis of the Fermat primality test and Carmichael numbers).
  • Forgetting the divisibility condition: if p divides a (so a ≡ 0 mod p), then a^(p-1) mod p equals 0, not 1 — the theorem's "≡ 1" form explicitly excludes this case, though a^p ≡ a (mod p) still holds.
  • Computing a^(p-1) directly: for large a or p, raising a to the power p-1 before reducing mod p produces astronomically large numbers; always reduce modulo p at every multiplication step (modular exponentiation), as this calculator does.

Checking your result

A quick sanity check: pick a small known case, such as a = 2, p = 7. Since 7 is prime and does not divide 2, you should get 26 mod 7 = 64 mod 7 = 1. If your inputs give ap-1 mod p ≠ 1 and p does not divide a, either p is not actually prime or there is an arithmetic mismatch — recheck both inputs.

Applications

Fermat's Little Theorem underlies several practical tools: the Fermat primality test uses it to quickly screen candidate primes (compute a^(n-1) mod n for a random base a — if it is not 1, n is definitely composite); RSA cryptography relies on a generalization of it (Euler's theorem) for key generation and correctness of encryption/decryption; and computing modular inverses via a^(p-2) mod p is a fast alternative to the extended Euclidean algorithm whenever the modulus is prime.

Frequently Asked Questions

What does Fermat's Little Theorem state?
If p is a prime number and a is an integer not divisible by p, then a^(p-1) ≡ 1 (mod p). Equivalently, for every integer a, a^p ≡ a (mod p), which holds even when p divides a.
Why does the modulus have to be prime?
The proof relies on the fact that when p is prime, the nonzero residues 1, 2, ..., p-1 modulo p form a group under multiplication, so multiplying all of them by a just permutes them. If p is composite this structure breaks down and a^(p-1) mod p is generally not 1, so the theorem does not apply.
How is Fermat's Little Theorem used in practice?
It underlies the Fermat primality test (checking a^(n-1) mod n for a possible prime n), fast computation of modular inverses via a^(p-2) mod p, and parts of RSA cryptography key generation and verification.
What happens if a is a multiple of p?
If p divides a, then a ≡ 0 (mod p), so a^(p-1) mod p equals 0, not 1. The theorem's congruence a^(p-1) ≡ 1 (mod p) is only guaranteed when a is not divisible by p; the more general form a^p ≡ a (mod p) still holds in every case.

Related calculators