GCD of two numbers in Python

The greatest common divisor (GCD) of two numbers is the largest number that divides both of them with no remainder. It is also called the HCF (highest common factor). The GCD of 48 and 18 is 6.

The program

def gcd(a, b):
    while b != 0:
        print(f"  {a} % {b} = {a % b}")
        a, b = b, a % b
    return abs(a)


print("GCD =", gcd(48, 18))

  48 % 18 = 12
  18 % 12 = 6
  12 % 6 = 0
GCD = 6

How it works

This is Euclid's algorithm, one of the oldest algorithms still in use. It uses one fact: the GCD of a and b is the same as the GCD of b and the remainder a % b.

• Each step replaces the pair (a, b) with (b, a % b). The numbers get smaller every time.
• When the remainder is 0, the other number (a) is the GCD.
• The print() inside the loop shows each step. Remove it when you use the function in a real program.
• abs(a) makes the result positive when one of the numbers is negative. If one number is 0, the GCD is the other number: gcd(0, 9) is 9.

Another way: math.gcd()

The math module has this function already. It also accepts more than two numbers:

import math

print(math.gcd(48, 18))
print(math.gcd(17, 5))
print(math.gcd(12, 18, 30))

6
1
6

When the GCD is 1, as for 17 and 5, the two numbers are called coprime: they have no common divisor except 1. To find the smallest common multiple instead, see the LCM program.