Number Theory - Greatest Common Divisor (G.C.D) Algorithms

Hope, you are enjoying this series of articles on number theory and learning from it efficiently.

So, we are back with our brand-new article on GCD algorithms, be relaxed and keep reading, we will make sure that after reading this article you will understand what is GCD and will be able to code an efficient solution for finding GCD of two numbers 😊

2. Naïve Approach – Brute Force:

As you may have predicted this is a brute force approach so we will be checking for every possible case.

Basically, we will be doing same process as explained above i.e. we will start checking from minimum of two numbers and iterate till 1, and in each iteration we will be checking that if given two numbers are divisible by it or not, if it is divisible we have got our GCD (we will stop iteration and return it) else we will continue the same process.

Note: The GCD of two numbers (let’s say a and b) lie in between minimum(a,b) to 1.
E.g. GCD(12,16) will lie in between minimum(12,16) = 12 and 1 i.e. GCD(12,16) = 4.

Below is the implementation of naïve approach:

Time Complexity = O( min(a,b) )

2. Euclid’s Algorithm – O( log(min(a,b)) ):

As learned from previous article if you want to optimize any approach try to figure out some observations from it.

Observation: The Euclidean algorithm is based on the following key observation: if d divides a and d divides b, then d also divides
a − b.

Note: Same goes for Addition also i.e if d divides a and d divides b, then d also divides a + b.

E.g. 4 divides 12 and 4 divides 20,and hence 4 also divides (20 - 12) i.e. 8.

This means that the GCD of a and b is the same as the GCD of a−b and b, which is progress since this makes the numbers smaller.

As a result, we can repeat this process to form an optimized algorithm:

Determine the greatest common factor of 84 and 132.

We follow our algorithm:

1. a is 84 and b is 132. Since b > a, we replace b with b – a = 132 – 84 = 48.

2. a is 84 and b is 48. Since a > b, we replace a with a – b = 84 – 48 = 36

3. a is 36 and b is 48. Since b > a, we replace b with b – a = 12

4. a is 36 and b is 12. Since a > b, we replace a with a – b = 24

5. a is 24 and b is 12. Since a > b, we replace a with a – b = 12

6. a is 12 and b is 12. Since a = b, the GCD is 12.

Below is the implementation of optimized approach:

Time Complexity: O( left to you, try it out… it would be fun !! )

In this particular approach as discussed above we can furthermore optimize it with using modular operation rather than subtracting two numbers.

Now instead of subtraction, if we divide smaller number, the algorithm stops when we find remainder 0.

formally defined as below:

Hence, finally we got b = 0 therefore our GCD came out to be 4.

Below is the implementation of above approach:

Time Complexity: O( log( min(a,b) ) )

There is one more algorithm which is to be considered while learning GCD named Extended Euclid’s Algorithm.
It is basically a extension of above algorithm as it wont optimize Euclid Algorithm more but it is useful for calculating Modulo Multiplicative Inverse.

But we will not be learning Extended Euclid’s Algorithm in this article as it has some concepts of modulo multiplicative inverse so we will first get ourselves familiar with modular arithmetic and then we will understand this algorithm as we don’t believe in giving half knowledge to our readers 😊

It is always better to solve a question after you learn a new concept as it helps in making concrete concepts.

So, below are problems which are handpicked by Programmers Army to make your concept more solid which you learned.

We highly recommend to solve above problems if you got stuck read editorials for guidance.

So that’s it for this article we will be coming up with our next article on further topics of number theory very soon till then keep learning, keep coding, keep reading and keep improving !!

Happy Coding 😊

By Programmers Army