Euclidean Algorithm Explained with Worked Examples

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.

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Euclidean algorithm means

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).

What is it used for?

The Euclidean algorithm finds the gcd by repeated division with remainder.

How to use euclidean algorithm

  1. Divide the larger by the smaller to get a remainder.
  2. Replace by .
  3. Repeat until the remainder is 0.
  4. The last non-zero remainder is the gcd.

Graph

Remainders in the Euclidean algorithm for 252 and 105gcd = 2100.511.522.533.544.55020406080100120Remainders in the Euclidean algorithm for 252 and 105stepvalueGraph with x from 0 to 5 and y from 0 to 120. Shows remainder (5); point gcd = 21 at (3, 21).

The remainders decrease until the last non-zero one, 21.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: gcd(252, 105)

Find and the number of division steps.

Worked example
Answer
21 in 3 steps21\ \text{in 3 steps}
  1. Steps

Example 2: gcd(1071, 462)

Find .

Worked example
Answer
2121
  1. Steps

Example 3: gcd(48, 18)

Find .

Worked example
Answer
66
  1. Steps

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

gcd(48, 18)

48 = 2·18 + 12, 18 = 12 + 6, 12 = 2·6

6.

gcd(252, 105)

252 = 2·105 + 42, 105 = 2·42 + 21

21.

gcd(1071, 462)

Euclid’s classic example

21.

lcm(12, 18)

12 × 18 / gcd

36.

Word problems

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).

First example

Find gcd(48, 18).

  1. 48 = 2·18 + 12
  2. 18 = 12 + 6
  3. 12 = 2·6
  4. Check: ✓6

Second example

Find gcd(252, 105).

  1. 252 mod 105 = 42
  2. 105 mod 42 = 21
  3. Check: ✓21

Larger Higher

Find gcd(1071, 462).

  1. 1071 mod 462 = 147
  2. 462 mod 147 = 21
  3. Check: ✓21

LCM Higher

Find lcm(12, 18) = 12 × 18/6.

  1. 216/6
  2. Check: ✓36

Common mistakes

Stopping at remainder 1 too early

always 1 ✗

continue to 0 ✓

Last non-zero remainder.

Using quotients

gcd = quotient ✗

remainders matter ✓

Not quotients.

lcm = ab

ignoring gcd ✗

ab/gcd ✓

Divide.

Order confusion

larger first required ✗

works either way ✓

After one step.

Exam tips

  1. gcd(a, b) = gcd(b, a mod b).
  2. Last non-zero remainder.
  3. lcm = ab/gcd.
  4. Fast even for big numbers.
  5. Back-substitute for Bézout.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. gcd(84, 36) Foundation

12

2. gcd(100, 75) Foundation

25

3. gcd(17, 5) Foundation

1

4. lcm(8, 12) Higher

24

5. gcd(144, 60) Higher

12

6. lcm(15, 20) Higher

60

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Euclidean algorithm
Repeated division.
GCD
Greatest common divisor.
Remainder
a mod b.
LCM
Lowest common multiple.
Coprime
gcd = 1.
Bézout
gcd as a combination.

Frequently asked questions

What is the Euclidean algorithm?

Repeated division until the remainder is 0.

What is gcd(48, 18)?

6.

How do I get the lcm?

ab/gcd.

Why does it work?

gcd(a, b) = gcd(b, a mod b).

Which page covers Bézout’s identity?

Bézout’s identity.

Which page covers linear congruences?

linear congruences.

More in Discrete maths and number theory and the formula sheets.