Wilson & Fermat
Three named theorems turn nightmarish exponents and factorials into 1. Fermat’s little theorem: for a prime p and a not divisible by p, a^(p−1) ≡ 1 (mod p) — so reduce the exponent mod (p−1) before computing. Euler’s theorem generalises this to any modulus n coprime to a: a^φ(n) ≡ 1 (mod n), where φ(n) counts integers below n that are coprime to n (φ(p) = p−1, φ(p^k) = p^k − p^(k−1)). This is the standard tool for "last two digits" (mod 100, φ(100) = 40). Wilson’s theorem handles factorials: for a prime p, (p−1)! ≡ −1 (mod p), and its corollary (p−2)! ≡ 1 (mod p). The make-or-break condition for Fermat and Euler is coprimality — if a shares a factor with the modulus, neither applies, and you must split using the Chinese Remainder idea or reduce directly. Reduce the exponent first; only then apply the theorem.
✅ Solved examples
✏️ Practice — try these, take hints as needed
📝 Topic test — 8 questions
Auto-graded with full solutions; saved to your dashboard. Use the calculator and formula sheet (top-right) any time.
Formula Reference Sheet
Modular reduction core
| Notation | a ≡ r (mod n) means n divides (a − r) |
|---|---|
| Sum / difference | (a ± b) mod n = (a mod n ± b mod n) mod n |
| Product | (a × b) mod n = ((a mod n)(b mod n)) mod n |
| Power | a^k mod n = (a mod n)^k mod n |
| Negative remainder | if a ≡ −1 (mod n) then a^k ≡ (−1)^k (mod n) |
Named theorems
| Fermat’s little theorem | a^(p−1) ≡ 1 (mod p), p prime, gcd(a,p)=1 |
|---|---|
| Euler’s theorem | a^φ(n) ≡ 1 (mod n), gcd(a,n)=1 |
| Euler’s totient | φ(n) = n·∏(1 − 1/p) over distinct primes p | n |
| Wilson’s theorem | (p − 1)! ≡ −1 (mod p), p prime |
| Corollary of Wilson | (p − 2)! ≡ 1 (mod p), p prime |