Fermat’s little theorem
Fermat’s little theorem says that for prime p and a not divisible by p, a^(p−1) ≡ 1 (mod p). The immediate payoff is exponent reduction: any exponent can be reduced modulo p−1, turning 3¹⁰⁰ mod 7 into a one-line computation. The coprimality condition is essential — the theorem says nothing when p ∣ a.
✓ Unlimited questions · marked criterion by criterion · no card needed
Method: how to approach it
The order below is what examiners expect to see, and each step carries its own marks.
- Check p is prime and p ∤ aBoth conditions are required. For composite moduli use Euler’s theorem instead.
- Reduce the exponent mod p − 1Write the exponent as q(p−1) + r; then a^exponent ≡ a^r (mod p).
- Compute the small remaining powerReduce the base first, then compute a^r by repeated squaring if needed.
- Use the alternative form when p ∣ a is possiblea^p ≡ a (mod p) holds for EVERY a, including multiples of p.
Worked example
Compute 3¹⁰⁰ mod 7.
- 7 is prime and 7 ∤ 3, so Fermat applies with p − 1 = 6.
- 100 = 6 × 16 + 4, so 3¹⁰⁰ = (3⁶)¹⁶ · 3⁴ ≡ 1¹⁶ · 3⁴ (mod 7).
- 3⁴ = 81.
- 81 = 7 × 11 + 4.
Answer. 3¹⁰⁰ ≡ 4 (mod 7).
Where marks get dropped
These are the specific errors that cost credit on fermat’s little theorem questions — QED's rubric penalises each of them separately.
- Reducing the exponent mod p instead of mod p − 1. The exponent lives in a cycle of length dividing p − 1.
- Applying the theorem with a composite modulus. 2⁸ ≢ 1 (mod 9) — that case needs Euler’s theorem with φ(9) = 6.
- Forgetting the p ∤ a condition for the a^(p−1) form.
Practise this until it is automatic
Unlimited fresh questions
QED generates new fermat’s little theorem problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.
Marked like an examiner
Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.
Answer in real notation
A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.
Saved to your library
Every question you generate is kept and re-takeable as a timed exam, and your Number Theory mastery is tracked so you know when this is exam-ready.
Fermat’s little theorem — frequently asked questions
What is a Fermat primality test?
If a^(n−1) ≢ 1 (mod n) for some a coprime to n, then n is definitely composite. Passing the test is not a proof of primality.
What are Carmichael numbers?
Composites like 561 that pass the Fermat test for every coprime base, so the test can never expose them. They are why Miller–Rabin is used instead.
How does it relate to Euler’s theorem?
Fermat is the special case n = p, where φ(p) = p − 1. Euler’s theorem a^φ(n) ≡ 1 (mod n) covers composite moduli.
The rest of Number Theory
Divisibility, primes, gcd, modular arithmetic. Each subtopic below has its own method, worked example and mark-losing traps.
- 1Divisibility & the division algorithm
- 2Primes & unique factorisation
- 3gcd, lcm & the Euclidean algorithm
- 4Modular arithmetic & congruences
- 5Solving linear congruences
- 6Fermat’s little theorem
- 7The Chinese remainder theorem
- 8Modular inverses & fast exponentiation
- 9Euler’s totient φ(n) & Euler’s theorem
- 10Base-b representations & digit arguments
- 11RSA & modular exponentiation in cryptography
- 12Wilson’s theorem & primality testing
- 13Linear Diophantine equations ax + by = c
Ready to make fermat’s little theorem exam-proof?
Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.
Start practising free →