GCD & LCM
The Greatest Common Divisor (GCD) and Least Common Multiple (LCM) are foundational number-theory tools with direct applications in fraction simplification, scheduling problems, modular arithmetic, and competitive programming. The Euclidean algorithm computes GCD in O(log(min(a,b))) — deceptively fast.
What Is GCD?
The GCD of two integers a and b is the largest integer that divides both without a remainder. gcd(12, 8) = 4 because 4 divides both, and no number larger than 4 does.
Key properties:
gcd(a, 0) = a — zero is divisible by everything
gcd(a, b) = gcd(b, a mod b) — the Euclidean identity
gcd(a, b) = gcd(b, a) — commutative
gcd(a, b) divides both a and b, and any linear combination ma + nb
Euclidean Algorithm
The Euclidean algorithm exploits the identity gcd(a, b) = gcd(b, a mod b) recursively until the remainder is 0. At that point the non-zero value is the GCD. Each step reduces the problem size by at least half, giving O(log min(a,b)) time.
// Recursive Euclidean GCD
function gcd(a: number, b: number): number {
return b === 0 ? a : gcd(b, a % b);
}
// Iterative (avoids call stack for very large inputs)
function gcdIterative(a: number, b: number): number {
while (b !== 0) {
[a, b] = [b, a % b];
}
return a;
}
// Trace: gcd(48, 18)
// gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) → 6
console.log(gcd(48, 18)); // 6
console.log(gcd(100, 75)); // 25
console.log(gcd(17, 13)); // 1 (coprime)LCM from GCD
The LCM is the smallest positive integer divisible by both a and b. The relationship between GCD and LCM is: lcm(a, b) = (a / gcd(a, b)) * b.
We divide first (not multiply then divide) to avoid overflow when a * b exceeds the safe integer range.
function lcm(a: number, b: number): number {
return (a / gcd(a, b)) * b; // divide first to reduce overflow risk
}
console.log(lcm(4, 6)); // 12
console.log(lcm(12, 18)); // 36
console.log(lcm(7, 5)); // 35
// Why LCM = a*b / gcd(a,b)?
// Every integer = product of prime powers.
// GCD keeps the MIN power of each prime.
// LCM keeps the MAX power of each prime.
// MAX(p) + MIN(p) = count_in_a(p) + count_in_b(p)
// → gcd * lcm = a * bGCD and LCM of an Array
// GCD/LCM are both associative — fold over the array
function arrayGcd(nums: number[]): number {
return nums.reduce((acc, n) => gcd(acc, n));
}
function arrayLcm(nums: number[]): number {
return nums.reduce((acc, n) => lcm(acc, n));
}
console.log(arrayGcd([12, 18, 24])); // 6
console.log(arrayLcm([4, 6, 10])); // 60
// Application: find if all elements in a range share a common factor
// If arrayGcd(arr) > 1, all elements are divisible by that factorExtended Euclidean Algorithm
The extended Euclidean algorithm finds not just gcd(a, b) but also integers x and y such that:
ax + by = gcd(a, b) — this is Bezout's identity.
These coefficients x, y are called Bezout coefficients and are used to compute the modular inverse.
// Returns [gcd, x, y] such that a*x + b*y = gcd
function extendedGcd(a: number, b: number): [number, number, number] {
if (b === 0) return [a, 1, 0];
const [g, x1, y1] = extendedGcd(b, a % b);
return [g, y1, x1 - Math.floor(a / b) * y1];
}
// Example: gcd(35, 15) = 5
// 35*1 + 15*(-2) = 35 - 30 = 5 ✓
const [g, x, y] = extendedGcd(35, 15);
console.log(g, x, y); // 5 1 -2
console.log(35 * x + 15 * y); // 5Modular Inverse via Extended GCD
The modular inverse of a modulo m is a number x such that ax ≡ 1 (mod m). It exists only when gcd(a, m) = 1 (a and m are coprime).
From Bezout's identity: ax + my = 1 → ax ≡ 1 (mod m) → x is the inverse.
function modInverse(a: number, m: number): number {
const [g, x] = extendedGcd(a, m);
if (g !== 1) throw new Error(`${a} has no inverse mod ${m} (not coprime)`);
return ((x % m) + m) % m; // ensure positive result
}
// 3 * x ≡ 1 (mod 7) → x = 5 (because 3*5 = 15 = 2*7 + 1)
console.log(modInverse(3, 7)); // 5
console.log((3 * 5) % 7); // 1 ✓
// Used in nCr mod prime when prime is NOT 2^k + 1 (Fermat's theorem doesn't apply)
// In that case use extended GCD inverse instead of fast powerFraction Simplification
// Simplify a fraction a/b to lowest terms
function simplifyFraction(a: number, b: number): [number, number] {
const g = gcd(Math.abs(a), Math.abs(b));
return [a / g, b / g];
}
console.log(simplifyFraction(12, 18)); // [2, 3]
console.log(simplifyFraction(7, 14)); // [1, 2]
console.log(simplifyFraction(100, 75)); // [4, 3]
// Add two fractions
function addFractions(a: number, b: number, c: number, d: number): [number, number] {
// a/b + c/d = (a*d + c*b) / (b*d)
return simplifyFraction(a * d + c * b, b * d);
}
console.log(addFractions(1, 2, 1, 3)); // [5, 6]Scheduling Application — LCM
LCM models periodic scheduling: if task A repeats every 4 days and task B every 6 days, they next coincide after lcm(4, 6) = 12 days. The same idea appears in problems about gear ratios, blinking lights, and bus timetables.
// When do two buses running every a and b minutes next meet at the stop together?
function nextMeeting(a: number, b: number): number {
return lcm(a, b);
}
// Three events repeating every 3, 4, and 5 minutes — when do all three coincide?
console.log(nextMeeting(3, 4)); // 12 minutes
console.log(arrayLcm([3, 4, 5])); // 60 minutes
// LCM in string repetition: "abcabc..." and "ababab..." first align after lcm(3,2)=6 charsQuick Reference
Formula | Use case |
|---|---|
gcd(a,b) = gcd(b, a%b) | Core Euclidean identity — base of everything |
lcm(a,b) = (a/gcd(a,b))*b | Smallest common multiple, scheduling |
gcdlcm = ab | Convert between GCD and LCM |
ax + by = gcd(a,b) | Bezout's identity — extended GCD |
x = (extGcd(a,m)[1] % m + m) % m | Modular inverse when gcd(a,m)=1 |