Introduction:
The Euclidean Algorithm is a number theory cornerstone with applications far beyond mathematics. Originally devised by the ancient Greek mathematician Euclid, this algorithm provides an efficient way to find the greatest common divisor (GCD) of two integers—a problem that arises in cryptography to computer science, engineering, and even music theory. By breaking down large numbers through a systematic process of repeated division, the Euclidean Algorithm stands out as both powerful and accessible, enabling us to simplify complex calculations and understand relationships between numbers. In this blog, we'll explore how the Euclidean Algorithm works.
Read More - Time Complexity of Sorting Algorithms, Prims and Kruskal Algorithm and Euclid GCD Algorithm
Basic Euclidean Algorithm for GCD
The Basic Euclidean Algorithm is a simple yet powerful method to find the Greatest Common Divisor (GCD) of two numbers. It works on the principle that the GCD of two numbers also divides their difference.
Here's how it works:
- Take two numbers a and b
- Divide a by b to get quotient q and remainder r
- If r = 0, b is the GCD
- If r ≠ 0, set a = b and b = r, then repeat from step 2
For example, let's find GCD(48, 18):
48 = 2 × 18 + 12
18 = 1 × 12 + 6
12 = 2 × 6 + 0Therefore, GCD(48, 18) = 6
Extended Euclidean Algorithm
The Extended Euclidean Algorithm is an extension of the basic algorithm that, in addition to the GCD, also finds the coefficients of Bézout's identity. That is, it finds integers x and y such that:
ax + by = gcd(a,b)This algorithm is particularly useful in:
- Finding multiplicative inverses in modular arithmetic
- Solving linear Diophantine equations
- Public key cryptography (RSA algorithm)
Here's how it works:
- Initialize:
- r1 = a, r2 = b
- s1 = 1, s2 = 0
- t1 = 0, t2 = 1
- While r2 > 0:
- Calculate quotient: q = r1/r2
- Update remainders: r = r1 - q×r2
- Update coefficients: s = s1 - q×s2, t = t1 - q×t2
- Update values for next iteration
For example, let's find GCD(48, 18) and coefficients:
48 = 2 × 18 + 12
18 = 1 × 12 + 6
12 = 2 × 6 + 0
Working backwards:
6 = 18 - 1(12)
6 = 18 - 1(48 - 2×18)
6 = 3×18 - 1×48Therefore: 3×18 - 1×48 = 6 The coefficients are x = -1 and y = 3
19+ registered 
