GCD
← Back to Number Theory
Greatest Common Divisor: the largest positive integer that divides two numbers. Computed efficiently using Euclid’s algorithm in O(log(min(a,b))) time. The extended Euclidean algorithm also finds coefficients for Bezout’s identity. Essential in simplifying fractions and cryptographic key generation.