Engineering / Mathematics — Integer Foundations
Fermat's Little Theorem and Euler's Theorem
Fermat's little theorem, Euler's generalisation, and their role as the foundation of primality testing and public-key cryptography.
Executive summary
Fermat's little theorem says that raising any unit to the power of the group order returns the identity. Stated that way it is a special case of Lagrange's theorem and requires no number theory at all.
Its importance is entirely computational: it provides a fast necessary condition for primality, and it is the identity that makes RSA decryption invert RSA encryption.
Learning objectives
- State Fermat's little theorem and Euler's generalisation.
- Derive both from Lagrange's theorem.
- Apply the result to compute inverses and to test compositeness.
01The theorems
Fermat's little theorem
If p is prime and p ∤ a, then a^{p−1} ≡ 1 (mod p).
Equivalently, for every integer a, a^p ≡ a (mod p).
Euler's theorem
If gcd(a, n) = 1, then a^{φ(n)} ≡ 1 (mod n).
Euler's theorem contains Fermat's as the case n = p, where φ(p) = p − 1. Both are instances of a single group-theoretic fact: in a finite group of order m, every element satisfies g^m = e, because the order of an element divides the order of the group.
02Computational consequences
Fast inverses
For prime p, the inverse of a is a^{p−2} mod p, computable by repeated squaring without running extended Euclid.
Exponent reduction
Exponents can be reduced modulo φ(n) before exponentiating, since a^{k} = a^{k mod φ(n)} when gcd(a,n) = 1.
Compositeness certificate
If a^{n−1} ≢ 1 (mod n) for some a coprime to n, then n is definitely composite — no factorisation needed.
RSA correctness
Choosing ed ≡ 1 (mod φ(n)) makes (a^e)^d = a^{1 + kφ(n)} = a, which is exactly why decryption inverts encryption.
The third of these is the Fermat primality test, and it is the starting point for all practical primality testing. Its weakness is that the converse fails.
03Where the converse fails
This gap is the entire reason the Miller–Rabin test exists. It strengthens the Fermat condition by additionally checking the square roots of 1 encountered during the exponentiation, and no composite survives that stronger test for more than a quarter of the possible bases.
| Test | Condition checked | Composites that pass |
|---|---|---|
| Fermat | a^{n−1} ≡ 1 | Pseudoprimes; Carmichael numbers pass for all bases |
| Miller–Rabin | Fermat plus non-trivial square roots of 1 | At most 1/4 of bases, for every composite |
04Frequently asked questions
Why is a^p ≡ a (mod p) the better statement of Fermat's theorem?
Because it holds for every integer a with no coprimality hypothesis. When p divides a both sides are 0 mod p, so the exceptional case is absorbed rather than excluded.
Can Euler's theorem be improved?
Yes. The smallest exponent working for all units is the Carmichael function λ(n), which divides φ(n) and is often strictly smaller. For n = 8, φ(n) = 4 but λ(n) = 2, since every odd square is 1 mod 8.
Does the theorem give an efficient primality test on its own?
It gives an efficient compositeness test — a failure is conclusive. It gives no proof of primality, because Carmichael numbers pass for every base, so passing establishes nothing definite.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 25-28.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.