Python Program to Find the GCD of Two Numbers

The Greatest Common Divisor (GCD) of two integers is the largest positive integer that divides both numbers evenly. Python gives you several ways to compute it, from writing the algorithm yourself to letting the standard library do the work in a single line.

Finding the GCD is a classic programming exercise that shows up in school curricula, coding interviews, and real-world tasks like simplifying fractions or determining step sizes in loops. This article walks through three working approaches, each building on the last in terms of elegance and efficiency.

What Is the GCD?

Before writing any code, it helps to make sure the concept is clear. The GCD of two numbers is the largest number that divides both of them with no remainder. For example:

• GCD(12, 18) = 6, because 6 divides both 12 and 18, and no number larger than 6 does.
• GCD(7, 13) = 1, because 7 and 13 are both prime, so the only common divisor is 1.
• GCD(100, 75) = 25, because 25 divides both 100 and 75.

When two numbers share a GCD of 1, they are called coprime (or relatively prime). The GCD is foundational in number theory and has practical uses anywhere ratios or divisibility matter.

Method 1: Using a Loop

The most straightforward approach is to check every integer from 1 up to the smaller of the two numbers and keep track of the largest one that divides both evenly. This works correctly, though it is not the fastest option for large numbers.

def gcd_loop(a, b):
    a = abs(a)
    b = abs(b)
    gcd = 1
    for i in range(1, min(a, b) + 1):
        if a % i == 0 and b % i == 0:
            gcd = i
    return gcd

# Example usage
num1 = 48
num2 = 18
print(f"GCD of {num1} and {num2} is: {gcd_loop(num1, num2)}")

Output:

GCD of 48 and 18 is: 6

The loop iterates through every candidate divisor, updating gcd each time it finds one that works. By the end of the loop, gcd holds the largest valid divisor found. The abs() calls ensure the function handles negative inputs gracefully.

Method 2: Using Recursion (Euclidean Algorithm)

The Euclidean algorithm is one of the oldest known algorithms, dating back over two thousand years. It is based on a simple mathematical property: the GCD of two numbers does not change if the larger number is replaced by its remainder when divided by the smaller number. That process repeats until one of the numbers reaches zero, at which point the other number is the GCD.

"The method of exhaustion and the Euclidean algorithm together represent the first systematic approaches to computation in mathematical history." — Donald Knuth, The Art of Computer Programming

In Python, this translates cleanly into a recursive function:

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

# Example usage
num1 = 48
num2 = 18
print(f"GCD of {num1} and {num2} is: {gcd_recursive(num1, num2)}")

Output:

GCD of 48 and 18 is: 6

Here is what happens step by step for gcd_recursive(48, 18):

1. 48 % 18 = 12, so the function calls gcd_recursive(18, 12)
2. 18 % 12 = 6, so the function calls gcd_recursive(12, 6)
3. 12 % 6 = 0, so the function calls gcd_recursive(6, 0)
4. b is 0, so the function returns 6

The iterative Euclidean version looks like this:

def gcd_euclidean(a, b):
    a = abs(a)
    b = abs(b)
    while b:
        a, b = b, a % b
    return a

# Example usage
print(f"GCD of 48 and 18 is: {gcd_euclidean(48, 18)}")
print(f"GCD of 100 and 75 is: {gcd_euclidean(100, 75)}")
print(f"GCD of 7 and 13 is:   {gcd_euclidean(7, 13)}")

Output:

GCD of 48 and 18 is: 6
GCD of 100 and 75 is: 25
GCD of 7 and 13 is:   1

Method 3: Using math.gcd()

Python's standard library includes a built-in math.gcd() function. For production code, this is the recommended choice. It is implemented in C under the hood, handles edge cases, and requires no additional code on your part.

import math

num1 = 48
num2 = 18
result = math.gcd(num1, num2)
print(f"GCD of {num1} and {num2} is: {result}")

Output:

GCD of 48 and 18 is: 6

Starting in Python 3.9, math.gcd() was extended to accept more than two arguments, so you can find the GCD of an entire list of numbers in one call:

import math

numbers = [48, 18, 36, 6]
result = math.gcd(*numbers)
print(f"GCD of {numbers} is: {result}")

Output:

GCD of [48, 18, 36, 6] is: 6

Which Method Should You Use?

Each approach has its place depending on context:

• Loop method — Good for learning. It makes the definition of GCD visible in the code itself. Do not use it for performance-sensitive work.
• Recursive Euclidean algorithm — A valuable exercise for understanding recursion and classical algorithms. The iterative version is preferable in practice to avoid hitting Python's default recursion depth limit of 1000.
• math.gcd() — The right choice for any real project. It is fast, tested, and already handles edge cases like negative inputs and zero.

Key Takeaways

1. GCD defined: The Greatest Common Divisor is the largest integer that divides two numbers with no remainder. It is always positive and at least 1.
2. Three approaches: A brute-force loop is easy to read but slow; the Euclidean algorithm is efficient and worth understanding; math.gcd() is the standard library solution that you should use in real code.
3. Edge cases matter: Always account for negative inputs (use abs()) and zero. Python's math.gcd() handles both for you automatically in Python 3.5+.
4. Python 3.9+ extras: math.gcd() and math.lcm() both accept multiple arguments in Python 3.9 and later, making it easy to work with lists of numbers.

Understanding how to compute the GCD builds intuition for number theory, recursion, and algorithmic thinking. Whether you are simplifying fractions, scheduling repeating events, or working through a coding challenge, this is a tool worth having in your Python toolkit.