Number System

Euclidean Algorithm

Pupils fit short measuring strips into longer ones and examine the leftover.

Euclidean Algorithm definition

The Euclidean algorithm finds the greatest common divisor of two integers by repeatedly replacing the larger number with a remainder.

In Spanish
algoritmo de Euclides
Topic
Number theory

Euclidean Algorithm in a picture

Euclidean Algorithm diagramRepeat division with the previous divisor and remainder.48 = 18 × 2 + 12First remainder: 1218 = 12 × 1 + 6Next remainder: 612 = 6 × 2 + 0The gcd is 6
Repeat division with the previous divisor and remainder.

How it works

For positive a and b, divide a by b and get remainder r. Then gcd(a, b) = gcd(b, r) because the two pairs have the same common divisors. Continue until a remainder is zero. The last nonzero remainder is the greatest common divisor. Use absolute values for negative inputs.

Worked examples

Find gcd(30, 18).

30 leaves 12, 18 leaves 6, and 12 leaves zero, so the gcd is 6.

Find gcd(25, 7).

25 mod 7 is 4, 7 mod 4 is 3, 4 mod 3 is 1, then zero. The gcd is 1.

Find gcd(12, 0).

12.

Common mistake

Stop at a zero remainder and use the last nonzero divisor. The final zero is not the gcd.

Quick check

What quantity does the algorithm find?

Show answer

The greatest common divisor.

What does each step replace?

Show answer

The pair becomes the previous divisor and the remainder.

What is gcd(10, 5)?

Show answer

5.

Sources

Flashcard

Euclidean Algorithm

Reveal the definition

The Euclidean algorithm finds the greatest common divisor of two integers by repeatedly replacing the larger number with a remainder.

Effortless Math. “Euclidean Algorithm.” Math Dictionary.