GCD & Euclidean Algorithm
The Greatest Common Divisor (GCD) of two numbers is the largest number that divides both of them evenly. The Euclidean algorithm is an ancient and elegant method to find it.
Why GCD matters: Finding the GCD is essential for computing modular inverses, which are the key to RSA decryption.
The Euclidean Algorithm
The algorithm is based on a simple observation: GCD(a, b) = GCD(b, a mod b). We keep applying this until we reach 0.
Click "Calculate" to see the steps...
How It Works
Let's trace through an example: GCD(252, 105)
- 252 = 105 × 2 + 42 → GCD(252, 105) = GCD(105, 42)
- 105 = 42 × 2 + 21 → GCD(105, 42) = GCD(42, 21)
- 42 = 21 × 2 + 0 → GCD(42, 21) = GCD(21, 0) = 21
Extended Euclidean Algorithm
The extended version finds not just the GCD, but also coefficients x and y such that:
ax + by = GCD(a, b)
This is called Bézout's Identity, and it's crucial for finding modular inverses!
Extended GCD Calculator
Enter values to see the extended GCD...
Coprimality
Two numbers are coprime (or relatively prime) if their GCD is 1. This concept is fundamental to cryptography.
Coprimality Checker
Enter values to check if they're coprime...
Why This Matters
Connection to Cryptography: In RSA, we need to find a number e that is coprime to φ(n). The extended Euclidean algorithm then helps us find d, the decryption exponent, as the modular inverse of e.