Modular inverses & fast exponentiation
a has an inverse modulo n exactly when gcd(a,n) = 1, and the extended Euclidean algorithm produces it: from ax + ny = 1 read off x. Fast exponentiation computes a^e mod n in about log₂ e squarings rather than e multiplications, by writing the exponent in binary — which is what makes RSA practical at all.
✓ 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 gcd(a,n) = 1No inverse exists otherwise, and saying so is the correct answer.
- Run the extended Euclidean algorithmSolve ax + ny = 1; then x mod n is the inverse.
- For exponentiation, write e in binarye = 13 is 1101₂, so a¹³ = a⁸ · a⁴ · a¹.
- Square and reduce at every stepCompute a², a⁴, a⁸ … each time reducing mod n so the numbers never grow.
Worked example
Compute 7¹³ mod 11 by repeated squaring.
- 13 in binary is 1101, so 7¹³ = 7⁸ · 7⁴ · 7¹.
- 7² = 49 ≡ 5 (mod 11). 7⁴ ≡ 5² = 25 ≡ 3 (mod 11). 7⁸ ≡ 3² = 9 (mod 11).
- Multiply the needed powers: 9 × 3 × 7.
- 9 × 3 = 27 ≡ 5; 5 × 7 = 35 ≡ 2 (mod 11).
Answer. 7¹³ ≡ 2 (mod 11). Fermat check: 7¹⁰ ≡ 1, so 7¹³ ≡ 7³ = 343 = 31·11 + 2 ✓.
Where marks get dropped
These are the specific errors that cost credit on modular inverses & fast exponentiation questions — QED's rubric penalises each of them separately.
- Trying to invert a number sharing a factor with the modulus. 4 has no inverse mod 6.
- Not reducing between squarings, which lets the intermediate numbers explode.
- Reading the binary expansion backwards, which multiplies the wrong set of powers.
Practise this until it is automatic
Unlimited fresh questions
QED generates new modular inverses & fast exponentiation 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.
Modular inverses & fast exponentiation — frequently asked questions
How do I find an inverse quickly for small moduli?
Trial multiplication: try a·1, a·2, … until you hit 1. For moduli above about 20 the extended Euclidean algorithm is faster and less error-prone.
Why is repeated squaring so much faster?
It uses about 2log₂e multiplications instead of e. For a 2048-bit RSA exponent that is roughly 3000 operations rather than an astronomically large number.
How many elements are invertible mod n?
Exactly φ(n) — the integers coprime to n. They form a group under multiplication, which is what Euler’s theorem describes.
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 modular inverses & fast exponentiation 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 →