Euclidean Algorithm GCD- Examples and Methods

What Is the Euclidean Algorithm?

The Euclidean algorithm is a method for finding the Greatest Common Divisor (GCD) of two integers. It's been around for over 2,000 years—Euclid described it around 300 BCE. You probably don't need it for everyday life, but if you're writing cryptography code, solving Diophantine equations, or preparing for a coding interview, you need this in your toolkit.

The algorithm works on a simple principle: the GCD of two numbers doesn't change if you replace the larger number with the difference of the two numbers. Repeat until the numbers match. That's it.

Two Methods Exist—Use the Right One

Most textbooks teach the division-based method because computers love it. The subtraction method is easier to understand by hand but takes longer. Choose based on your situation.

The Division-Based Euclidean Algorithm

Replace the larger number with the remainder when you divide it by the smaller number. Keep doing this until one number becomes zero. The other number is your GCD.

The Subtraction-Based Euclidean Algorithm

Repeatedly subtract the smaller number from the larger one. When both numbers match, that's your GCD. This works but can be slow if you're dealing with numbers like 1,000,000 and 1.

Step-by-Step Examples

Example 1: GCD of 48 and 18

Using the division method:

• 48 ÷ 18 = 2 remainder 12
• 18 ÷ 12 = 1 remainder 6
• 12 ÷ 6 = 2 remainder 0
• GCD = 6

That took three steps. The subtraction method would have taken longer—subtracting 18 from 48 repeatedly gets tedious fast.

Example 2: GCD of 1071 and 462

Working through the algorithm:

• 1071 ÷ 462 = 2 remainder 147
• 462 ÷ 147 = 3 remainder 21
• 147 ÷ 21 = 7 remainder 0
• GCD = 21

This is a classic example—1071 and 462 are consecutive terms in a Fibonacci-like sequence, which makes the algorithm take more steps than usual.

Example 3: GCD of 144 and 89

Numbers that are close together take fewer steps:

• 144 ÷ 89 = 1 remainder 55
• 89 ÷ 55 = 1 remainder 34
• 55 ÷ 34 = 1 remainder 21
• 34 ÷ 21 = 1 remainder 13
• 21 ÷ 13 = 1 remainder 8
• 13 ÷ 8 = 1 remainder 5
• 8 ÷ 5 = 1 remainder 3
• 5 ÷ 3 = 1 remainder 2
• 3 ÷ 2 = 1 remainder 1
• 2 ÷ 1 = 2 remainder 0
• GCD = 1

These numbers are coprime—they share no common factors other than 1. Notice how many steps this took. The algorithm doesn't care; it just keeps working.

The Extended Euclidean Algorithm

The basic algorithm gives you the GCD. The extended version also gives you the coefficients x and y such that:

ax + by = gcd(a, b)

This matters in cryptography, particularly in RSA encryption where you need modular multiplicative inverses.

Extended Algorithm Example: GCD of 35 and 15

Working backwards:

• 35 = 15 × 2 + 5
• 15 = 5 × 3 + 0
• GCD = 5

Now back-substitute:

• 5 = 35 - 15 × 2
• 5 = 35(1) + 15(-2)

So x = 1, y = -2. Verify: 35(1) + 15(-2) = 35 - 30 = 5 ✓

Comparison: Euclidean Algorithm Methods

How to Implement the Euclidean Algorithm

Python Implementation

```python
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
```

The % operator gives you the remainder. That's the entire algorithm.

JavaScript Implementation

```javascript
function gcd(a, b) {
    while (b !== 0) {
        [a, b] = [b, a % b];
    }
    return Math.abs(a);
}
```

C++ Implementation

```cpp
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}
```

Recursive versions work fine for small numbers. For performance-critical code, use the iterative version to avoid stack overflow.

Where This Algorithm Actually Shows Up

• Cryptography — RSA key generation uses the extended Euclidean algorithm for finding modular inverses
• Computer graphics — Simplifying fractions and aspect ratio calculations
• Error-correcting codes — CRC and polynomial-based checksums
• Music theory — Tuning systems and frequency ratios
• Puzzle solving — Chinese Remainder Theorem problems

Common Mistakes to Avoid

Using subtraction for large numbers. If you're calculating GCD(1000000, 2) with subtraction, you'll be there all day. Use division or modulo.

Forgetting to handle negative numbers. The GCD is always non-negative. Take absolute values or handle the sign separately.

Confusing the algorithm with prime factorization. They both find GCD, but the Euclidean algorithm is faster. Factorization is O(√n); Euclidean is O(log n).

Practice Problems

Try these to test your understanding:

1. Find GCD(123456, 7890)
2. Find GCD(100, 35) using only subtraction
3. Find x and y for 35x + 15y = GCD(35, 15)
4. Prove that GCD(a, b) = GCD(b, a % b) always holds

The Bottom Line

The Euclidean algorithm is efficient, ancient, and essential. Two thousand years of staying power means something. Learn the division-based version, memorize the modulo trick, and you can solve any GCD problem in a few lines of code.

No excuses for inefficient prime factorization when you need the GCD of large numbers.