Euclidean GCD Algorithm in Python
Find the greatest common divisor in a few steps with Euclid's remainder trick, then compare with math.gcd.
- What the GCD is
- Euclid's algorithm
- math.gcd in the standard library
48 % 18 = 12→ (18, 12)18 % 12 = 6→ (12, 6)12 % 6 = 0→ gcd = 6
Replace the pair with (b, a % b)
The problem
Simplifying fractions, splitting things into equal groups and many puzzles need the largest number that divides two numbers. Trying every candidate is slow for big numbers; Euclid found a much faster way over 2,000 years ago.
Think of it like this
Euclid's method is like tiling a rectangle with the biggest possible square tiles. Cut the largest square you can from a 48 × 18 rectangle, then from what is left, and keep going. When the pieces fit exactly with nothing left over, the last square's side is the answer.
first, second▭ The rectangle: 48 × 18first % second✂️ What is left after cutting squares of the smaller sidefirst, second = second, first % second🔁 Repeat with the leftover piecewhile second:✅ Nothing left over: the side is the GCD, 6The greatest common divisor (GCD) of two integers is the largest positive integer that divides both; Euclid's algorithm finds it by replacing the pair (a, b) with (b, a % b) until b is 0.
Key points
first, second = second, first % secondreplaces the pair with the smaller number and the remainder.- For 48 and 18 the pairs are (48, 18), (18, 12), (12, 6), (6, 0).
while second:stops when the remainder becomes 0.return abs(first)gives a positive result even for negative inputs.
When should you use it?
- Simplifying fractions and ratios.
- Finding the least common multiple: a * b
//gcd(a, b). - Number puzzles, modular arithmetic and cryptography basics.
When not to use it
- Real code:
math.gcdis built in and handles any number of arguments in recent Python versions. - Finding all common divisors: the GCD gives only the largest one.
Example code
def gcd(first, second):
while second:
first, second = second, first % second
return abs(first)
print(gcd(48, 18))
Result of running the code
6
Code explanation
Each step replaces the pair with the smaller value and the remainder. When the remainder becomes zero, the remaining value is the GCD.
Change the values and run the program in the CodeUtility online Python compiler without installing Python locally.
Practice exercises
Modify the runnable example with the exercises below to build understanding beyond copying the result.
- Try empty, single-item, and duplicate-value inputs.
- Print state after every step to observe the algorithm.
- Benchmark 100, 1,000, and 10,000 items, then compare another approach.
Common mistakes
Using subtraction instead of the remainder
Repeated subtraction gives the same answer but is very slow for numbers far apart.
while first != second:
if first > second:
first -= second
else:
second -= first
while second:
first, second = second, first % second
Finished this lesson?
Mark it as learned to track your progress.
Practice with a challenge
Use what this lesson covers to solve a real problem. Each challenge runs in your browser with instant tests and an AI review.
- Greatest Common Divisor Find the largest number that divides both values. Easy
- Least Common Multiple Find the smallest positive number divisible by both values. Easy
- Exact Fraction Arithmetic Perform fraction operations and return a reduced fraction. Medium