gcd(48, 18)
48 = 2·18 + 12, 18 = 12 + 6, 12 = 2·6
6.
The Euclidean algorithm finds the greatest common divisor using : replace the pair by the smaller number and the remainder, and repeat until the remainder is 0. The last non-zero remainder is the gcd.
This page is easier if you are comfortable with:
For : , , , so the gcd is 21 (3 steps). For : , , , again 21. For : , , , giving 6. The remainders are those of division with remainder.
Why it works: any common divisor of and also divides , and conversely, so the pair and have the same common divisors. The algorithm is much faster than listing prime factors (prime factor form): the number of steps is at most about 5 times the number of digits, with the worst case for consecutive Fibonacci numbers (the gcd property of Fibonacci numbers, Binet's formula).
Together with the LCM (HCF and LCM), . Keeping track of the quotients gives integers with (Bézout's identity), which solves linear congruences (linear congruences) and underlies RSA (RSA).
The Euclidean algorithm finds the gcd by repeated division with remainder.
The remainders decrease until the last non-zero one, 21.
These examples are worked by hand, step by step, so you can compare your own working.
Find and the number of division steps.
Find .
Find .
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
48 = 2·18 + 12, 18 = 12 + 6, 12 = 2·6
6.
252 = 2·105 + 42, 105 = 2·42 + 21
21.
Euclid’s classic example
21.
12 × 18 / gcd
36.
gcd(a, b) = gcd(b, a mod b); repeat until the remainder is 0. The last non-zero remainder is the gcd, and lcm(a, b) = ab/gcd(a, b).
Find gcd(48, 18).
Find gcd(252, 105).
Find gcd(1071, 462).
Find lcm(12, 18) = 12 × 18/6.
always 1 ✗
continue to 0 ✓
Last non-zero remainder.
gcd = quotient ✗
remainders matter ✓
Not quotients.
ignoring gcd ✗
ab/gcd ✓
Divide.
larger first required ✗
works either way ✓
After one step.
Try each one on paper, then open the answer. Use the solver above to see the full working.
12
25
1
24
12
60
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
Repeated division until the remainder is 0.
6.
ab/gcd.
gcd(a, b) = gcd(b, a mod b).
Bézout’s identity.
linear congruences.
More in Discrete maths and number theory and the formula sheets.