Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Basic Euclidean Algorithm for GCD
2.1.
Naïve Approach:
3.
Euclid’s GCD Algorithm
3.1.
Binary Euclidean Algorithm
3.2.
Least Common Multiple:
4.
Extended Euclidean Algorithm
5.
How does Extended Algorithm Work?
6.
How is Extended Algorithm Useful?
7.
Some Problems Based on Euclid’s Algorithm:
8.
Frequently Asked Questions
8.1.
What is the Euclidean algorithm for GCD?
8.2.
What is the GCD of 75 and 45 using Euclid's algorithm?
8.3.
What is the GCD of P 144 and Q 55 using Euclid's algorithm?
8.4.
What is an example of the Euclidean algorithm for GCD?
8.5.
What is the Euclidean algorithm formula?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

GCD Euclidean Algorithm

Author Nikunj Goel
12 upvotes

Introduction

The Euclidean algorithm efficiently determines the greatest common divisor (GCD) of two positive integers. The GCD represents the largest number dividing both integers. This algorithm provides a straightforward method to calculate the GCD without factorization.

One of the earliest known numerical algorithms is that developed by Euclid (the father of geometry) in about 300 B.C. for computing the Greatest Common Divisor (GCD) of two positive integers. Euclid’s algorithm is an efficient method for calculating the GCD of two numbers, the largest number that divides both of them without any remainder.

Euclid gcd algorithm

Basic Euclidean Algorithm for GCD

  • The first way of doing it if we try to subtract the smallest number from the greatest, GCD remain the same and in this way, if we keep repeating this step we’ll finally get GCD.
     
  • But as above process subtraction could be time-consuming then instead of subtracting what we do, we divide the smaller number, the algorithm stops when we find remainder 0.
     

Let GCD(x,y) be the GCD of positive integers x and y. If x = y, then obviously GCD(x,y) = GCD(x,x) = x Euclid’s insight was to observe that, if x > y, then GCD(x,y) = GCD(x-y,y).

Actually, this is easy to prove. Suppose that d is a divisor of both x and y. Then there exist integers q 1  and q 2  such that x = q 1 d and y = q 2 d. But then x – y = q 1 d – q 2 d = (q 1  – q 2 )d. Therefore d is also a divisor of x-y.

Using similar reasoning, one can show the converse, i.e., that any divisor of x-y and y is also a divisor of x. Hence, the set of common divisors of x and y is the same as the set of common divisors of x-y and y. In particular, the largest values in these two sets are the same, which is to say that GCD(x,y) = GCD(x-y,y).

For improving the other we can also use, (For less no. of iterations) GCD(x,y) = GCD(x%y,y).

For illustration, the Euclidean algorithm can be used to find the greatest common
divisor of a = 1071 and b = 462.
1071 mod 462= 147
462 mod 147= 21
147 mod 21 =0

Since the last remainder is zero, the algorithm ends with 21 as the greatest
common divisor of 1071 and 462.

Implementation: If we compare this algorithm with a naïve approach (brute force), what we generally try to do. Let’s see How?

Naïve Approach:

// we'll start from 1 to smallest of the two number until we find a number that divides into both of them

int gcd(int a , int b)
{
    int ans = 1;
    for(int i;i<=min(a,b);i++){
        if(a%i == 0 && b%i == 0){
            ans=i;
        }
    }
}


But Euclid’s method is faster than this naive method, So lets we follow the Euclidean method to find out the GCD of 4598 and 3211. We represent the two number to the following way, Dividend should be the large number and Divisor is another number.we will repeat the process until the remainder is equal to zero.

Dividend = Divisor * Quotient + Remainder
4598 = 3211 * 1 + 1387
3211= 1387 * 2 + 437
1387 = 437 * 3 + 76
437 = 76 * 5 + 57
76= 57 * 1 + 19
57 = 19 * 3 + 0

At the point, the remainder is 0 and we get the GCD 19. Notice that every step dividend and devisor are exchanged and remainder and divisor exchanged. When we remainder is 0 that means the remaining divisor our GCD.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Euclid’s GCD Algorithm

int gcd (int a,int b){

   if (b ==0){

      return a;

   }

  else{

      return gcd(b, a%b);

      }

}

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

Binary Euclidean Algorithm

This algorithm finds the gcd using only subtraction, binary representation, shifting and parity testing. We will use a divide and conquer technique. The following function calculates gcd(a, b, res) = gcd(a, b, 1) · res. So to calculate gcd(a, b) it suffices to call gcd(a, b, 1) = gcd(a, b).

// Greatest commmon divisor using binary euclidean algorithm

def gcd(a, b, res):
   if a==b:
       return res*a;
   elif( a % 2 == 0 ) and ( b % 2 == 0):
       return gcd(a // 2, b // 2, 2*res)
   elif( a%2 == 0 ):
       return gcd(a // 2 , b, res)
   elif( b%2 == 0 ):
       return gcd(a , b // 2, res)
   elif a > b:
       return gcd(a - b, b , res)
   else:
       return gcd(a, b - a ,res)


This algorithm is superior to the previous one for very large integers when it cannot be assumed that all the arithmetic operations used here can be done in constant time. Due to the binary representation, operations are performed in linear time based on the length of the binary representation, even for very big integers. On the other hand, modulo applied in algorithm 10.2 has worse time complexity. It exceeds O(log n · log log n), where n = a + b. Thus the time complexity is O(log(a · b)) = O(log a + b) = O(log n). And for very large integers, O((log n)2), since each arithmetic operation can be done in O(log n) time.

Least Common Multiple:

The least common multiple (lcm) of two integers a and b is the smallest positive integer that is divisible by both a and b. There is the following relation:

lcm(a, b) = a·b/gcd(a,b)
Knowing how to compute the gcd(a, b) in O(log(a+b)) time, we can also compute the lcm(a, b) in the same time complexity.

Extended Euclidean Algorithm

Although the Euclid GCD algorithm works for almost all cases we can further improve it and this algorithm is known as the Extended Euclidean Algorithm. This algorithm not only finds the GCD of two numbers but also integer coefficients x and y such that:

ax + by = gcd(a, b)
Input: a = 35, b = 15
Output: gcd = 5
x = 1, y = -2
(Note that 351 + 15(-2) = 5)

Basically, what this algorithm does, it updates the results of gcd(a,b) using the results calculated by recursive call gcd(b%a, a). Let values of x and y obtained by the recursive calls are x1 and y1. Then x and y are as follows:
x = y1 – (b/a)*x1
y= x1

int gcd(int a, int b, int& x, int& y){

   if(b == 0){
       x=1;
       y=0;
       return a;
   }
   int x1, y1;
   int d = gcd(b, a % b, x1, y1);
   x = y1;
   y = x1 - y1 * (a / b);
   return d;
}


This implementation of the extended Euclidean algorithm produces correct results for negative integers as well.

Approach Time Complexity Space Complexity
Brute Force Solution  O(min(num1,num2)) O(1)
Euclidean Algorithm O(max(num1,num2)) O(1)
Optimized Euclidean Algorithm O(log(num1+num2)) O(log(num1+num2))

How does Extended Algorithm Work?

The Extended Euclidean Algorithm (EEA) is an extension of the Euclidean Algorithm used to find the greatest common divisor (GCD) of two numbers. It calculates not only the GCD but also the coefficients of Bézout's identity, which are integers that satisfy the equation ax + by = gcd(a, b).

Here's how the Extended Euclidean Algorithm works:

  1. It starts with the two numbers a and b for which we want to find the GCD and the Bézout coefficients.
  2. It performs the Euclidean Algorithm to find the GCD of a and b.
  3. While performing the Euclidean Algorithm, it simultaneously computes the Bézout coefficients by working backwards from the GCD.

How is Extended Algorithm Useful?

The Extended Euclidean Algorithm is useful in various cryptographic applications, particularly in modular arithmetic. Some key applications include:

  1. Modular Inverse: It can find the multiplicative modular inverse of a number a modulo m if a and m are coprime (i.e., gcd(a,m)=1).
  2. RSA Encryption: In the RSA encryption scheme, the Extended Euclidean Algorithm is used to calculate the private key from the public key components.
  3. Elliptic Curve Cryptography: It is used in elliptic curve cryptography algorithms to find the inverse of a number modulo a prime.

Some Problems Based on Euclid’s Algorithm:

  • Program to find the LCM of two numbers using GCD.
     
  • Program to find GCD of floating-point numbers.
     
  • Program to find the common ratio of three numbers.
     
  • Program to find GCD of an array of integers.
     
  • Program to find the sum of squares of N natural numbers.

Frequently Asked Questions

What is the Euclidean algorithm for GCD?

The Euclidean algorithm is a method for finding the greatest common divisor (GCD) of two integers. It is one of the oldest and most efficient algorithms for this purpose.

What is the GCD of 75 and 45 using Euclid's algorithm?

15 will be the GCD of 75 and 45 since its absolute value of the last non-zero remainder, which is 15.

What is the GCD of P 144 and Q 55 using Euclid's algorithm?

1 will be the GCD of P144 and Q55 since the remainder will be 1, and GCD is the absolute value of the last non-zero remainder.

What is an example of the Euclidean algorithm for GCD?

An example of the Euclidean algorithm for GCD: given a=48 and b=18, the algorithm iteratively computes remainders until b becomes zero, resulting in gcd(48,18)=6.

What is the Euclidean algorithm formula?

The Euclidean algorithm formula calculates the GCD of two numbers iteratively by repeatedly replacing the larger number with the remainder of the division of the two numbers until the remainder is zero.

Conclusion

In this article, we have discussed GCD Euclidean Algorithm. The Euclidean Algorithm for finding the Greatest Common Divisor (GCD) is a simple yet powerful method in number theory. Its iterative approach efficiently computes the GCD of two numbers by repeatedly replacing the larger number with the remainder of their division until reaching zero. 

Also Read - Kadanes AlgorithmIntroduction to Recursion

Refer to our Guided Path to upskill yourself in DSACompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio!

But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundles for placement preparations.

However, you may consider our paid courses to give your career an edge over others!

Live masterclass