DSA GCD and the Euclidean Algorithm

The greatest common divisor is the largest whole number that divides two numbers exactly. The Euclidean algorithm finds it by replacing the larger number with a remainder.

One remainder step

Dividing 48 by 18 leaves a remainder of 12. The pair 48 and 18 becomes the pair 18 and 12.

a = 48
b = 18
print("48 divided by 18 leaves", a % b)
print("new pair:", b, a % b)

Steps shrink fast

Each step replaces the pair with a smaller pair. A counter records how many remainder steps run.

def gcd_steps(a, b):
    steps = 0
    while b:
        a, b = b, a % b
        steps += 1
    return a, steps

print("gcd of 24 and 9:", gcd_steps(24, 9))
print("gcd of 17 and 5:", gcd_steps(17, 5))

The lcm follows from the gcd

Dividing the product by the gcd gives the least common multiple. The check line multiplies the two answers back together.

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

a = 4
b = 6
g = gcd(a, b)
lcm = a // g * b
print("gcd:", g, "lcm:", lcm)
print("check gcd * lcm == a * b:", g * lcm == a * b)

Example

def gcd_counted(a, b):
    steps = 0
    while b:
        a, b = b, a % b
        steps += 1
    return a, steps

pairs = [(48, 18), (24, 9), (17, 5), (100, 75), (270, 192)]
for a, b in pairs:
    g, steps = gcd_counted(a, b)
    lcm = a // g * b
    print(a, "and", b, "| gcd", g, "| steps", steps, "| lcm", lcm, "| gcd*lcm == a*b:", g * lcm == a * b)

Key points

The greatest common divisor is the largest whole number dividing both numbers exactly.
A remainder is what is left after one number is divided by another.
Replacing a pair with the smaller number and the remainder keeps the same divisor.
The algorithm stops when the remainder reaches zero.
The last nonzero remainder step leaves the divisor standing as the answer.
The least common multiple of a pair equals their product divided by their divisor.

In this example, each pair runs through the remainder loop. The steps column counts the remainder operations for that pair. The divisor and the multiple are printed side by side. The check column confirms their product equals the pair's product. Even the largest pair finishes in four steps.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

def gcd_counted(a, b):
    steps = 0
    while b:
        a, b = b, a % b
        steps += 1
    return a, steps

pairs = [(48, 18), (24, 9), (17, 5), (100, 75), (270, 192)]
for a, b in pairs:
    g, steps = gcd_counted(a, b)
    lcm = a // g * b
    print(a, "and", b, "| gcd", g, "| steps", steps, "| lcm", lcm, "| gcd*lcm == a*b:", g * lcm == a * b)

Exercise

What is the greatest common divisor of 36 and 24?

6 8 12 4