Lesson 2 of 8 · Number Theory
GCD, LCM & the Euclidean Algorithm
Factoring two numbers to find their gcd works, but it's slow for large numbers. The Euclidean algorithm finds the gcd of any two integers in a handful of steps, no matter how large — and it's the foundation for Bezout's identity, which shows up again later in this domain.
Mark your status for this lesson:
Learning objectives
- Compute gcd(a, b) efficiently using the Euclidean algorithm, for numbers too large to factor comfortably by hand.
- Use the relationship gcd(a,b) × lcm(a,b) = a × b to find one quantity from the other.
- Find the gcd or lcm of three or more numbers by combining results pairwise.
- Recognize Bezout's identity — gcd(a,b) as a linear combination of a and b — and use it in simple modular-inverse problems.
The core idea
The Euclidean algorithm rests on one fact: gcd(a, b) = gcd(b, a mod b). Repeatedly replacing the pair with (smaller number, remainder) shrinks the numbers fast — usually to 0 within a handful of steps — and the last nonzero remainder is the gcd. This is dramatically faster than factoring both numbers first, especially once the numbers get into the thousands.
The Euclidean algorithm
gcd(a, b) = gcd(b, a mod b)
Repeat until the second number is 0 — the first number at that point is the gcd.
GCD-LCM relationship
gcd(a,b) × lcm(a,b) = a × b
Once you have the gcd (fast, via the Euclidean algorithm), the lcm follows in one division — no need to search for common multiples directly.
Bezout's identity
gcd(a,b) = xa + yb for some integers x, y
The gcd of two integers can always be written as an integer combination of them. Working backwards through the Euclidean algorithm's steps finds one such x, y pair explicitly.
Worked example 1 — The Euclidean algorithm
Problem
Find gcd(252, 105).
Key insight
Repeatedly replace the pair with (smaller number, remainder) until the remainder hits 0.
Solution
252 = 2(105) + 42, 105 = 2(42) + 21, 42 = 2(21) + 0. The last nonzero remainder is 21.
Takeaway
Three steps found the gcd of two three-digit numbers — factoring both first would have taken much longer.
Worked example 2 — LCM from GCD
Problem
Find lcm(252, 105), reusing the previous example's result.
Key insight
gcd(a,b) × lcm(a,b) = a × b — solve directly for the lcm.
Solution
lcm(252,105) = 252 × 105 / 21 = 1260.
Takeaway
Once you have the gcd, the lcm is a single division away — never search for common multiples by listing them.
Worked example 3 — Bezout's identity
Problem
Express gcd(48, 18) = 6 as an integer combination of 48 and 18.
Key insight
Run the Euclidean algorithm forward, then substitute back from the last step to the first.
Solution
Forward: 48=2(18)+12, 18=1(12)+6. Backward: 6 = 18 − 1(12), and substituting 12 = 48 − 2(18): 6 = 3(18) − 48. So x = −1, y = 3 in gcd = x(48) + y(18).
Takeaway
This "run forward, substitute backward" pattern is the extended Euclidean algorithm — it always finds some valid (x, y) pair, though not the only one.
Worked example 4 — LCM word problem
Problem
Two runners start together on a circular track. One completes a lap every 18 seconds, the other every 24 seconds. After how many seconds are they next together at the starting point?
Key insight
Both runners are at the start exactly when elapsed time is a multiple of their own lap time — so the answer is the lcm of the two lap times.
Solution
lcm(18,24) = 72 seconds.
Takeaway
"When do repeating events next coincide" is almost always an lcm question in disguise.
Strategy notes
Default to the Euclidean algorithm for large numbers
Once numbers get past two or three digits, factoring both to find a gcd is slower and more error-prone than a few rounds of the Euclidean algorithm — use it by default, not just when factoring looks hard.
"When do repeating events coincide" is an lcm question
Any problem describing multiple periodic events (bells, blinking lights, laps) and asking when they next align together is asking for the lcm of the periods.
Common mistakes
Confusing which number to take the remainder of
gcd(a,b) = gcd(b, a mod b) — the smaller number carries forward unchanged, and the remainder replaces the larger number. Swapping this produces nonsense results.
Finding the lcm of three numbers by pairing the wrong two first
lcm(a,b,c) can be found as lcm(lcm(a,b), c) — but you must actually carry the intermediate lcm forward, not go back to the original a or b at the second step.
Assuming Bezout's coefficients are unique
Many different (x, y) pairs satisfy gcd(a,b) = xa + yb — the extended Euclidean algorithm finds one specific solution, not the only one.
Practice
20 questions across four difficulty tiers, each with a single numeric answer. Up to three tries per question before the solution is shown.