The Euclidean algorithm for computing the greatest common divisor is one of the oldest algorithms in mathematics, described in Book VII of Euclid's "Elements" around 300 BCE, though it may have been known to earlier Greek mathematicians including Eudoxus. The algorithm's elegance lies in its simplicity: to find GCD(a, b) where a is greater than b, divide a by b and take the remainder r. If r is zero, b is the GCD. Otherwise, replace a with b and b with r, and repeat. For example, GCD(252, 105): 252 divided by 105 gives remainder 42; 105 divided by 42 gives remainder 21; 42 divided by 21 gives remainder 0; therefore GCD(252, 105) equals 21. The algorithm is guaranteed to terminate because the remainders form a strictly decreasing sequence of non-negative integers, and its efficiency is remarkable: the number of steps is at most five times the number of digits in the smaller number, as shown by Gabriel Lame in 1844.

The mathematical foundation for why the Euclidean algorithm works rests on a key property of divisibility: if d divides both a and b, then d also divides a minus b (and more generally, any linear combination of a and b). Since a equals b times q plus r (the division algorithm), any common divisor of a and b must also divide r, and conversely any common divisor of b and r must divide a. Therefore GCD(a, b) equals GCD(b, r), justifying each step of the algorithm. This reasoning extends to a profound result known as Bezout's identity: for any integers a and b, there exist integers x and y such that ax plus by equals GCD(a, b). The extended Euclidean algorithm computes these coefficients alongside the GCD, and this result is fundamental to modular arithmetic and cryptography.

The application of GCD in modern cryptography, particularly the RSA algorithm, demonstrates how ancient number theory underpins digital security. RSA encryption relies on modular arithmetic with large prime numbers. Key generation involves computing modular multiplicative inverses, which requires the extended Euclidean algorithm. The security of RSA rests on the computational difficulty of factoring large numbers, while the decryption process uses the mathematical relationships between GCD, modular inverses, and Euler's totient function. Without efficient GCD computation, modern public-key cryptography would not be practical.

Number theory foundations connect GCD and LCM through the fundamental relationship: for any positive integers a and b, GCD(a, b) times LCM(a, b) equals a times b. This means LCM can always be computed efficiently from the GCD. The LCM of two numbers equals their product divided by their GCD. For multiple numbers, LCM is computed iteratively: LCM(a, b, c) equals LCM(LCM(a, b), c). Prime factorization provides an alternative perspective: the GCD takes the minimum exponent of each prime factor present in both numbers, while the LCM takes the maximum exponent. For example, 12 equals 2 squared times 3 and 18 equals 2 times 3 squared, so GCD equals 2 times 3 equals 6 and LCM equals 2 squared times 3 squared equals 36. These complementary operations on prime factorizations elegantly encode the fundamental relationship between divisibility and multiplication in the integers.