euclid's algorithm

Topics

• modular arithmetic
• divisibility

It efficiently computes the Greatest Common Divisor (GCD) and has variations crucial for solving complex problems.

gcd(a, b) = gcd(b, a % b) until b = 0.

3 popular variants:

• standard euclidean algorithm
• extended euclidean algorithm
• binary gcd aka Stein’s algorithm

The applications are plenty:

• Finding modular multiplicative inverse
• Solving linear diophantine equations
• Chinese Remainder Theorem (CRT)
• Simplifying fractions by dividing numerator and denominator by their GCD

Tip

In array GCD, exit early if intermediate GCD becomes 1.

Related