Do you think IIT Guwahati certified course can help you in your career?
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.
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)
You can also try this code with Online Python Compiler
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;
}
You can also try this code with Online C++ Compiler
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
Switch to top management roles with Online MBA
by Coding Ninjas
20 Jan, 2025
11:30 AM
Transition to SDE Career with Online PG Certification by IIT
by Coding Ninjas
20 Jan, 2025
03:30 PM
Transition to data career with Online PG Certification by IIT
by Coding Ninjas
21 Jan, 2025
01:30 PM
Switch to top management roles with Online MBA
by Coding Ninjas
20 Jan, 2025
11:30 AM
Transition to SDE Career with Online PG Certification by IIT
85+ registered 