Euclidean algorithm is the algorithm based on euclid’s division lemma. Now, what is lemma? A lemma is a proven statement used to help prove other theorems or results. As per euclid’s division lemma, if there are two positive numbers, let’s a and b, then there will be one more pair of two integers, let’s say p and q, hence, a = (b × p) + q, where 0 ≤ q < b. Euclid’s division algorithm is applied for problems where the highest common factor (HCF) is unknown, and only two non-negative numbers are given. After reading this guide on euclid’s division algorithm, you will understand everything about what is euclidean algorithm, and what is extended euclidean algorithm.
Table of Contents:
What is Euclidean Algorithm?
The Euclidean algorithm is an efficient method developed by ancient Greek mathematician Euclid to find the greatest common divisor (GCD) of two positive integers by repeatedly applying the division algorithm until the remainder is zero.
To understand this, you must be familiar with two things as prerequisites.
Prerequisites for Understanding the Euclidean Algorithm
Greatest Common Divisor (GCD)
The GCD of two or more integers is the largest integer that divides each of the integers such that its remainder is always zero.
Example:
GCD of 20, 50 = 10 (10 is the largest number that divides 20 and 50 with a remainder as 0)
GCD of 32, 140, 280 = 4 (4 is the largest number that divides 32, 140, and 280 with a remainder as 0)
“MOD” Operation
The mod operation results in a remainder when two positive integers are divided. We write it as follows-
A mod B = R
This means that dividing A by B gives you R as a remainder. This is not like a division operation, which provides you with a quotient.
Example:
12 mod 10 (Dividing 12 by 10 gives the remainder 2)
52 mod 2 (Dividing 52 by 2 gives the remainder 0)
With the above two terms understood, you are now ready to understand the Euclidean Algorithm.
How to Calculate GCD?
Let’s learn the calculation using Pseudo Code of the Euclidean Algorithm–
- Take two numbers, say a and b, where a > b.
- Divide a by b and find the remainder r.
- Formula: r = a mod b
- Replace a with b, and b with r.
- Repeat step 2 until b becomes 0.
- The last non-zero value of b is the GCD.
For Example:
Find the GCD of 48 and 18
48 ÷ 18 = 2 remainder 12 → 48 mod 18 = 12
Replace a=18, b=12
18 ÷ 12 = 1 remainder 6 → 18 mod 12 = 6
Replace a=12, b=6
12 ÷ 6 = 2 remainder 0 → 12 mod 6 = 0
Last non-zero remainder is 6 → GCD(48, 18) = 6
Euclidean Algorithm for Greatest Common Divisor (GCD)
To find GCD using Euclidean algorithm, you need 2 numbers. Let’s understand the GCD algorithm through its working.
Let’s say you want to calculate the GCD of 2240 and 615. Now, if we apply the Euclidean algorithm to these two numbers, we get:
To find the GCD using the recursive method in C programming, there are two ways:
1. Subtraction Method
int gcd(int a, int b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// base case
if (a == b)
return a;
// a is greater
if (a > b)
return gcd(a-b, b);
return gcd(a, b-a);
}
Now, this is the code to perform GCD using recursion. This is a subtraction-based method to find the GCD and will help you find the GCD of two numbers, a and b. But, this method is a bit slow if large numbers are used, as it runs many recursive calls.
Pro Tip: Try to make a recursion tree for small numbers (like the GCD of 16 and 10) to see how the function reduces the problem step by step.
2. Modulo Method
A more efficient version uses modulo instead of subtraction as it deduces the steps to a fewer number of steps.
int gcd(int a, int b) {
// Base case, if the second number becomes 0, the first number is the GCD
if (b == 0)
return a;
// Recursive step to call gcd with the smaller pair
return gcd(b, a % b);
}
Pro Tip: This same logic works across most programming languages (Java, Python, JS).
int gcd(int a,int b) {
int r;
while ((a % b) > 0) {
r = a % b;
a = b;
b = r;
}
return b;
}
static int gcd(int a, int b)
{
if(b == 0)
{
return a;
}
return gcd(b, a % b);
}
Java handles recursion effectively, but we recommend you to use BigInteger.gcd() in case of very large numbers. BigInteger.gcd() is a built-in function of Java’s standard library.
Pro Tip: Try to print the values of a and b inside the function of the above code to visualize how the recursion progresses.
def gcd(a, b):
# Base case, when the second number is 0
if b == 0:
return a
else:
# Recursive step using modulo
return gcd(b, a % b)
Python’s recursion is simple, but you can use the built-in function math.gcd(a,b) for instant results.
Pro Tip: Try printing each recursive call to understand how parameters swap and reduce in this program.
function gcd(a, b) {
var R;
// Keeps looping until the remainder becomes zero
while ((a % b) > 0) {
R = a % b; // Find remainder
a = b; // Assign b to a
b = R; // Assign remainder to b
}
return b; // Final non-zero b is the GCD
}
This is the iterative method to find GCD in JavaScript. It is memory-efficient and avoids recursion depth issues.
Pro Tip: Use console.log(a, b) inside the loop to trace the process interactively.
function gcd(a, b) {
// Base case
if (b == 0)
return a;
else
// Recursive call with reduced numbers
return gcd(b, a % b);
}
Recursion in JS works the same as in Python or Java, but keep in mind that very large numbers can hit recursion limits in browsers.
What is Extended Euclidean Algorithm?
The Extended Euclidean Algorithm is a method used to find not only the GCD (Greatest Common Divisor) of two numbers but also two numbers x and y such that:
a×x+b×y=gcd(a,b)
These numbers x and y are called Bézout coefficients. This is useful for solving modular inverse problems and is widely used in cryptographic systems like RSA.
C Code for Extended Euclidean Algorithm
#include <stdio.h>
// Structure to store the result of the Extended Euclidean Algorithm
struct IntellipaatTriplet {
int gcd; // Greatest Common Divisor
int x; // Coefficient for 'a'
int y; // Coefficient for 'b'
};
// Function implementing the Extended Euclidean Algorithm
struct IntellipaatTriplet intellipaatExtendedGCD(int a, int b) {
// Base Case: when b becomes 0
if (b == 0) {
struct IntellipaatTriplet result;
result.gcd = a; // gcd(a, 0) = a
result.x = 1; // Coefficient of a
result.y = 0; // Coefficient of b
return result;
}
// Recursive Call: compute result for smaller values
struct IntellipaatTriplet smallerResult = intellipaatExtendedGCD(b, a % b);
// Using Extended Euclidean relations:
// x = y1
// y = x1 - (a / b) * y1
struct IntellipaatTriplet currentResult;
currentResult.gcd = smallerResult.gcd;
currentResult.x = smallerResult.y;
currentResult.y = smallerResult.x - (a / b) * smallerResult.y;
return currentResult;
}
// Example to test the function
int main() {
int a = 35, b = 15;
struct IntellipaatTriplet answer = intellipaatExtendedGCD(a, b);
printf("GCD(%d, %d) = %d\n", a, b, answer.gcd);
printf("Coefficients: x = %d, y = %d\n", answer.x, answer.y);
printf("Verification: (%d * %d) + (%d * %d) = %d\n", a, answer.x, b, answer.y, answer.gcd);
return 0;
}
The Extended Euclidean Algorithm is very useful in:
- Solving Diophantine equations
- Cryptography (RSA algorithm)
- Modular inverses (finding the inverse of a number under mod m)
Conclusion
The Euclidean Algorithm is one of the oldest and most efficient methods to find the Greatest Common Divisor (GCD) of two numbers. By applying the division or modulo operation repeatedly, it quickly reduces large problems into smaller ones until the remainder becomes zero.
The algorithm’s strength lies in its simplicity and efficiency, working equally well across different programming languages, no matter you use recursion or iteration. While the subtraction method is simple to use and understand, the modulo method is faster and more practical for larger numbers.
Euclid’s timeless logic continues to power modern computation, forming the foundation for applications in cryptography, number theory, and algorithm design, proving that even 2,000-year-old mathematics still shapes today’s technology.
Euclidean Algorithm -FAQs
1. Give a Euclidean algorithm example?
Let’s find GCD(252, 105) using the Euclidean algorithm.
252 ÷ 105 = 2 remainder 42
105 ÷ 42 = 2 remainder 21
42 ÷ 21 = 2 remainder 0
The last non-zero remainder is 21, so GCD(252, 105) = 21
2. What is Euclidean algorithm formula?
The Euclidean algorithm formula is:
GCD(a, b) = GCD(b, a mod b)
Repeat the steps until the second number becomes 0. This formula is the foundation of both recursive and iterative implementations.
3. What is the Extended Euclidean Algorithm used for?
The Extended Euclidean Algorithm not only finds the GCD of two numbers but also returns integers x and y such that ax + by = gcd(a, b). This is useful for solving modular inverse problems and is widely used in cryptographic systems like RSA.
4. How is Euclidean algorithm used in cryptography?
In cryptography, especially in RSA, the Euclidean and Extended Euclidean Algorithms are used to compute modular inverses, generate private keys, and validate public key pairs. They ensure secure communication by solving equations within modular arithmetic.