gcd, lcm & the Euclidean algorithm
The Euclidean algorithm computes gcd(a,b) by repeatedly replacing (a,b) with (b, a mod b) until the remainder is 0 — the last non-zero remainder is the gcd. Running it backwards (the extended algorithm) expresses the gcd as ax + by, which is Bézout’s identity and the key to modular inverses. The lcm follows from gcd(a,b)·lcm(a,b) = ab.
✓ 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.
- Divide and replaceWrite a = bq + r, then repeat with (b, r). Keep every line — you need them for back-substitution.
- Stop at remainder zeroThe last non-zero remainder is the gcd.
- Back-substitute for BézoutStarting from the penultimate line, substitute each earlier remainder until only a and b remain.
- Get the lcm from the productlcm(a,b) = ab/gcd(a,b). Never compute the lcm by listing multiples.
Worked example
Find gcd(252, 198) and express it as 252x + 198y.
- 252 = 1(198) + 54; 198 = 3(54) + 36; 54 = 1(36) + 18; 36 = 2(18) + 0. So gcd = 18.
- Back-substitute: 18 = 54 − 1(36).
- Replace 36 = 198 − 3(54): 18 = 54 − (198 − 3·54) = 4(54) − 198.
- Replace 54 = 252 − 198: 18 = 4(252 − 198) − 198 = 4(252) − 5(198).
Answer. gcd(252,198) = 18 = 4(252) − 5(198), and lcm = 252·198/18 = 2772.
Where marks get dropped
These are the specific errors that cost credit on gcd, lcm & the euclidean algorithm questions — QED's rubric penalises each of them separately.
- Discarding the intermediate lines. Back-substitution needs every equation from the forward pass.
- Making an arithmetic slip in one division, which silently corrupts everything after it — check each line satisfies a = bq + r.
- Computing the lcm by listing multiples. For numbers in the hundreds that is impractical; use the product formula.
Practise this until it is automatic
Unlimited fresh questions
QED generates new gcd, lcm & the euclidean algorithm 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.
gcd, lcm & the Euclidean algorithm — frequently asked questions
Why does the algorithm work?
Because gcd(a,b) = gcd(b, a mod b): any common divisor of a and b divides the remainder, and conversely. Each step shrinks the numbers while preserving the gcd.
How fast is it?
O(log min(a,b)) divisions — the worst case is consecutive Fibonacci numbers, which is Lamé’s theorem.
What is Bézout’s identity used for?
Finding modular inverses: if gcd(a,n) = 1 then ax + ny = 1, so x is the inverse of a mod n. This is how RSA keys are generated.
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 gcd, lcm & the euclidean algorithm 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 →