Euler’s totient φ(n) & Euler’s theorem
φ(n) counts the integers in 1…n coprime to n. It is multiplicative for coprime arguments and satisfies φ(p^k) = p^k − p^(k−1), so the factorisation of n gives φ(n) immediately. Euler’s theorem then generalises Fermat: a^φ(n) ≡ 1 (mod n) whenever gcd(a,n) = 1, which is what lets exponents be reduced for composite moduli.
✓ 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.
- Factorise nEverything about φ comes from the prime factorisation.
- Apply φ(p^k) = p^k − p^(k−1)Equivalently p^(k−1)(p − 1). For a prime, φ(p) = p − 1.
- Multiply across coprime factorsφ(mn) = φ(m)φ(n) when gcd(m,n) = 1. This is why the formula works factor by factor.
- Reduce exponents mod φ(n)For gcd(a,n) = 1, a^e ≡ a^(e mod φ(n)) (mod n).
Worked example
Compute φ(36) and use it to find 5¹⁰⁰ mod 36.
- 36 = 2² × 3², so φ(36) = φ(4)φ(9) = (4−2)(9−3) = 2 × 6 = 12.
- gcd(5,36) = 1, so Euler applies: 5¹² ≡ 1 (mod 36).
- 100 = 12 × 8 + 4, so 5¹⁰⁰ ≡ 5⁴ (mod 36).
- 5⁴ = 625 = 36 × 17 + 13.
Answer. φ(36) = 12 and 5¹⁰⁰ ≡ 13 (mod 36).
Where marks get dropped
These are the specific errors that cost credit on euler’s totient φ(n) & euler’s theorem questions — QED's rubric penalises each of them separately.
- Using φ(mn) = φ(m)φ(n) for non-coprime m and n. φ(4)φ(2) = 2 × 1 = 2, but φ(8) = 4.
- Writing φ(p^k) = p^k − p. The correct subtraction is p^(k−1), the count of multiples of p up to p^k.
- Applying Euler’s theorem when gcd(a,n) > 1, where it simply fails.
Practise this until it is automatic
Unlimited fresh questions
QED generates new euler’s totient φ(n) & euler’s 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.
Euler’s totient φ(n) & Euler’s theorem — frequently asked questions
What is the product formula for φ?
φ(n) = n·Π(1 − 1/p) over the distinct primes p dividing n. For 36 that is 36 × (1/2) × (2/3) = 12.
Why does RSA need φ?
Because the decryption exponent d satisfies ed ≡ 1 (mod φ(n)), so encryption and decryption compose to the identity by Euler’s theorem.
Is φ(n) always even?
For n > 2, yes. Coprime residues pair up as a and n − a, and they are distinct for n > 2.
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 euler’s totient φ(n) & euler’s 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 →