Last verified · v1.0

Calculator · math

Fermat's Little Theorem Calculator

Calculate Fermat's Little Theorem results: verify a^(p-1) ≡ 1 (mod p), compute modular exponents, and find modular inverses for any prime modulus.

FreeInstantNo signupOpen source

Inputs

Base (a)

Exponent (n)

Prime Modulus (p)

Calculation Mode

Result (a^n mod p)

—

Get a plain-English breakdown of your result with practical next steps.

Result (a^n mod p)—

The formula

How the
result is
computed.

What Is Fermat's Little Theorem?

Fermat's Little Theorem, first stated by Pierre de Fermat in 1640 and formally proved by Leonhard Euler in 1736, is one of the most important results in elementary number theory. The theorem establishes a precise congruence relationship between integers and prime numbers, forming the mathematical backbone of RSA encryption, digital signatures, and probabilistic primality testing used in modern computer security.

The Core Formula

The theorem takes two equivalent forms. For any integer a and prime p:

General form: a^p ≡ a (mod p) — valid for all integers a
Reduced form: a^p−1 ≡ 1 (mod p) — valid when gcd(a, p) = 1

The reduced form applies whenever a is not a multiple of p. Under that condition, a and p share no common factor greater than 1, which guarantees that a has a well-defined multiplicative inverse modulo p.

Variable Reference

Base (a): Any integer. In cryptographic contexts, a commonly represents a plaintext message, a key component, or a randomly chosen witness for primality testing.
Prime Modulus (p): A prime number serving as the modulus. Primality is a strict requirement — the theorem does not hold for arbitrary composite moduli without invoking Euler's generalization.
Exponent (n): The power to which a is raised when computing aⁿ mod p directly. Fermat's theorem permits replacing n with n mod (p−1), dramatically reducing the size of the exponent before calculation.

Step-by-Step Calculation Method

Confirm that p is prime using a reliable primality test such as trial division for small values or Miller-Rabin for large values.
Verify that gcd(a, p) = 1 — that is, a is not divisible by p.
To compute aⁿ mod p efficiently, reduce the exponent: compute r = n mod (p−1).
Evaluate a^r mod p using repeated squaring (binary exponentiation), which completes in O(log r) multiplications.

Worked Examples

Example 1 — Verifying the Reduced Form

Let a = 3, p = 7. Since gcd(3, 7) = 1, the reduced form applies. Compute 3⁶ = 729. Dividing: 729 = 104 × 7 + 1, so 3⁶ ≡ 1 (mod 7). The theorem holds.

Example 2 — Reducing a Large Exponent

Compute 2¹⁰⁰ mod 7. With p = 7, reduce the exponent: r = 100 mod 6 = 4. Therefore 2¹⁰⁰ ≡ 2⁴ = 16 ≡ 2 (mod 7). This result is obtained without evaluating the 31-digit number 2¹⁰⁰ directly.

Example 3 — Computing a Modular Inverse

The modular inverse of a modulo p equals a^p−2 mod p. For a = 3 and p = 7: inverse = 3⁵ mod 7 = 243 mod 7 = 5. Verification: 3 × 5 = 15 = 2 × 7 + 1, confirming 3 × 5 ≡ 1 (mod 7).

Real-World Applications

RSA Cryptography

RSA encryption exploits Fermat's theorem through Euler's generalization. During key generation, two primes p and q — each typically containing 150 or more decimal digits in modern 2048-bit implementations — are chosen. Public exponent e and private exponent d satisfy ed ≡ 1 (mod (p−1)(q−1)), so that encrypting a message m as m^e and decrypting as (m^e)^d recovers m exactly.

Primality Testing

The Fermat primality test checks a candidate n by verifying aⁿ⁻¹ ≡ 1 (mod n) for multiple random bases a. Failure for any single base proves n is composite. This principle underlies the Miller-Rabin algorithm, which powers primality testing in OpenSSL, Python's sympy library, and Java's BigInteger.isProbablePrime method.

Sources and Methodology

The calculations performed by this tool follow the congruence arithmetic framework established in Congruences and Congruence Equations (University of California, Irvine, Math 180A) and the algorithmic treatment of modular exponentiation in Lecture Notes on Fermat's Little Theorem (University of South Carolina, CS 2112). Theoretical foundations draw from Theory of Numbers (Kansas State University) and the worked problem sets in Carnegie Mellon University ARML Number Theory Solutions.

Reference

Frequently asked questions

What is Fermat's Little Theorem and why is it important in mathematics?

Fermat's Little Theorem states that for any integer a and prime p, a^p is congruent to a modulo p. When gcd(a, p) = 1, this simplifies to a^(p-1) ≡ 1 (mod p). First stated in 1640 by Pierre de Fermat and proved by Leonhard Euler in 1736, the theorem is foundational in number theory and directly enables RSA encryption, digital signatures, and probabilistic primality testing algorithms used throughout modern cryptography and computer science.

What is the difference between the general and reduced forms of Fermat's Little Theorem?

The general form, a^p ≡ a (mod p), holds for any integer a and prime p with no restrictions on a. The reduced form, a^(p-1) ≡ 1 (mod p), additionally requires gcd(a, p) = 1, meaning a is not divisible by p. For example, with a = 3 and p = 7: the general form gives 3^7 = 2187 ≡ 3 (mod 7), while the reduced form gives 3^6 = 729 ≡ 1 (mod 7). Both forms are consistent and mathematically equivalent under the gcd condition.

How does Fermat's Little Theorem simplify computation of large modular exponents?

When computing a^n mod p for a prime p with gcd(a, p) = 1, Fermat's Little Theorem allows replacement of n with r = n mod (p-1), since a^(p-1) ≡ 1 (mod p) means the powers of a repeat with period p-1. For example, to compute 2^100 mod 7: since p-1 = 6 and 100 mod 6 = 4, the result equals 2^4 = 16 ≡ 2 (mod 7). This avoids computing the 31-digit number 2^100 and makes large-exponent modular arithmetic practical in cryptographic applications.

Why must the modulus p be a prime number for Fermat's Little Theorem to apply?

Fermat's Little Theorem requires p to be prime because the proof depends on the set {1, 2, ..., p-1} forming a complete multiplicative group under multiplication modulo p, a property that holds exclusively for prime moduli. For composite moduli the theorem generally fails: with n = 9 and a = 2, computing 2^8 = 256 gives 256 mod 9 = 4, not 1, even though gcd(2, 9) = 1. Euler's theorem generalizes the result to composite moduli by replacing p-1 with the Euler totient function phi(n).

How is Fermat's Little Theorem applied in RSA encryption?

RSA encryption uses Fermat's theorem — through Euler's generalization — to guarantee that encryption and decryption are exact inverses. Two large primes p and q, each containing 150 or more decimal digits in 2048-bit implementations, are selected. Public exponent e and private exponent d satisfy ed ≡ 1 (mod (p-1)(q-1)). Encrypting message m as m^e mod n and then applying decryption as (m^e)^d mod n returns m exactly, because Fermat's theorem ensures the composite exponent ed reduces to 1 modulo the group order.

What are Carmichael numbers and how do they affect the Fermat primality test?

Carmichael numbers are composite integers n that satisfy a^(n-1) ≡ 1 (mod n) for every integer a with gcd(a, n) = 1, perfectly mimicking prime behavior under the Fermat test. The smallest Carmichael number is 561 = 3 × 11 × 17. Because Carmichael numbers fool the basic Fermat primality test for every valid base a, cryptographic libraries use the Miller-Rabin test instead, which examines additional structural properties of modular arithmetic and reliably identifies Carmichael numbers as composite with very high probability.