Find the greatest common divisor and least common multiple of two numbers.
GCD found via the Euclidean algorithm. LCM = (a × b) / GCD(a,b).
The greatest common divisor (GCD) of two numbers is the largest number that divides both evenly, while the least common multiple (LCM) is the smallest number that both divide into evenly — they measure opposite things (a shared factor versus a shared multiple), but they're mathematically linked by a single elegant relationship: GCD(a,b) × LCM(a,b) = a × b. This means once either value is known, the other can be calculated directly without repeating the full process — for 12 and 18, GCD is 6, and since 12 × 18 = 216, LCM must be 216 ÷ 6 = 36, which checks out (36 is indeed the smallest number both 12 and 18 divide into evenly).
The standard efficient method for finding GCD is the Euclidean algorithm, which repeatedly replaces the larger number with the remainder of dividing it by the smaller number until the remainder reaches zero — far faster than checking every possible common factor, especially for large numbers. Both concepts show up constantly outside pure number theory: GCD is exactly what's used to reduce a fraction to its simplest form (dividing numerator and denominator by their GCD), while LCM is what's needed to find a common denominator when adding fractions with different denominators, or to solve real-world "when do these repeating cycles line up again" problems, like figuring out when two differently-timed traffic lights or event schedules will next align.
GCD (greatest common divisor) is the largest number that divides evenly into both given numbers. LCM (least common multiple) is the smallest number that both given numbers divide evenly into. They describe opposite relationships — a shared factor versus a shared multiple.
Yes — GCD(a,b) × LCM(a,b) = a × b for any two numbers. Once you know the GCD, LCM = (a × b) ÷ GCD, avoiding the need to separately search for the least common multiple from scratch.
It's an efficient method that repeatedly replaces the larger of two numbers with the remainder of dividing it by the smaller number, continuing until the remainder reaches zero — the last nonzero remainder is the GCD. It's dramatically faster than checking every possible common factor, especially for large numbers.
GCD is used to simplify fractions to their lowest terms (dividing numerator and denominator by their GCD). LCM is used to find a common denominator when adding fractions, and to solve scheduling-style problems like determining when two repeating cycles — such as differently-timed events or signals — will next align.