How this instrument works
Fermat's little theorem makes a strong claim about primes: pick a prime p and any whole number a that p does not divide, raise a to the power p − 1, and divide the result by p — the remainder is 1, without exception. Why should that be true? Line up the nonzero remainders 1 through p − 1 and multiply each one by a, then reduce modulo p again; because p is prime, that operation just reshuffles the same p − 1 remainders into a new order, never producing a repeat or a zero. Multiply the whole reshuffled list together and it equals the original list times aᵖ⁻¹; cancel the shared product from both sides and aᵖ⁻¹ ≡ 1 mod p falls straight out.
The requirement that p not divide a is not a technicality to wave away. Set a to a multiple of p — 5 raised to the fourth power and reduced mod 5 — and the remainder collapses to 0, not 1, because a itself vanishes mod p before the exponent does any work; the golden case in this sheet deliberately keeps 3 and 7 free of that shared factor. Swap a composite number in for p and the guarantee disappears too: 2 raised to the eighth power is 256, and 256 divided by 9 leaves 4, not 1, even though 2 and 9 share no factor at all — primality of the modulus is doing real work here, not mere coprimality of the base.
Reversing the logic is where most people trip. Seeing aⁿ⁻¹ ≡ 1 mod n for some particular a tempts the conclusion that n itself must be prime — the basis of the classical Fermat primality test — but the implication only runs one direction. The number 561, equal to 3 × 11 × 17, is thoroughly composite, yet it passes aⁿ⁻¹ ≡ 1 mod n for every base a coprime to it, a curiosity discovered decades afterward and now named for Robert Carmichael. Pierre de Fermat set the prime-modulus claim down in a 1640 letter and left the general proof to Euler, who published one in 1736, nearly a century later; the theorem carries 'little' in its name only to keep it apart from Fermat's far more famous — and far harder to prove — Last Theorem.
- Enter the base as a whole number into the a field — any integer works, though the theorem's guarantee only kicks in once it is coprime to p.
- Enter a prime number into p (prime): 2, 3, 5, 7, 11, 13, and so on — the identity is stated for primes only, so a composite entry breaks it.
- Read aᵖ⁻¹ mod p: the sheet raises a to the power p − 1 and reduces the result modulo p in one pass.
- A result of 1 confirms the theorem held for that pair; try several values of a against the same p and watch every one land on 1.
- Set a to a multiple of p to see the one deliberate exception: the remainder drops to 0 instead of 1.
Worked example — 3 raised to the 6th, reduced mod 7
Set a to 3 and p (prime) to 7 in the sheet. It raises 3 to the power p − 1 = 6, giving 3⁶ = 729, then divides that figure by 7 and keeps only the remainder: 729 = 7 × 104 + 1, so aᵖ⁻¹ mod p reads exactly 1.0 — the field is built to land on 1 whenever the prime and base satisfy the theorem's condition.
Nothing about 3 and 7 is special beyond 7 being prime and not dividing 3. Run a from 1 through 6 against the same p (prime) = 7 and the result field returns 1 every single time — six separate confirmations of the identical claim, all produced by one fixed prime. Change p to a composite number such as 8, though, and that streak breaks almost immediately, which is the entire reason the field only behaves this way when p is genuinely prime.
Questions
What does Fermat's little theorem say?
For any prime p and any integer a that p does not divide, raising a to the power p − 1 and reducing the result modulo p always leaves a remainder of 1 — written aᵖ⁻¹ ≡ 1 (mod p). A wider version, aᵖ ≡ a (mod p), holds for every integer a, including multiples of p, where it correctly reduces to a ≡ 0.
Why must p be a prime number for the theorem to hold?
Primality is what keeps the p − 1 nonzero remainders from colliding when each is multiplied by a — a rearrangement that stays lossless only because a prime modulus has no smaller factors to force a repeat. Make p composite instead and the guarantee can fail outright: 2 raised to the eighth power divided by 9 leaves a remainder of 4, not 1, even though 2 and 9 share no common factor.
What happens if a is a multiple of p?
The remainder collapses to 0 instead of 1, because a itself is congruent to 0 modulo p before any exponent is applied — 5 raised to the fourth power, reduced mod 5, returns 0 for exactly this reason. That is why the theorem's standard statement excludes the case where p divides a; this field will show 0 rather than 1 whenever you enter such a pair.
Does a result of 1 prove that p is prime?
No — the implication runs one way only. A composite number can still satisfy aⁿ⁻¹ ≡ 1 (mod n) for a particular base, and 561, equal to 3 × 11 × 17, does so for every base coprime to it despite being thoroughly composite; such numbers are called Carmichael numbers, and their existence is exactly why the Fermat test is a probable-primality check rather than a proof.
How does this identity connect to RSA encryption?
RSA's decryption step relies on Euler's theorem, the direct generalization of this identity to composite moduli built from two primes, so that raising a ciphertext to the matching private exponent returns the original message exactly. Fermat's little theorem is the special case that makes the generalization provable in the first place, and fast modular exponentiation of exactly this kind is what makes large-key RSA practical to compute.
Why is it called Fermat's 'little' theorem?
The word 'little' is a later nickname, added to separate this identity from Fermat's far more famous Last Theorem, the claim that xⁿ + yⁿ = zⁿ has no whole-number solutions once n exceeds 2 — a statement Fermat also left unproved and that took over three centuries to settle. This theorem, by contrast, is comparatively tame: Euler published a full proof within a century of Fermat first writing it down.