GCD

Euclidean Algorithm

Examples

In Depth

The Euclidean algorithm is one of the oldest algorithms in mathematics, appearing in Euclid's Elements (c. 300 BCE). It runs in \(O(\log\min(a,b))\) steps — the number of steps is bounded by the number of digits. The extended Euclidean algorithm also finds integers \(x,y\) such that \(ax+by=\gcd(a,b)\) (Bézout's identity).

GCD has a beautiful lattice structure: \(\gcd(a,b)\) is the largest element dividing both \(a\) and \(b\), while \(\text{lcm}(a,b)\) is the smallest multiple of both. The identity \(\gcd(a,b)\cdot\text{lcm}(a,b)=|ab|\) reflects this duality.

In abstract algebra, the GCD generalizes to principal ideal domains (PIDs): \(\gcd(a,b)\) generates the ideal \((a)+(b)=\{ax+by:x,y\in\mathbb{Z}\}\). This perspective unifies integer GCDs with polynomial GCDs and other algebraic structures.

Further Reading & Context

The GCD is the cornerstone of elementary number theory. The identity \(\gcd(a,b)=\gcd(b,a\bmod b)\) drives the Euclidean algorithm, one of the oldest and most efficient algorithms known. The extended version yields Bézout coefficients \(x,y\) with \(ax+by=\gcd(a,b)\), essential for modular inverses.

Properties: \(\gcd(a,b)=\gcd(a,b-a)\) (subtraction form); \(\gcd(a,0)=a\); \(\gcd(a,b)\cdot\text{lcm}(a,b)=ab\). The GCD is the largest element of the ideal \(a\mathbb{Z}+b\mathbb{Z}=\gcd(a,b)\mathbb{Z}\) in \(\mathbb{Z}\).

In abstract algebra, the GCD generalizes to any principal ideal domain (PID). In \(\mathbb{Z}[i]\) (Gaussian integers), the GCD is computed by the Gaussian Euclidean algorithm. In \(F[x]\) (polynomials over a field), the GCD of two polynomials is found by the polynomial Euclidean algorithm.

Applications: simplifying fractions (divide numerator and denominator by GCD); solving linear Diophantine equations (\(ax+by=c\) has solutions iff \(\gcd(a,b)\mid c\)); RSA key generation (checking \(\gcd(e,\phi(n))=1\)); and the Chinese Remainder Theorem (requires pairwise coprime moduli).

The binary GCD algorithm replaces division with subtraction and bit shifts, making it efficient on hardware. The Lehmer GCD algorithm uses single-precision arithmetic to handle most of the computation, falling back to multi-precision only when necessary — a key optimization in computer algebra systems.