The Euclidean Algorithm for Greatest Common Divisor
Formulated by the ancient Greek mathematician Euclid in Book VII of his Elements (circa 300 BC), the Euclidean algorithm is one of the oldest and most computationally efficient numerical algorithms in history.
How the Algorithm Operates
Given two positive integers $a$ and $b$ where $a \ge b$:
- Compute the quotient $q$ and remainder $r$ such that $a = b \cdot q + r$, where $0 \le r < b$.
- If $r = 0$, the algorithm terminates and $\text{GCD}(a, b) = b$.
- If $r > 0$, replace $a \leftarrow b$ and $b \leftarrow r$, and repeat step 1.
| Step | Division Equation: a = b × q + r | Remainder (r) |
|---|---|---|
| Step 1 | 180 = 48 × 3 + 36 | r = 36 |
| Step 2 | 48 = 36 × 1 + 12 | r = 12 |
| Step 3 | 36 = 12 × 3 + 0 | r = 0 (Stop! GCD = 12) |
Frequently Asked Questions
What is the GCD of two prime numbers?
Since prime numbers have no positive divisors other than 1 and themselves, the GCD of any two distinct prime numbers (such as 13 and 29) is always exactly 1.
Can the GCD of two numbers be larger than either number?
No. By definition, a common divisor must divide both numbers without remainder. Therefore, GCD(a, b) can never exceed min(a, b). It equals min(a, b) only when the smaller number divides the larger number completely (e.g. GCD(6, 24) = 6).