Python Coding Exercise #25: Greatest Common Divisor

The question

Write a program that enters two numbers and finds the greatest common divisor of those two numbers. Use the gcd function from the math module.

For example:

Enter number 1: 12
Enter number 2: 18
The Greatest Common Divisor of 12 and 18 is 6

My Solution

from math import gcd

number1 = int(input("Enter number 1: "))
number2 = int(input("Enter number 2: "))
greatest_common_divisor = gcd(number1, number2)
print(f"The Greatest Common Divisor of {number1} and {number2} is {greatest_common_divisor}")

How My Solution Works

1. What is a greatest common divisor?

A divisor of a number is a number that divides it exactly, with no remainder. A common divisor of two numbers divides both of them. The greatest common divisor (GCD) is the biggest one.

For 12 and 18, list the divisors of each:

Number	Its divisors
12	1, 2, 3, 4, 6, 12
18	1, 2, 3, 6, 9, 18

The numbers that appear in both lists are 1, 2, 3 and 6, and the largest of those is 6. So the GCD of 12 and 18 is 6.

2. Import gcd from the math module

from math import gcd

The math module is a collection of ready-made mathematical tools. This line brings in just the gcd function, so you can call it by its plain name. (Importing from math was also used in Exercise #22 for pi.)

3. Read two whole numbers

int(input(...)) is used twice, so each answer is converted to an integer. The GCD is defined for whole numbers.

4. Call gcd()

gcd(number1, number2) returns the greatest common divisor of the two numbers, and the program stores it in greatest_common_divisor. Then an f-string builds a clear sentence that shows both input numbers and the answer.

Here are some more results:

Number 1	Number 2	GCD	Why
12	18	6	6 is the largest number dividing both
48	36	12	both are multiples of 12
100	75	25	both are multiples of 25
7	13	1	no common divisor except 1
9	9	9	a number’s biggest divisor is itself

When the GCD is 1, the two numbers have nothing in common except 1, and they are called coprime. Seven and thirteen are an example.

What gcd() does inside

You don’t need to know how gcd() works to use it. But it’s interesting, and it uses an idea you’ve already met: the remainder operator, %. A famous method, Euclid’s algorithm, finds the GCD by repeating one step: replace the pair (a, b) with (b, a % b) until the second number is 0. The first number is then the answer.

For 48 and 36:

Step	a	b	a % b
1	48	36	12
2	36	12	0
done	12	0

When b reaches 0, a is the GCD, which is 12. You could write it yourself with a while loop:

def my_gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

print(my_gcd(48, 36))   # 12

This isn’t needed for the exercise, since the exercise says to use gcd() from math, but it gives the same answer as math.gcd() for every pair of numbers from 0 to 79. The built-in function is the better choice in real programs: it’s already written, tested and fast.

Things to notice

Zero is handled sensibly. The GCD of 0 and 5 is 5, because 5 divides both 0 and 5. And gcd(0, 0) is 0.

More than two numbers. In Python 3.9 and later, gcd() accepts any number of values: gcd(12, 18, 24) gives 6.

There is a matching function for the opposite idea. math.lcm() finds the least common multiple, the smallest number that both values divide into. For example, lcm(4, 6) is 12.

What it’s used for. The GCD is the tool for simplifying fractions. To simplify 12/18, divide the top and bottom by their GCD, 6, to get 2/3:

from math import gcd

top, bottom = 12, 18
divisor = gcd(top, bottom)

print(f"{top // divisor}/{bottom // divisor}")   # 2/3

Key takeaways

• A divisor divides a number exactly. The greatest common divisor is the largest number that divides two numbers.
• from math import gcd brings the function in, and gcd(a, b) returns the answer.
• If the GCD is 1, the numbers are coprime.
• Euclid’s algorithm finds the GCD by repeatedly replacing (a, b) with (b, a % b).
• gcd() accepts more than two numbers in Python 3.9 and later, and math.lcm() finds the least common multiple.
• The GCD is useful for simplifying fractions.

✦ This is part of my Python Practice Exercise series, where I work through exercises while learning Python and explain each answer in plain language. ✦

---

Practice Source: This exercise is taken from Ultimate Python Programming: Learn Python with 650+ Programs, 900+ Practice Questions, and 5 Projects by Deepali Srivastava, published by BPB Publications. I’m working through the exercises as part of my Python learning journey and documenting my answers and explanations here.