Introduction to the Euclidean Algorithm
The Euclidean Algorithm is one of the oldest and most important algorithms in mathematics. Developed by Euclid around 300 BCE, it provides an efficient method for computing the greatest common divisor (GCD) of two integers.
Why the Euclidean Algorithm Matters:
- Foundational algorithm in number theory and computer science
- Essential for simplifying fractions to lowest terms
- Core component of RSA encryption and other cryptographic systems
- Used in solving Diophantine equations
- Basis for the Extended Euclidean Algorithm
- Applications in computer graphics, signal processing, and error correction
In this comprehensive guide, we'll explore the Euclidean Algorithm from basic concepts to advanced applications, with clear explanations, visual examples, and interactive practice problems to help you master this essential mathematical tool.
What is the Greatest Common Divisor (GCD)?
The Greatest Common Divisor (GCD) of two integers is the largest positive integer that divides both numbers without leaving a remainder.
Read as: "The greatest common divisor of a and b is the maximum positive integer d that divides both a and b."
Examples:
gcd(12, 18) = 6 (divisors of 12: 1,2,3,4,6,12; divisors of 18: 1,2,3,6,9,18)
gcd(17, 25) = 1 (17 and 25 are coprime)
gcd(48, 180) = 12
gcd(0, 5) = 5 (by convention, gcd(0, n) = |n|)
- Commutative: gcd(a, b) = gcd(b, a)
- Associative: gcd(a, gcd(b, c)) = gcd(gcd(a, b), c)
- Distributive: gcd(ab, ac) = |a|·gcd(b, c)
- gcd(a, 0) = |a|
- gcd(a, 1) = 1
- If a | b, then gcd(a, b) = |a|
GCD Explorer
Basic Euclidean Algorithm
The Euclidean Algorithm is based on the principle that the GCD of two numbers does not change if the larger number is replaced by its difference with the smaller number.
Proof: If d divides both a and b, then d divides a - qb for any integer q. In particular, d divides a mod b = a - ⌊a/b⌋·b.
Step 1: Start with two positive integers a and b, where a ≥ b
Step 2: Compute r = a mod b
Step 3: Replace a with b, and b with r
Step 4: Repeat steps 2-3 until b = 0
Step 5: When b = 0, the GCD is a
Example: Find gcd(48, 18)
48 = 18 × 2 + 12 → gcd(48, 18) = gcd(18, 12)
18 = 12 × 1 + 6 → gcd(18, 12) = gcd(12, 6)
12 = 6 × 2 + 0 → gcd(12, 6) = 6
Answer: gcd(48, 18) = 6
Interactive Euclidean Algorithm
Enter numbers and click "Run Algorithm" to see the steps
def gcd(a, b):
while b != 0:
a, b = b, a % b
return abs(a)
# Recursive implementation
def gcd_recursive(a, b):
if b == 0:
return abs(a)
return gcd_recursive(b, a % b)
Extended Euclidean Algorithm
The Extended Euclidean Algorithm not only computes gcd(a, b) but also finds integers x and y such that:
Theorem: For any integers a and b, there exist integers x and y satisfying this equation.
Step 1: Initialize (x₁, y₁) = (1, 0) and (x₂, y₂) = (0, 1)
Step 2: While b ≠ 0, compute quotient q = ⌊a/b⌋
Step 3: Update (a, b) = (b, a mod b)
Step 4: Update (x₁, y₁, x₂, y₂) = (x₂, y₂, x₁ - q·x₂, y₁ - q·y₂)
Step 5: When b = 0, gcd = a, and x = x₁, y = y₁
Example: Find x and y such that 48x + 18y = gcd(48, 18) = 6
Using Extended Euclidean Algorithm:
48 = 18 × 2 + 12 → 12 = 48 - 2×18
18 = 12 × 1 + 6 → 6 = 18 - 1×12 = 18 - 1×(48 - 2×18) = -1×48 + 3×18
Solution: x = -1, y = 3 (Check: 48×(-1) + 18×3 = -48 + 54 = 6 ✓)
Extended Euclidean Algorithm Calculator
Results will appear in a table format
Modular Inverse using Extended Euclidean Algorithm
The modular inverse of a modulo m is an integer x such that:
Exists if and only if: gcd(a, m) = 1 (a and m are coprime)
Step 1: Use Extended Euclidean Algorithm to find x and y such that ax + my = 1
Step 2: Reduce x modulo m to get the inverse in range [0, m-1]
Step 3: The modular inverse is x mod m
Example: Find the modular inverse of 7 modulo 26
We need x such that 7x ≡ 1 (mod 26)
Using Extended Euclidean Algorithm: gcd(7, 26) = 1
26 = 7 × 3 + 5 → 5 = 26 - 3×7
7 = 5 × 1 + 2 → 2 = 7 - 1×5 = 7 - 1×(26 - 3×7) = 4×7 - 1×26
5 = 2 × 2 + 1 → 1 = 5 - 2×2 = (26 - 3×7) - 2×(4×7 - 1×26) = 3×26 - 11×7
Thus: -11×7 + 3×26 = 1
Modular inverse: x = -11 ≡ 15 (mod 26)
Check: 7 × 15 = 105 ≡ 1 (mod 26) ✓
Modular Inverse Calculator
def mod_inverse(a, m):
# Returns modular inverse of a modulo m
g, x, y = extended_gcd(a, m)
if g != 1:
raise Exception('Modular inverse does not exist')
return x % m
def extended_gcd(a, b):
if a == 0:
return b, 0, 1
g, x1, y1 = extended_gcd(b % a, a)
x = y1 - (b // a) * x1
y = x1
return g, x, y
Complexity Analysis of Euclidean Algorithm
The Euclidean Algorithm is remarkably efficient. Its time complexity is logarithmic in the size of the input numbers.
Proof: Based on Lamé's Theorem, the number of steps is at most 5 times the number of digits in the smaller number.
Best Case: When one number is a multiple of the other
Complexity: O(1)
Example: gcd(100, 200) = 100 (1 step)
Average Case: Random numbers
Complexity: O(log min(a, b))
Steps: Approximately 2.078 log₁₀(min(a, b)) + 1.672
Worst Case: Consecutive Fibonacci numbers
Complexity: O(log φ min(a, b))
Example: gcd(Fₙ, Fₙ₋₁) takes n-1 steps
Space Complexity: Iterative version
Complexity: O(1)
Memory: Constant space for variables
Theorem: For integers a ≥ b ≥ 1, the number of division steps in the Euclidean Algorithm is at most 5 times the number of decimal digits in b.
Example: For b = 1000 (4 digits), at most 20 steps are needed
Proof Sketch: The worst case occurs with consecutive Fibonacci numbers. Since Fibonacci numbers grow exponentially, the number of digits increases linearly with the index.
Complexity Analyzer
Real-World Applications of Euclidean Algorithm
The Euclidean Algorithm has numerous practical applications in computer science, cryptography, and engineering.
Cryptography (RSA)
The Extended Euclidean Algorithm is essential for RSA encryption:
Key Generation: Compute modular inverses for public/private key pairs
Example: Finding d such that e·d ≡ 1 mod φ(n)
Without the Euclidean Algorithm, RSA encryption would be impractical.
Simplifying Fractions
Reducing fractions to lowest terms:
Process: Divide numerator and denominator by their GCD
Example: 48/18 = (48÷6)/(18÷6) = 8/3
Used in computer algebra systems and educational software.
Computer Graphics
Simplifying ratios for aspect ratios and scaling:
Example: Screen resolution 1920×1080 has aspect ratio 16:9
gcd(1920, 1080) = 120
1920/120 = 16, 1080/120 = 9
Used in image processing and display technology.
Solving Diophantine Equations
Finding integer solutions to linear equations:
Example: Solve 48x + 18y = 6
Using Extended Euclidean Algorithm: x = -1, y = 3
General solution: x = -1 + 3k, y = 3 - 8k for any integer k
Used in number theory and optimization problems.
Problem: Generate RSA keys for small primes p=61, q=53
Step 1: Compute n = p×q = 61×53 = 3233
Step 2: Compute φ(n) = (p-1)(q-1) = 60×52 = 3120
Step 3: Choose e = 17 (coprime with 3120)
Step 4: Use Extended Euclidean Algorithm to find d such that e·d ≡ 1 mod φ(n)
Step 5: Solve 17d ≡ 1 mod 3120 → d = 2753
Public Key: (e, n) = (17, 3233)
Private Key: (d, n) = (2753, 3233)
Verification: 17 × 2753 = 46801 ≡ 1 mod 3120 ✓
Interactive Practice
Euclidean Algorithm Practice Tool
Practice all Euclidean Algorithm concepts with randomly generated problems or create your own.
Select a topic and click "Generate Problem"
Solution:
1071 = 462 × 2 + 147
462 = 147 × 3 + 21
147 = 21 × 7 + 0
Answer: gcd(1071, 462) = 21
Solution:
gcd(35, 15) = 5
35 = 15 × 2 + 5 → 5 = 35 - 2×15
Thus: x = 1, y = -2
Check: 35×1 + 15×(-2) = 35 - 30 = 5 ✓
Answer: x = 1, y = -2
Euclidean Algorithm Summary & Cheat Sheet
| Concept | Definition | Formula/Algorithm | Time Complexity |
|---|---|---|---|
| GCD | Greatest Common Divisor | Largest integer dividing both numbers | - |
| Euclidean Algorithm | Compute GCD using remainders | gcd(a, b) = gcd(b, a mod b) | O(log min(a, b)) |
| Extended Euclidean | Find Bézout coefficients | ax + by = gcd(a, b) | O(log min(a, b)) |
| Modular Inverse | Multiplicative inverse modulo m | a·a⁻¹ ≡ 1 (mod m) | O(log m) |
| Bézout's Identity | Linear combination equals GCD | ∃x,y: ax + by = gcd(a, b) | - |
| Lamé's Theorem | Upper bound on steps | Steps ≤ 5 × digits in smaller number | - |
Mistake: Not handling negative numbers
Wrong: gcd(-12, 18) = -6
Correct: gcd(-12, 18) = 6 (take absolute values)
Mistake: Assuming modular inverse always exists
Wrong: 2⁻¹ mod 4 exists
Correct: Inverse exists only if gcd(a, m) = 1
Mistake: Confusing gcd with lcm
Wrong: gcd(4, 6) = 24
Correct: gcd(4, 6) = 2, lcm(4, 6) = 12
Mistake: Incorrect Bézout coefficient signs
Wrong: 48x + 18y = 6 has x=1, y=3
Correct: x = -1, y = 3 (Check: 48×(-1) + 18×3 = 6)
- Always take absolute values: gcd(a, b) = gcd(|a|, |b|)
- Use the iterative version: More efficient than recursive for large numbers
- Check your work: Verify gcd divides both numbers and is the largest such divisor
- Understand the connection: Extended Euclidean Algorithm gives modular inverses
- Practice with Fibonacci numbers: They give the worst-case performance
- Learn the applications: Understanding uses in cryptography reinforces the concepts
function gcd(a, b) {
a = Math.abs(a);
b = Math.abs(b);
while (b !== 0) {
[a, b] = [b, a % b];
}
return a;
}
function extendedGcd(a, b) {
if (b === 0) return [a, 1, 0];
const [g, x1, y1] = extendedGcd(b, a % b);
return [g, y1, x1 - Math.floor(a / b) * y1];
}
function modInverse(a, m) {
const [g, x] = extendedGcd(a, m);
if (g !== 1) throw new Error('No modular inverse');
return (x % m + m) % m;
}