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.
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 getGCD.
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 positiveintegersx 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 thisalgorithmwith 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.
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.
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 caseswe 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:
It starts with the two numbers a and b for which we want to find the GCD and the Bézout coefficients.
It performs the Euclidean Algorithm to find the GCD of a and b.
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:
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).
RSA Encryption: In the RSA encryption scheme, the Extended Euclidean Algorithm is used to calculate the private key from the public key components.
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 anarray 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.
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 problems, interview experiences, and interview bundles for placement preparations.
However, you may consider our paid courses to give your career an edge over others!
Live masterclass
Master PowerBI using Netflix Data
by Ashwin Goyal, Product @ HRS Groups, Ex - Udaan, OYO
306+ registered