Greatest Common Divisor (GCD) in Python

The greatest common divisor in Python is one function call: math.gcd(a, b) returns the largest whole number that divides both values evenly. Since Python 3.9 it accepts any number of arguments:

import math
math.gcd(84, 126)        # 42
math.gcd(84, 126, 210)   # 42

These results come from real runs of Python 3.12.5, so you can trust the edge cases like zero and negative numbers.

I’ll cover math.gcd() and its quirks, Euclid’s algorithm step by step, practical uses like simplifying fractions and finding the LCM, NumPy’s version, and a quick speed check.

How to find the greatest common divisor with math.gcd()

math.gcd() works with integers of any size. The result is never negative, gcd(0, n) is n, and a result of 1 means the numbers are coprime:

import math

print(math.gcd(84, 126))            # 42
print(math.gcd(84, 126, 210))       # several numbers at once (Python 3.9+)
print(math.gcd(-12, 18))            # always non-negative: 6
print(math.gcd(0, 25), math.gcd(0, 0))
print(math.gcd(17, 31))             # 1 -> the numbers are coprime

try:
    math.gcd(12.0, 18)
except TypeError as err:
    print("TypeError:", err)

Output:

42
42
6
25 0
1
TypeError: 'float' object cannot be interpreted as an integer

Euclid’s algorithm: how GCD works

Euclid’s algorithm is over 2,000 years old and still what computers use. Replace the pair (a, b) with (b, a % b) until the remainder is 0; the last non-zero value is the GCD:

def gcd(a, b, show=False):
    a, b = abs(a), abs(b)
    while b:
        if show:
            print(f"  gcd({a}, {b}) -> {a} % {b} = {a % b}")
        a, b = b, a % b
    return a

print("result:", gcd(1071, 462, show=True))

def gcd_recursive(a, b):
    return abs(a) if b == 0 else gcd_recursive(b, a % b)

print("recursive:", gcd_recursive(1071, 462))

Output:

  gcd(1071, 462) -> 1071 % 462 = 147
  gcd(462, 147) -> 462 % 147 = 21
  gcd(147, 21) -> 147 % 21 = 0
result: 21
recursive: 21

The % operator gives the remainder. If you’d like a refresher, what the percent sign means in Python explains it. The loop is a classic while loop that runs until b hits 0.

What is GCD used for in Python?

GCD shows up whenever you need to split things evenly, simplify ratios, or line up repeating cycles. Here are four everyday uses, including the least common multiple:

import math
from fractions import Fraction
from functools import reduce

# 1. biggest equal gift boxes: 84 cupcakes and 126 cookies, nothing left over
boxes = math.gcd(84, 126)
print(f"{boxes} boxes, each with {84 // boxes} cupcakes and {126 // boxes} cookies")

# 2. simplify a fraction by hand, or let Fraction do it
num, den = 1890, 2520
g = math.gcd(num, den)
print(f"{num}/{den} = {num // g}/{den // g}", "|", Fraction(num, den))

# 3. gcd of a whole list
widths = [48, 72, 120, 96]
print("largest tile that fits every width:", reduce(math.gcd, widths), "| same:", math.gcd(*widths))

# 4. least common multiple
print("lcm(6, 8, 12) =", math.lcm(6, 8, 12), "| via gcd:", 6 * 8 // math.gcd(6, 8))

Output:

42 boxes, each with 2 cupcakes and 3 cookies
1890/2520 = 3/4 | 3/4
largest tile that fits every width: 24 | same: 24
lcm(6, 8, 12) = 24 | via gcd: 24

reduce() applies gcd across a list pair by pair, though math.gcd(*widths) is simpler now. More in the reduce() function in Python.

GCD of arrays with NumPy

For many pairs at once, np.gcd() and np.lcm() work element by element, and np.gcd.reduce() collapses a whole array:

import numpy as np

a = np.array([84, 48, 100, 17])
b = np.array([126, 180, 75, 51])
print("pairwise gcd:", np.gcd(a, b))
print("pairwise lcm:", np.lcm(a, b))
print("gcd of all:  ", np.gcd.reduce(np.array([48, 72, 120, 96])))

Output:

pairwise gcd: [42 12 25 17]
pairwise lcm: [252 720 300  51]
gcd of all:   24

Is math.gcd faster than writing your own?

Yes. math.gcd() is implemented in C, so it beats a Python loop even on very large integers. Your own version is still great for learning or tracing steps:

import math
import timeit

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

big_a, big_b = 2**200 + 12345, 3**120 + 6789
print(gcd_loop(big_a, big_b) == math.gcd(big_a, big_b))
t_loop = timeit.timeit(lambda: gcd_loop(big_a, big_b), number=20_000)
t_math = timeit.timeit(lambda: math.gcd(big_a, big_b), number=20_000)
print(f"Python loop: {t_loop:.3f} s | math.gcd: {t_math:.3f} s")

Output:

True
Python loop: 0.145 s | math.gcd: 0.015 s

Both give the same answer; the built-in is just several times faster. I’d use it in real code every time.

GCD tools in Python

Tool	What it does
math.gcd(a, b, ...)	Greatest common divisor of integers
math.lcm(a, b, ...)	Least common multiple (Python 3.9+)
Fraction(n, d)	A fraction reduced to lowest terms
np.gcd(a, b)	Element-wise GCD of arrays
np.gcd.reduce(arr)	GCD of every value in an array

More number programs you can try:

• Factors of a number in Python
• Check prime numbers in Python
• Factorial of a number in Python
• Order of operations in Python

Frequently asked questions