Fermat's Little Theorem Calculator

Verify and apply Fermat's Little Theorem: ap-1 ≡ 1 (mod p) for prime p, with modular exponentiation steps.

Enter Values

Result

ap-1 mod p
1
Theorem Verified
Base (a)3
Prime (p)7
Exponent (p-1)6
a mod p3
ap-1 mod p1
Is p prime?Yes

Step-by-Step Solution

3^6 mod 7 = 729 mod 7 = 1

Understanding Fermat's Little Theorem

Fermat's Little Theorem, stated by Pierre de Fermat in 1640, is one of the fundamental results in number theory. It states that if p is a prime number and a is any integer not divisible by p, then ap-1 ≡ 1 (mod p). Equivalently, for any integer a, ap ≡ a (mod p). This theorem is the foundation of many results in modular arithmetic, primality testing, and modern cryptography.

Key Concepts

The Theorem Statement

If p is prime and gcd(a, p) = 1, then a raised to the power p-1 is congruent to 1 modulo p.

a^(p-1) ≡ 1 (mod p)

Alternative Form

For any integer a (even if divisible by p): a^p is congruent to a modulo p.

a^p ≡ a (mod p)

Modular Inverse

Using the theorem, the modular inverse of a modulo p is a^(p-2) mod p.

a^(-1) ≡ a^(p-2) (mod p)

Fermat Primality Test

If a^(n-1) is not congruent to 1 mod n, then n is definitely composite. Used as a fast probabilistic primality test.

a^(n-1) ≠ 1 (mod n) ⇒ composite

Binary Exponentiation

Efficiently compute a^n mod m by repeatedly squaring, reducing computation from O(n) to O(log n).

a^13 = a^8 · a^4 · a^1

Euler's Generalization

Euler's theorem generalizes Fermat's: a^phi(n) ≡ 1 (mod n) where phi is Euler's totient function.

a^φ(n) ≡ 1 (mod n)

Applications

Fermat's Little Theorem is widely used in cryptography (RSA algorithm relies on it), primality testing (Fermat test, Miller-Rabin test), computing modular inverses, simplifying large exponentiations in modular arithmetic, and in competitive programming. It enables reducing very large exponents modulo p-1 before computing, which dramatically speeds up calculations.

Important Notes

  • The theorem only applies when p is prime. For composite numbers, use Euler's theorem instead.
  • The base a must not be divisible by p (i.e., gcd(a, p) = 1).
  • Carmichael numbers are composites that satisfy a^(n-1) ≡ 1 (mod n) for all coprime a, making the Fermat test unreliable for them.
  • Binary exponentiation (repeated squaring) is the standard method for efficient modular exponentiation.
  • To compute a^n mod p for very large n, first reduce n modulo (p-1) using Fermat's theorem.