Introduction to Euclidean Algorithm
The Euclidean Algorithm is one of the oldest algorithms still in common use. Named after the ancient Greek mathematician Euclid, who described it in his Elements (c. 300 BC), this algorithm efficiently computes the greatest common divisor (GCD) of two integers.
The Euclidean Algorithm predates computers by over two millennia but remains one of the most efficient algorithms for computing GCDs. Its applications span from ancient Greek mathematics to modern cryptography and computer science.
Ancient Origins
First described by Euclid in Book VII of his Elements around 300 BC. Used by ancient Greek mathematicians for number theory and Number-Theory.
Efficiency
One of the first algorithms analyzed for computational complexity. Runs in O(log min(a, b)) time, making it extremely fast even for large numbers.
Modern Applications
Essential for RSA encryption, modular arithmetic, and computer algebra systems. Forms the basis for many cryptographic protocols.
- Fundamental Concept: Core to number theory and algebra
- Practical Applications: Used in cryptography, computer science, and engineering
- Algorithmic Thinking: Excellent example of efficient algorithm design
- Mathematical Beauty: Simple yet powerful mathematical idea
- Historical Importance: One of the oldest algorithms still in use
Improve your understanding by working through practical tasks with the gcf-calculator.
What is 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. Also known as the greatest common factor (GCF) or highest common factor (HCF).
Where:
- a, b are integers (not both zero)
- d | a means "d divides a" (a is divisible by d)
- ℕ represents the set of natural numbers (positive integers)
Examples:
gcd(48, 18) = 6 because 6 is the largest number dividing both 48 and 18
gcd(17, 5) = 1 (17 and 5 are coprime)
gcd(0, 5) = 5 (by definition, gcd(a, 0) = |a|)
gcd(60, 84) = 12
- Commutative: gcd(a, b) = gcd(b, a)
- gcd(a, 0): gcd(a, 0) = |a|
- gcd with negative numbers: gcd(a, b) = gcd(|a|, |b|)
- Distributive: gcd(ka, kb) = |k|·gcd(a, b) for any integer k
- Linear combination: gcd(a, b) is the smallest positive integer of the form ax + by
The naive approach to find gcd(a, b) is to:
- List all divisors of a
- List all divisors of b
- Find the largest number appearing in both lists
Example: gcd(48, 18)
Divisors of 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48
Divisors of 18: 1, 2, 3, 6, 9, 18
Common divisors: 1, 2, 3, 6
Greatest common divisor: 6
The naive method becomes inefficient for large numbers because:
- Finding all divisors requires checking up to √n numbers
- For large numbers (e.g., 100-digit numbers), this is computationally infeasible
- The Euclidean Algorithm provides a much more efficient solution
Take your learning further by practicing real examples using the gcf-calculator.
The 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.
For any integers a and b (with b > 0), there exist unique integers q (quotient) and r (remainder) such that:
The key insight: gcd(a, b) = gcd(b, r)
Given two positive integers a and b (with a ≥ b):
- If b = 0, then gcd(a, b) = a
- Otherwise, compute r = a mod b (remainder when a is divided by b)
- Set a = b, b = r
- Repeat from step 1
The algorithm can be expressed recursively:
if b == 0:
return a
else:
return gcd(b, a mod b)
For computational efficiency, an iterative approach is often used:
while b ≠ 0:
t = b
b = a mod b
a = t
return a
Theorem: For any integers a, b with b > 0, gcd(a, b) = gcd(b, a mod b)
Proof:
- Let d = gcd(a, b). Then d divides both a and b.
- Write a = bq + r where r = a mod b.
- Since d divides a and b, it must also divide r = a - bq.
- Thus d divides both b and r, so d ≤ gcd(b, r).
- Conversely, let d' = gcd(b, r). Then d' divides both b and r.
- Since a = bq + r, d' must also divide a.
- Thus d' divides both a and b, so d' ≤ gcd(a, b).
- Therefore, gcd(a, b) = gcd(b, r). ∎
Step-by-Step Examples
Let's work through several examples to understand how the Euclidean Algorithm works in practice.
Let's compute gcd(48, 18) using the Euclidean Algorithm:
This example appears in Euclid's original work:
Let's trace through another example:
When numbers are coprime (relatively prime), their GCD is 1:
Try It Yourself
Enter two numbers to see the Euclidean Algorithm in action:
Enter two numbers and click "Calculate GCD" to see the step-by-step process.
Measure your knowledge with real-world exercises on the gcf-calculator.
Extended Euclidean Algorithm
The Extended Euclidean Algorithm not only computes gcd(a, b) but also finds integers x and y such that:
This equation is known as Bézout's identity, and the coefficients x and y are called Bézout coefficients.
For any integers a and b (not both zero), there exist integers x and y such that:
Moreover, gcd(a, b) is the smallest positive integer that can be expressed in this form.
The Extended Euclidean Algorithm works by keeping track of coefficients as we perform the standard Euclidean Algorithm:
- Initialize: (x₁, y₁) = (1, 0), (x₂, y₂) = (0, 1)
- While b ≠ 0:
- Compute quotient q = a ÷ b (integer division)
- Compute remainder r = a mod b
- Update coefficients: (x, y) = (x₁ - qx₂, y₁ - qy₂)
- Shift: a = b, b = r, x₁ = x₂, y₁ = y₂, x₂ = x, y₂ = y
- Result: gcd = a, coefficients = (x₁, y₁)
Let's find x and y such that 48x + 18y = gcd(48, 18) = 6:
function extendedGcd(a, b):
if b == 0:
return (a, 1, 0)
else:
g, x1, y1 = extendedGcd(b, a mod b)
x = y1
y = x1 - (a // b) * y1
return (g, x, y)
Extended GCD Calculator
Find Bézout coefficients for ax + by = gcd(a, b):
Enter two numbers to find x and y such that ax + by = gcd(a, b).
Applications of Euclidean Algorithm
The Euclidean Algorithm has numerous practical applications beyond just computing GCDs:
Simplifying Fractions
To simplify a fraction a/b, divide both numerator and denominator by gcd(a, b):
This gives the fraction in lowest terms.
Diophantine Equations
Solving linear equations of the form ax + by = c. Solutions exist only if gcd(a, b) divides c.
Solution: x = -1 + 3k, y = 3 - 8k
Modular Inverses
Finding modular inverses using Extended Euclidean Algorithm. For a mod m, find x such that:
iff gcd(a, m) = 1
Least Common Multiple
Computing LCM using the relationship with GCD:
Example: lcm(48, 18) = 864/6 = 144
| Field | Application | How Euclidean Algorithm Helps |
|---|---|---|
| Computer Science | Algorithm Analysis | Example of efficient recursive algorithm |
| Cryptography | RSA Encryption | Finding modular inverses, key generation |
| Engineering | Signal Processing | Simplifying rational transfer functions |
| Mathematics | Number Theory | Fundamental tool for proofs and computations |
| Education | Teaching Algorithms | Classic example of elegant algorithm design |
Test and improve your skills using the gcf-calculator.
Applications in Cryptography
The Extended Euclidean Algorithm is fundamental to modern cryptography, particularly in public-key cryptosystems like RSA.
RSA (Rivest-Shamir-Adleman) is one of the first practical public-key cryptosystems and is widely used for secure data transmission.
The Extended Euclidean Algorithm is used in RSA to:
- Find the modular inverse of e modulo φ(n) during key generation
- Compute the private key d such that ed ≡ 1 (mod φ(n))
- Ensure that e and φ(n) are coprime (gcd(e, φ(n)) = 1)
Let's see how the Extended Euclidean Algorithm is used in RSA:
The modular inverse of a modulo m exists if and only if gcd(a, m) = 1. The Extended Euclidean Algorithm finds it:
function modInverse(a, m):
g, x, y = extendedGcd(a, m)
if g ≠ 1:
return "No inverse exists"
else:
return x mod m
Diffie-Hellman Key Exchange
Uses modular arithmetic and the fact that finding discrete logarithms is hard. The Euclidean Algorithm helps verify that chosen parameters are valid.
Elliptic Curve Cryptography
ECC operations involve arithmetic on elliptic curves. The Extended Euclidean Algorithm is used for computing modular inverses in finite fields.
Digital Signatures
Digital signature algorithms like DSA use modular arithmetic and require computing modular inverses, which relies on the Extended Euclidean Algorithm.
Chinese Remainder Theorem
Used to speed up RSA decryption. The Extended Euclidean Algorithm helps find coefficients for combining solutions from different moduli.
Interactive Euclidean Algorithm Calculator
Complete GCD Calculator
Compute GCD, LCM, Bézout coefficients, and modular inverses all in one tool.
Enter numbers and click "Compute All" to see comprehensive results.
Practice Problems
Solution:
Solution:
Solution:
Refine your understanding through guided practice with the gcf-calculator.
Time Complexity and Efficiency
The Euclidean Algorithm is remarkably efficient. Its time complexity is O(log min(a, b)), making it suitable for very large numbers.
Gabriel Lamé proved that the number of division steps in the Euclidean Algorithm for two numbers is at most five times the number of digits in the smaller number.
More precisely, for a ≥ b > 0, the number of steps is ≤ 5·log₁₀b.
| Method | Time Complexity | Steps for 100-digit numbers | Practicality |
|---|---|---|---|
| Naive (trial division) | O(√n) | ~10⁵⁰ operations | Impossible |
| Euclidean Algorithm | O(log n) | ~500 operations | Instant |
| Binary GCD Algorithm | O(log n) | ~500 operations | Very fast |
| Extended Euclidean | O(log n) | ~500 operations | Very fast |
The Euclidean Algorithm reduces numbers quickly because:
- Each step reduces the larger number by at least half (in the worst case)
- Fibonacci numbers represent the worst-case scenario
- For Fibonacci numbers Fₙ, Fₙ₊₁: gcd(Fₙ, Fₙ₊₁) takes n steps
- Since Fₙ ≈ φⁿ/√5, n ≈ logφ(Fₙ) ≈ 1.44 log₁₀(Fₙ)
Also known as Stein's algorithm, this variant uses bitwise operations and is even more efficient on computers:
if a == b: return a
if a == 0: return b
if b == 0: return a
if a is even:
if b is odd: return binaryGcd(a/2, b)
else: return 2×binaryGcd(a/2, b/2)
if b is even: return binaryGcd(a, b/2)
if a > b: return binaryGcd((a-b)/2, b)
return binaryGcd((b-a)/2, a)
Practice Problems and Exercises
Test your understanding with these practice problems:
Hint: These are the first six digits of π and e respectively. Start with 314159 = 271828 × 1 + 42331
Hint: First divide by gcd(21, 14) = 7 to get 3x + 2y = 10. Find one solution using Extended Euclidean Algorithm.
Hint: Let d = gcd(a+b, a-b). Show that d divides 2a and 2b, so d divides gcd(2a, 2b) = 2gcd(a, b) = 2.
Python Example:
while b != 0:
a, b = b, a % b
return abs(a)
def extended_gcd(a, b):
if b == 0:
return a, 1, 0
g, x1, y1 = extended_gcd(b, a % b)
return g, y1, x1 - (a // b) * y1
Put theory into action by practicing on the gcf-calculator.