Verify a^(p-1) ≡ 1 (mod p) for prime p and integer a. Fundamental to modular arithmetic and cryptography.
Last updated: May 2026 | By Patchworkr Team
| a | p | a^(p-1) mod p |
|---|---|---|
| 2 | 5 | 1 |
| 3 | 7 | 1 |
| 2 | 7 | 1 |
| 5 | 11 | 1 |
| 2 | 13 | 1 |
Fermat's Little Theorem states: if $p$ is a prime number and $a$ is an integer not divisible by $p$, then $a^6 \equiv 1 \pmod7$. This elegant result connects modular arithmetic with prime numbers and is foundational to number theory.
Named after French mathematician Pierre de Fermat, this theorem has extensive applications in cryptography (RSA encryption), primality testing, and computational mathematics. It's one of the most important results in elementary number theory and appears frequently in advanced algorithm design.
Conditions: $p$ must be prime and $a$ must not be a multiple of $p$.
It's the mathematical foundation of RSA encryption and other cryptographic systems that rely on modular exponentiation properties.
The theorem doesn't apply; for composite p, a^(p-1) mod p may not equal 1.
Then a ≡ 0 (mod p), so a^(p-1) ≡ 0 (mod p), not 1. The theorem requires a to be coprime to p.
If a^(n-1) ≢ 1 (mod n) for any a coprime to n, then n is definitely composite.
Euler's Theorem generalizes Fermat's Little Theorem: a^φ(n) ≡ 1 (mod n) for coprime a and n.
Not directly — the converse isn't always true (Carmichael numbers), but it helps eliminate composites efficiently.
It repeatedly squares and reduces mod p, computing a^(p-1) efficiently without huge intermediate values.
Composite numbers n where a^(n-1) ≡ 1 (mod n) for all a coprime to n, tricking simple primality tests.
Related Tools