Python Program to Find GCD of Two Numbers

Q: How do you find the GCD of two numbers in Python?

Call `math.gcd(a, b)`. To write it yourself, loop `a, b = b, a % b` while `b` is not 0 and return `a`.

Q: How do you find the LCM in Python?

Use `math.lcm(a, b)` in Python 3.9 and later, or compute `abs(a * b) // math.gcd(a, b)`.

By Yogesh Sharma (LinkedIn) · Every code example is run and checked on Python 3.13 (how we test) · Last updated 21 Oct 2026

Short answer

The GCD (greatest common divisor, also called HCF) of two numbers is the largest number that divides both exactly; in Python use math.gcd(a, b) or the Euclidean algorithm.

The GCD of 48 and 18 is 6, because 6 is the biggest number that goes into both. You use it to simplify fractions (48/18 becomes 8/3), to tile a rectangle with the largest possible square, and as a building block for the least common multiple.

The classic method is the Euclidean algorithm, over 2000 years old and still the standard approach. It is a nice example of a while loop that shrinks a problem until it disappears, and it also has a short recursive form.

Quick facts
Input	Two integers `a` and `b`
Output	Their greatest common divisor
Approach	Euclidean algorithm: replace `(a, b)` by `(b, a % b)` until `b` is 0
Time complexity	O(log(min(a, b)))

Approach (step by step)

If b is 0, the answer is a.
Otherwise replace a with b and b with the remainder a % b.
Repeat until b becomes 0; the current a is the GCD.

The idea is that any number dividing both a and b also divides the remainder a % b, so the GCD does not change while the numbers get smaller. For 48 and 18 the pairs are (48, 18), then (18, 12), then (12, 6), then (6, 0), so the GCD is 6.

How the code works

The loop while b: uses the fact that 0 is falsy (see truthy and falsy), so it runs until b is 0. The single line a, b = b, a % b does the swap and the remainder together. Because each remainder is smaller than the divisor, the loop always ends, and it takes very few steps even for huge numbers.

The edge case gcd(a, 0) returns a, and gcd(0, 0) returns 0, matching the built-in. Python's math.gcd always returns a non-negative result, so negative inputs are fine there.

Python

a, b = 48, 18
while b:
    print(a, b)
    a, b = b, a % b
print("GCD:", a)

Variations: math.gcd(), recursion and LCM

In real code use math.gcd(a, b). Since Python 3.9 it accepts any number of arguments, so math.gcd(12, 18, 30) works. The same release added math.lcm() for the least common multiple.

By hand the LCM follows from the GCD: lcm(a, b) = abs(a * b) // gcd(a, b). The slowest method, checking every number from min(a, b) downwards, is only useful to understand the definition.

Ways to compute a greatest common divisor
Method	Code idea	Speed
Built-in	`math.gcd(a, b)`	Fastest, written in C
Euclid with a loop	`while b: a, b = b, a % b`	Very fast
Euclid with recursion	`gcd(b, a % b)` until `b == 0`	Very fast, uses call stack
Brute force	Count down from `min(a, b)` until both divide	Slow for big numbers

Examples you can run

Press Run, then edit the code and run it again.

Euclidean algorithm as a function

The function returns the GCD after the loop. The results include a prime pair, a zero and a multiple.

Euclidean algorithm as a function

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

print(gcd(48, 18))
print(gcd(17, 5))
print(gcd(0, 9))
print(gcd(36, 12))

Expected output6
1
9
12

math.gcd() and math.lcm()

The standard library does the work for you, including more than two numbers.

math.gcd() and math.lcm()

import math

print(math.gcd(48, 18))
print(math.gcd(12, 18, 30))
print(math.lcm(4, 6))
print(math.gcd(-20, 8))

Expected output6
6
12
4

Simplify a fraction (interactive)

Read two numbers and divide both by their GCD to reduce the fraction.

Simplify a fraction (interactive)

import math

a = int(input("Numerator: "))
b = int(input("Denominator: "))
g = math.gcd(a, b)
print(f"GCD: {g}")
print(f"{a}/{b} = {a // g}/{b // g}")

Input (stdin) — one line per input() call

Expected outputNumerator: 48
Denominator: 18
GCD: 6
48/18 = 8/3

Common mistakes

Swapping with two separate assignments

✗ Wrong

a, b = 48, 18
while b:
    a = b
    b = a % b
print(a)

Prints 18, which is wrong: after `a = b`, the next line computes `a % b` with the new `a`, which is always 0.

✓ Right

a, b = 48, 18
while b:
    a, b = b, a % b
print(a)

Assign both variables at once with a, b = b, a % b.

Using / instead of // when simplifying

✗ Wrong

import math
a, b = 48, 18
g = math.gcd(a, b)
print(a / g, b / g)

Prints 8.0 3.0: true division gives floats.

✓ Right

import math
a, b = 48, 18
g = math.gcd(a, b)
print(a // g, b // g)

Use floor division // to keep whole numbers, see division vs floor division.

Python Program to Find GCD of Two Numbers: questions people ask

How do you find the GCD of two numbers in Python?

Call math.gcd(a, b). To write it yourself, loop a, b = b, a % b while b is not 0 and return a.

What is the difference between GCD and HCF?

There is none. GCD (greatest common divisor) and HCF (highest common factor) are two names for the same value.

How do you find the LCM in Python?

Use math.lcm(a, b) in Python 3.9 and later, or compute abs(a * b) // math.gcd(a, b).

Keep learning

Step-by-step lessons:
Python while Loops Python Recursion Python math and statistics

More in number programs:
Python Program to Check Even or Odd Number Python Program to Check Prime Number Python Program to Find Factorial of a Number Python Program to Print the Fibonacci Series Python Program to Check Armstrong Number Python Program to Check Leap Year Python Program to Find the Sum of Digits of a Number Python Program to Print a Multiplication Table See all →