3 ways to find the Greatest Common Divisor in Python

For today’s practice question, we’ll be writing a Python function that returns the greatest common divisor of a list of numbers.

Here are some topics we’ll cover in the post:

• How to find the greatest common divisor in Python
• How to use the built-in gcd() function
• What is the Euclidian Algorithm
• What is recursion
• How to use recursion to implement the Euclidian Algorithm

Key Concepts

Let’s start with a discussion of what the greatest common divisor is.

The greatest common divisor of a set of numbers – also known as the greatest common factor, highest common divisor or highest common factor – is the largest positive integer that divides all the numbers in the set without remainder.

For instance, the GCD of the set of numbers 12, 18 and 48 is 6. This is because all three numbers can be divided by 6 with no remainder.

Although all 3 numbers can also be divided by 2 without remainder, 2 is not the GREATEST common divisor (as 6 is greater than 2).

In addition, although 48 can be divided by 8 without remainder, the same does not apply to12 and 18. Hence, 8 is not a COMMON divisor.

6 is the only number that divides all 3 numbers without remainder and is the greatest among all the common divisors.

How to find GCD mathematically

There are many different methods to find GCD of a set of numbers. For today’s tutorial, we’ll look at two methods to find the GCD of a pair of integers.

Using “Brute Force”

The first method is to use “brute force”. This method involves repeatedly dividing both numbers by a selected number until we find a common divisor.

Suppose we want to find the GCD of 12 and 18. Since we know that the divisor of a number cannot be greater than the number itself, we’ll start with the number 12.

At each step, as long as a common divisor is not found, we reduce the number by 1 and keep trying until we find a common divisor that gives us no remainder for both numbers.

To find GCD for 12 and 18, here are the steps:

Divisor = 12:
12 divided by 12, remainder = 0
18 divided by 12, remainder = 6

Divisor = 11:
12 divided by 11, remainder = 1
18 divided by 11, remainder = 7

Divisor = 10:
12 divided by 10, remainder = 2
18 divided by 10, remainder = 8

Divisor = 9:
12 divided by 9, remainder = 3
18 divided by 9, remainder = 0

Divisor = 8:
12 divided by 8, remainder = 4
18 divided by 8, remainder = 2

Divisor = 7:
12 divided by 7, remainder = 5
18 divided by 7, remainder = 4

Divisor = 6:
12 divided by 6, remainder = 0
18 divided by 6, remainder = 0

When the divisor is 6, we see that the remainder is 0 for both the numbers 12 and 18. Hence, we conclude that 6 is the GCD.

Using the Euclidian Algorithm

As you can see from the previous section, finding the GCD of two numbers using brute force is quite intuitive. You just keep dividing until you find a number that works.

However, while the “brute force” technique is easy to implement, it is not efficient. One can imagine how tedious it will be when the two numbers are large. Instead of using brute force to find the GCD, a better technique is to use the Euclidian Algorithm.

This algorithm states that

gcd(a, 0) = a
gcd(a, b) = gcd(b, a%b)

a%b refers to the remainder when a is divided by b.

Let’s see how the algorithm works.

We’ll use the numbers 18 and 12 to demonstrate. Since both numbers are not zero, line 2 of the algorithm applies.

When a = 18, b = 12,

gcd(18, 12) 
= gcd(12, 18%12) 
= gcd(12, 6)

a and b become 12 and 6 respectively.

When a = 12, b = 6,

gcd(12, 6) 
= gcd(6, 12%6) 
= gcd(6, 0)

a and b become 6 and 0 respectively.

Now that the second number is zero, line 1 of the algorithm applies.

When a = 6, b = 0

gcd(6, 0) = 6

Hence, the GCD is 6.

How to find Greatest Common Divisor in Python

Now, let’s look at how we can use Python to find the greatest common divisor of two numbers. To do that, we can use one of the three techniques below:

• Using the built-in gcd() function
• Using a while loop
• Using recursion to implement the Euclidian Algorithm

Using the built-in gcd() function

The easiest is to use the built-in gcd() function. This function is available in the math module. Hence, we need to import the module first.

The gcd() function accepts two integers and returns the GCD of the two integers.

The syntax is as follows:

math.gcd(a, b)

Let’s look at some examples:

import math

print(math.gcd(18,12))
print(math.gcd(200,100))
print(math.gcd(2, 5))

If you run the code above, you’ll get the following output:

6
100
1

Using a while loop

Besides using the built-in gcd() function, we can use a while loop to find the greatest common divisor of two integers in Python. To do that, we use the while loop to implement the “brute force” technique mentioned above.

Here’s how to do it:

a = 18
b = 12

divisor = min(a, b)

while divisor > 0:
    if a%divisor == 0 and b%divisor == 0:
        print('The GCD is', divisor)
        break
    divisor -= 1

Here, we first initialise two variables a and b.

Next, we use the built-in min() function to look for the smaller of a and b and assign the result to a variable called divisor.

Next, we use a while loop to loop from divisor = 12 (i.e. min(a, b)) to divisor = 1 (i.e. divisor > 0).

Inside the loop, we use the % operator to find the remainder when a and b are divided by divisor.

If the remainder is zero for both a and b, we know that the current divisor is the GCD. The if condition on line 7 evaluates to True and the if block (on lines 8 and 9) is executed.

On line 8, we print the answer and on line 9, we use the break statement to break out of the while loop. This is because once we find the GCD, we do not want the while loop to continue trying other numbers.

On the other hand, if we get a non-zero remainder for either a or b, we know that the current divisor is not the GCD. Hence, we reduce divisor by 1 (on line 10) and run the while loop again.

We keep doing this until we find the GCD.

If you run the code above, you’ll get

The GCD is 6

as the output.

Using Recursion

The third method to find the greatest common divisor in Python is to use recursion to implement the Euclidian Algorithm.

This requires us to write a recursive function. A recursive function is a function that calls itself in its implementation. This is very useful for solving problems where the solution depends on solutions to smaller instances of the same problem.

Consider the case where we want to find the factorial of a number n.

The factorial, denoted as n!, is given by the formula:

n! = n(n-1)(n-2)....(3)(2)(1)

Suppose we want to calculate 5!, here’s how we do it:

5! = 5x4x3x2x1

From the formula above, notice that we can express 5! in terms of 4!? In other words, we can express 5! as the following:

5! 
= 5x(4x3x2x1)
= 5X(4!)

This means that we can solve a factorial problem by solving a smaller instance of the same problem. That is, we can solve 5! by solving 4!. In cases like these, recursion is a very useful technique.

Another example where recursion can be very useful is when we want to find the GCD of two numbers using the Euclidian Algorithm. Recall that the formula states:

gcd(a, 0) = a
gcd(a, b) = gcd(b, a%b)

From line 2, we see that we can solve gcd(a, b) by solving gcd(b, a%b). In other words, we can solve gcd(18, 12) by solving gcd(12, 6). This makes it the perfect candidate for using recursion.

To use recursion, we need a base case. The base case is the case that returns the answer and stops the recursion. With reference to the Euclidian Algorithm, the base case is the case on line 1 shown above.

To implement the Euclidian Algorithm using recursion, this is how we can do it:

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

result = eGCD(18, 12)
print('The GCD is', result)

On line 1, we define a function called eGCD() that has two parameters – a and b.

On line 7, we call this function using 18 and 12 as arguments. The diagram below shows what happens at each stage. The base case is on lines 2 and 3 in the code above and is indicated in orange in the diagram below.

Look through the code and diagram carefully to appreciate how recursion works. On line 7, the code calls eGCD(18, 12).

eGCD(18, 12) in turn calls eGCD(12, 6), which in turn calls eGCD(6, 0).

eGCD(6, 0) satisfies the base case on line 2 and 3. Hence, it returns 6 to its caller, which in turn returns 6 to its caller, which in turn returns 6 to result. Hence, when we print the value of result on line 8, we’ll get

The GCD is 6

as the output.

While recursion may seem complicated, it really just consists of two parts:

• a base case (lines 2 and 3), and
• a non-base case that calls the function recursively (lines 4 and 5)

That’s it. We are now ready to work on the practice question for today.

Practice Question

Today’s task is to write a function called myGCD() that accepts a Python list as argument and finds the GCD of all the numbers in the list.

Expected Results

To test your function, you can run the statements below:

print(myGCD([18, 12]))
print(myGCD([15, 30, 105]))
print(myGCD([1, 2, 3, 4, 5]))

you should get the following output:

6
15
1

Additional Notes

Getting GCD of more than two numbers

Suppose we want to get the GCD of [a, b, c, d, e], here’s how we can do it:

1. Find the GCD of a and b first. Suppose the answer is g1.
2. Next, get the GCD of g1 and c. Suppose the answer is g2.
3. Proceed on to get the GCD of g2 and d. Suppose the answer is g3.
4. Finally, get the GCD of g3 and e. That’ll be the GCD of all the five numbers.

Let’s look at an example.

Suppose we want to get the GCD of [12, 18, 20].

GCD of 12 and 18 = 6
GCD of 6 and 20 = 2

Therefore, GCD of 12, 18 and 20 is 2

Suggested Solution

The suggested solution for today’s practice question is as shown below:

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

def myGCD(myList):
    j = 0
    currentGCD = myList[0]
    while j < len(myList) - 1:
        currentGCD = eGCD(currentGCD, myList[j+1])
        j += 1
    return currentGCD