Euclidean Algorithm definition
The Euclidean algorithm finds the greatest common divisor of two integers by repeatedly replacing the larger number with a remainder.
Euclidean Algorithm in a picture
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.
