I consider Euclid’s algorithm one of the oldest algorithms still in everyday use, and I find that remarkable given how much computing has changed since its origin. It is a method for efficiently computing the greatest common divisor (GCD) of two integers, meaning the largest number that divides both of them without leaving a remainder. Despite its age, I still reach for it constantly, whether directly or as a building block inside other algorithms like RSA key generation, which I described earlier in this collection.
History and Background
I trace this algorithm back to the ancient Greek mathematician Euclid, who described it in his book “Elements,” written around 300 BCE. Euclid presented it as a geometric procedure for finding a common measure of two lengths, though the arithmetic version I use today is the one most familiar in computer science. Some historians believe the underlying idea may predate Euclid, possibly originating with earlier Greek mathematicians like Eudoxus, but Euclid’s writings are the earliest surviving complete description. What I find striking is that this makes Euclid’s algorithm one of the oldest algorithms in continuous documented use in human history, and it is often cited as the first true algorithm in the modern sense: a well-defined, finite sequence of steps guaranteed to produce a correct result.
Problem Statement
The problem Euclid’s algorithm solves is finding the greatest common divisor of two non-negative integers efficiently. I could, in principle, find the GCD by listing every divisor of both numbers and finding the largest one they share, but this brute-force approach becomes impractical for large numbers, since it requires checking many candidate divisors. Euclid’s algorithm solves this far more efficiently by relying on a simple but powerful mathematical observation about how remainders behave under division.
Core Concepts
Terms I use throughout my explanation:
- Greatest common divisor (GCD): the largest positive integer that divides two given integers without leaving a remainder.
- Divisibility: an integer $a$ is divisible by $b$ if there exists an integer $k$ such that $a = bk$.
- Modulo operation: the remainder left after dividing one integer by another, written $a \bmod b$.
- Recursive algorithm: an algorithm that calls itself on a smaller version of the same problem until it reaches a base case.
- Bézout’s identity: a related concept stating that the GCD of two integers $a$ and $b$ can always be expressed as an integer linear combination $ax + by = \gcd(a, b)$ for some integers $x$ and $y$, which the extended version of Euclid’s algorithm computes directly.
How It Works
I break the standard (non-extended) version of Euclid’s algorithm into these steps:
- I start with two integers, $a$ and $b$, where I want to find $\gcd(a, b)$.
- If $b$ equals zero, the algorithm stops, and $a$ is the greatest common divisor.
- Otherwise, I compute the remainder $r = a \bmod b$.
- I replace $a$ with $b$, and replace $b$ with $r$.
- I repeat from step 2 until $b$ becomes zero.
Working Principle
I rely on a key mathematical fact: for any two integers $a$ and $b$ (with $b \neq 0$), $\gcd(a, b) = \gcd(b, a \bmod b)$. This is true because any number that divides both $a$ and $b$ must also divide $a – qb$ for any integer $q$, and since $a \bmod b$ is exactly $a – qb$ for the appropriate quotient $q$, any common divisor of $a$ and $b$ is also a common divisor of $b$ and $a \bmod b$, and vice versa. By repeatedly replacing the pair $(a, b)$ with $(b, a \bmod b)$, I keep shrinking the numbers involved while preserving the GCD, until eventually the remainder reaches zero, at which point the other number in the pair must be the GCD, since any number divides itself and zero.
Mathematical Foundation
The core recursive identity is:
$$\gcd(a, b) = \gcd(b, a \bmod b)$$
with the base case:
$$\gcd(a, 0) = a$$
I can prove this identity directly. Let $d$ be any common divisor of $a$ and $b$. Since $a = qb + r$ for some quotient $q$ and remainder $r = a \bmod b$, I can rearrange to $r = a – qb$. Since $d$ divides both $a$ and $b$, it must divide $a – qb = r$ as well, so $d$ is also a common divisor of $b$ and $r$. Conversely, if $d$ divides both $b$ and $r$, then $d$ divides $qb + r = a$ as well, so $d$ is a common divisor of $a$ and $b$. Since the sets of common divisors of $(a, b)$ and $(b, r)$ are identical, their greatest elements, the GCDs, must be equal too.
The extended version additionally tracks coefficients satisfying Bézout’s identity:
$$ax + by = \gcd(a, b)$$
which I compute by keeping track of how $x$ and $y$ evolve alongside $a$ and $b$ at each recursive step.
Diagrams
flowchart TD
A["Start with a, b"] --> B{"Is b equal to 0?"}
B -->|Yes| C["Return a as the GCD"]
B -->|No| D["Compute r = a mod b"]
D --> E["Set a = b, b = r"]
E --> BPseudocode
function EUCLID_GCD(a, b):
while b != 0:
temp = b
b = a mod b
a = temp
return a
function EUCLID_GCD_RECURSIVE(a, b):
if b == 0:
return a
return EUCLID_GCD_RECURSIVE(b, a mod b)
function EXTENDED_EUCLID(a, b):
if b == 0:
return (a, 1, 0) // gcd, x, y such that a*x + b*y = gcd
(gcd, x1, y1) = EXTENDED_EUCLID(b, a mod b)
x = y1
y = x1 - (a div b) * y1
return (gcd, x, y)
Step-by-Step Example
I will trace through computing $\gcd(48, 18)$.
- I start with $a = 48$, $b = 18$.
- Since $b \neq 0$, I compute $r = 48 \bmod 18 = 12$.
- I set $a = 18$, $b = 12$.
- Since $b \neq 0$, I compute $r = 18 \bmod 12 = 6$.
- I set $a = 12$, $b = 6$.
- Since $b \neq 0$, I compute $r = 12 \bmod 6 = 0$.
- I set $a = 6$, $b = 0$.
- Since $b = 0$, the algorithm stops, and the GCD is $6$.
I can verify this: $48 = 6 \times 8$ and $18 = 6 \times 3$, and $6$ is indeed the largest number dividing both evenly.
Time Complexity
I find Euclid’s algorithm remarkably efficient: it runs in $O(\log(\min(a, b)))$ time, meaning the number of steps grows only logarithmically with the size of the smaller input. This bound comes from the fact that the remainder at least halves every two steps in the worst case, and the theoretical worst case (where the algorithm takes the most steps relative to the size of the inputs) occurs when $a$ and $b$ are consecutive Fibonacci numbers, a result known as Lamé’s theorem. Even for very large numbers, such as the hundreds-of-digits values used in RSA key generation, Euclid’s algorithm remains extremely fast in practice.
Space Complexity
The iterative version of Euclid’s algorithm uses only a constant amount of extra space, $O(1)$, since it just needs to track the current pair of numbers and a temporary variable during each swap. The recursive version uses $O(\log(\min(a, b)))$ space due to the call stack, since each recursive call adds a new stack frame until the base case is reached, matching the same logarithmic bound as the time complexity.
Correctness Analysis
I demonstrated the correctness of Euclid’s algorithm mathematically above by proving that $\gcd(a, b) = \gcd(b, a \bmod b)$ for all valid inputs, showing that the set of common divisors of $(a, b)$ is identical to the set of common divisors of $(b, a \bmod b)$. Since each step preserves the GCD exactly while strictly decreasing the values involved (the remainder is always smaller than the divisor), the algorithm is guaranteed to terminate, and when it does, at the point where $b$ reaches zero, the value of $a$ at that moment must equal the original GCD, since $\gcd(a, 0) = a$ trivially. This combination of an invariant (GCD is preserved at every step) and guaranteed termination (values strictly decrease and are bounded below by zero) is what makes the correctness proof airtight.
Advantages
- I find Euclid’s algorithm extremely fast, running in logarithmic time even for very large numbers.
- It requires only basic arithmetic operations (division and modulo), making it simple to implement in virtually any programming environment.
- The extended version conveniently gives me the Bézout coefficients as a byproduct, which I need for computing modular inverses, a critical step in algorithms like RSA.
- It works correctly and efficiently regardless of how large the input numbers are, as long as I have a way to perform division and modulo on them.
Disadvantages
- For extremely large numbers (such as those used in modern cryptography), even Euclid’s algorithm’s logarithmic step count can involve computationally expensive division operations at each step, so specialized “binary GCD” variants that avoid division altogether are sometimes preferred in performance-critical cryptographic contexts.
- The recursive version can hit stack depth limits in some programming environments if used naively on adversarially chosen or extremely large inputs, though this is rarely an issue in practice given the logarithmic depth.
- It only computes the GCD of two numbers directly; finding the GCD of more than two numbers requires applying the algorithm repeatedly across pairs, which, while straightforward, is an extra step I need to remember to implement.
Applications
I rely on Euclid’s algorithm constantly, both directly and as a hidden building block. I use it to simplify fractions to their lowest terms by dividing both numerator and denominator by their GCD. I use its extended version to compute modular multiplicative inverses, which is essential for RSA key generation, as I described earlier in this collection when computing the private exponent $d$. I have also seen it used in computer graphics for tasks like determining aspect ratios, in music theory for calculating rhythmic relationships, and in various number-theoretic algorithms as a fundamental subroutine, including in the Euclidean algorithm’s extension to polynomial GCDs used in some error-correcting codes.
Implementation in C
#include <stdio.h>
/* Iterative version of Euclid's algorithm */
int gcd_iterative(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
/* Recursive version of Euclid's algorithm */
int gcd_recursive(int a, int b) {
if (b == 0) {
return a;
}
return gcd_recursive(b, a % b);
}
/* Extended Euclid's algorithm, returns gcd and sets x, y such that
a*x + b*y = gcd(a, b) */
int extended_gcd(int a, int b, int *x, int *y) {
if (b == 0) {
*x = 1;
*y = 0;
return a;
}
int x1, y1;
int gcd = extended_gcd(b, a % b, &x1, &y1);
*x = y1;
*y = x1 - (a / b) * y1;
return gcd;
}
int main() {
int a = 48, b = 18;
printf("gcd_iterative(%d, %d) = %d\n", a, b, gcd_iterative(a, b));
printf("gcd_recursive(%d, %d) = %d\n", a, b, gcd_recursive(a, b));
int x, y;
int g = extended_gcd(a, b, &x, &y);
printf("extended_gcd(%d, %d) = %d, with x = %d, y = %d\n", a, b, g, x, y);
printf("Verification: %d * %d + %d * %d = %d\n", a, x, b, y, a * x + b * y);
return 0;
}
Sample Input and Output
Running the program on $a = 48$ and $b = 18$ produces gcd_iterative(48, 18) = 6 and gcd_recursive(48, 18) = 6, matching the manual trace I walked through earlier. The extended Euclidean algorithm outputs extended_gcd(48, 18) = 6, along with coefficients such as x = -1, y = 3 (exact values depend on the recursion path, but they always satisfy the identity), and the verification line confirms that 48 * (-1) + 18 * 3 = 6, matching the computed GCD exactly.
Optimization Techniques
I have found a few refinements worth knowing about:
- The binary GCD algorithm (also called Stein’s algorithm) replaces expensive division and modulo operations with bit shifts, subtraction, and parity checks, which can be significantly faster on hardware where division is costly, particularly for very large numbers used in cryptography.
- Using the iterative version instead of the recursive version avoids any function call overhead and stack usage concerns, which matters in performance-sensitive or embedded environments.
- When I need to compute the GCD of more than two numbers, I fold the computation pairwise, computing $\gcd(\gcd(a, b), c)$ and so on, rather than trying to invent a more complex multi-argument version.
- For big integers used in cryptographic contexts, using a well-optimized big-integer library’s built-in GCD implementation is generally better than a naive hand-written version, since these libraries often include the binary GCD optimization and other low-level tuning.
Common Mistakes
I sometimes see mistakes where developers assume gcd(a, 0) should be undefined or throw an error, when mathematically it is correctly defined as a itself, and handling this base case incorrectly can cause subtle bugs. I also see off-by-one or sign-handling errors when applying Euclid’s algorithm to negative numbers, since the standard algorithm assumes non-negative integers, and care is needed if negative inputs are possible in a given application. Another mistake I have seen is reimplementing the extended Euclidean algorithm incorrectly by mixing up which variable tracks $x$ versus $y$ during the back-substitution step, leading to Bézout coefficients that do not actually satisfy the required identity.
Further Reading
- Euclid, “Elements,” Book VII, Propositions 1 and 2 (various translations available). https://mathcs.clarku.edu/~djoyce/java/elements/bookVII/bookVII.html
- Knuth, D. “The Art of Computer Programming, Volume 2: Seminumerical Algorithms,” section on Euclid’s Algorithm.
- Stein, J. “Computational problems associated with Racah algebra.” Journal of Computational Physics, 1967, describing the binary GCD algorithm.
- Cormen, T., Leiserson, C., Rivest, R., and Stein, C. “Introduction to Algorithms,” chapter on Number-Theoretic Algorithms. https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
