Python Algorithms

Euclidean GCD Algorithm in Python

Find the greatest common divisor in a few steps with Euclid's remainder trick, then compare with math.gcd.

  • Intermediate
  • 2 min read
  • 1 runnable example
What you'll learn
  • What the GCD is
  • Euclid's algorithm
  • math.gcd in the standard library
gcd(48, 18)
  1. 48 % 18 = 12→ (18, 12)
  2. 18 % 12 = 6→ (12, 6)
  3. 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.

From cutting squares to code
first, second▭ The rectangle: 48 × 18
first % second✂️ What is left after cutting squares of the smaller side
first, second = second, first % second🔁 Repeat with the leftover piece
while second:✅ Nothing left over: the side is the GCD, 6
gcd(a, b) = gcd(b, a % b) until the remainder is 0.
In one sentence

The 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

  1. first, second = second, first % second replaces the pair with the smaller number and the remainder.
  2. For 48 and 18 the pairs are (48, 18), (18, 12), (12, 6), (6, 0).
  3. while second: stops when the remainder becomes 0.
  4. 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.gcd is 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

Run code →
main.py
def gcd(first, second):
    while second:
        first, second = second, first % second
    return abs(first)

print(gcd(48, 18))
Get a Run button for this example

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.

  1. Try empty, single-item, and duplicate-value inputs.
  2. Print state after every step to observe the algorithm.
  3. Benchmark 100, 1,000, and 10,000 items, then compare another approach.
Run in the Python compiler →

Common mistakes

Using subtraction instead of the remainder

Repeated subtraction gives the same answer but is very slow for numbers far apart.

Problem
while first != second:
    if first > second:
        first -= second
    else:
        second -= first
Fix
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.

All challenges