Sprint 8 Converter + Math
Greatest Common Divisor (GCD) Finder
Euclidean algorithm.
GCD
2
How it works
The Greatest Common Divisor (GCD), also called Greatest Common Factor (GCF) or Highest Common Factor (HCF), is the largest positive integer that divides two or more integers without a remainder. The Least Common Multiple (LCM) is the smallest positive integer divisible by all given integers. These two operations are fundamental to fraction arithmetic, scheduling problems, and number theory.
**The Euclidean Algorithm (GCD)** The most efficient classical algorithm for GCD uses the property gcd(a, b) = gcd(b, a mod b). Repeat until the remainder is 0; the last non-zero remainder is the GCD. Example: gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) = 6. This runs in O(log min(a,b)) time — dramatically faster than trial division for large numbers.
**GCD–LCM relationship** LCM(a, b) = (a × b) / GCD(a, b). This relationship means computing LCM reduces to computing GCD, which is fast.
**Fraction simplification** To reduce a fraction p/q to lowest terms, divide both by GCD(p, q). 48/18 → GCD(48,18) = 6 → 8/3. This is the fundamental use case.
**Scheduling and cyclic problems** If event A repeats every 12 days and event B repeats every 18 days, when do they coincide? LCM(12, 18) = 36 days. LCM arises in any "when do cycles align?" problem — gear ratios, chemical synthesis timing, musical polyrhythms.
**Multiple inputs** For more than two numbers: GCD(a, b, c) = GCD(GCD(a, b), c). LCM extends the same way. The tool accepts any number of integers.
Privacy: all calculations run in the browser. No data is transmitted.
Frequently Asked Questions
- The Euclidean algorithm computes GCD(a, b) by repeatedly replacing (a, b) with (b, a mod b) until the remainder is 0. The last non-zero remainder is the GCD. Example: GCD(252, 105) → GCD(105, 42) → GCD(42, 21) → GCD(21, 0) = 21. It's fast because each step reduces the larger number by at least half (in terms of bits), giving O(log min(a,b)) steps. This makes it efficient even for numbers with hundreds of digits.
- GCD tells you the exact factor by which to simplify a fraction. For p/q: divide both by GCD(p,q) to get the simplest form. Example: 84/126 → GCD(84,126) = 42 → 2/3. GCD(p,q) = 1 means the fraction is already in lowest terms (p and q are coprime — they share no common factor). Coprime numbers appear frequently in number theory: consecutive integers are always coprime; prime numbers are coprime to every number they don't divide.
- Yes — GCD is associative: GCD(a, b, c) = GCD(GCD(a, b), c). Compute pairwise. Example: GCD(12, 18, 24) → GCD(12, 18) = 6, then GCD(6, 24) = 6. The result is the largest integer that divides all inputs simultaneously. For three fractions with different denominators (e.g., 1/12 + 1/18 + 1/24), the LCD = LCM(12, 18, 24) = 72, and LCM = (product) / GCD for two at a time.
- Two integers are coprime (relatively prime) when their GCD is 1 — they share no prime factors. Examples: 8 and 9 (GCD=1), 25 and 36 (GCD=1). Consecutive integers are always coprime. Coprimality appears in: Chinese Remainder Theorem (solving simultaneous congruences); RSA encryption (public exponent e must be coprime to φ(n)); gear design (gears with coprime tooth counts mesh every tooth before repeating, ensuring even wear); and fraction addition (coprime denominators produce fractions already in lowest terms).