GCD & LCM Calculator
Table of Contents
What Are GCD and LCM
Greatest Common Divisor (GCD)
The Greatest Common Divisor (GCD), also known as the Highest Common Factor (HCF), is the largest positive integer that divides two or more integers without leaving a remainder. For example, gcd(12, 18) = 6, because 6 is the largest integer that divides both 12 and 18.
Formal definition: For integers a and b (not both zero), gcd(a, b) = max{d ∈ Z+ : d | a and d | b}.
Least Common Multiple (LCM)
The Least Common Multiple (LCM) is the smallest positive integer that is divisible by two or more given integers. For example, lcm(4, 6) = 12, because 12 is the smallest positive integer divisible by both 4 and 6.
Formal definition: For positive integers a and b, lcm(a, b) = min{m ∈ Z+ : a | m and b | m}.
Why Do GCD and LCM Matter?
GCD and LCM are fundamental building blocks of number theory. From simplifying fractions to the RSA encryption algorithm, from musical rhythms to planetary orbits, they appear everywhere. The Euclidean algorithm (c. 300 BC) is the oldest non-trivial algorithm still in active use, and remains a core tool in computer science today.
Euclidean Algorithm
History
The Euclidean algorithm appears in Euclid's Elements, Book VII, Propositions 1-2, dating to approximately 300 BC. It is the oldest known non-trivial algorithm still in active use today, predating even the Sieve of Eratosthenes by about half a century.
How It Works
Core recurrence:
Repeatedly replace the larger number with the remainder of dividing the two numbers, until the remainder becomes 0. The other number at that point is the GCD.
Why Does It Work?
Proof: gcd(a, b) = gcd(b, a mod b)
Let d = gcd(a, b). Let a = bq + r (where r = a mod b).
1. Since d | a and d | b, we have d | (a − bq) = r. So d is a common divisor of b and r.
2. Conversely, let d' be any common divisor of b and r. Then d' | (bq + r) = a. So d' is also a common divisor of a and b, hence d' ≤ d.
3. Combining 1 and 2, gcd(a, b) = gcd(b, r) = gcd(b, a mod b). ◼
Key insight: If d divides both a and b, then d also divides a − b, and therefore d divides a mod b. The set of common divisors is preserved under the modulo operation.
Time Complexity
O(log(min(a, b))). This result was proven by Gabriel Lamé in 1844, making it one of the earliest results in computational complexity theory.
Lamé's Theorem: The number of steps in the Euclidean algorithm for two numbers a ≥ b > 0 never exceeds 5 times the number of decimal digits of b.
Why? The worst case occurs for consecutive Fibonacci numbers. Since Fn ≈ φn/√5 (where φ = (1+√5)/2), the number of steps is approximately logφ b ≈ 2.078 × log10 b, bounded above by 5 × log10 b.
Code Implementations
Python:
JavaScript:
Worked Example: gcd(252, 198)
Extended Euclidean Algorithm
Bรฉzout's Identity
Formally stated by French mathematician รtienne Bรฉzout in 1779:
Bรฉzout's Theorem
For any integers a and b (not both zero), there exist integers x and y such that ax + by = gcd(a, b). The coefficients x and y are called Bรฉzout coefficients.
The extended Euclidean algorithm computes not only gcd(a, b) but also finds the coefficients x and y satisfying Bรฉzout's identity.
Why Does the Extended Euclidean Algorithm Matter?
The extended Euclidean algorithm is the standard method for computing modular inverses. If gcd(a, m) = 1 (i.e., a and m are coprime), then ax + my = 1, which means ax ≡ 1 (mod m), i.e., x is the modular inverse of a modulo m. This is a core step in the RSA encryption algorithm.
Algorithm
JavaScript:
Worked Example: Find x, y for 252x + 198y = gcd(252, 198)
LCM from GCD
The Formula
lcm(a, b) = |a × b| / gcd(a, b)
Why Does This Formula Work?
Intuition from prime factorization:
Let a = p1a1 × p2a2 × ... and b = p1b1 × p2b2 × ...
GCD takes the minimum exponent of each prime: gcd(a,b) = ∏ pimin(ai, bi)
LCM takes the maximum exponent of each prime: lcm(a,b) = ∏ pimax(ai, bi)
Since for any two numbers min(x,y) + max(x,y) = x + y, we get:
gcd(a,b) × lcm(a,b) = ∏ pimin(ai,bi) + max(ai,bi) = ∏ piai + bi = a × b ◼
Why Compute LCM via GCD?
Directly computing a × b can cause integer overflow. But if you divide by gcd first, i.e., lcm = (a / gcd) × b, the intermediate value is smaller and less likely to overflow. For example, with 32-bit integers, a = 2×109, b = 3×109, a × b overflows, but a / gcd(a,b) may be quite small.
Example
Properties & Theorems
Fundamental Properties
| Property | Formula | Explanation |
|---|---|---|
| Commutativity | gcd(a, b) = gcd(b, a) | Order does not matter |
| Associativity | gcd(a, gcd(b, c)) = gcd(gcd(a, b), c) | Extends to any number of inputs |
| Idempotence | gcd(a, a) = a | GCD of a number with itself is itself |
| Absorbing element | gcd(a, 0) = a | Every integer divides 0 |
| Identity | gcd(a, 1) = 1 | 1 is coprime to everything |
| Product relation | gcd(a,b) × lcm(a,b) = a × b | The central link between GCD and LCM |
GCD and LCM Are Both Commutative and Associative
Why is GCD associative?
gcd(a, gcd(b, c)) is the largest integer dividing all three of a, b, and c. Regardless of whether you first combine b and c or a and b, the set "the largest integer dividing all three numbers" is uniquely determined and does not depend on computation order. ◼
Distributive Law
Distributive law: gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c))
Why? GCD and LCM correspond to the min and max operations on prime factor exponents. min and max satisfy distributivity: min(a, max(b, c)) = max(min(a, b), min(a, c)), which can be verified by checking the three cases a ≤ b, b < a ≤ c, and c < a.
Important Properties When Coprime
If gcd(a, b) = 1 (i.e., a and b are coprime), then:
- lcm(a, b) = a × b
- There exist integers x, y such that ax + by = 1 (special case of Bรฉzout's theorem, i.e., modular inverse exists)
- If a | c and b | c, then ab | c
- If a | bc, then a | c (Euclid's lemma)
Applications
1. Simplifying Fractions
To reduce a fraction a/b to lowest terms: divide both numerator and denominator by gcd(a, b). For example, 48/36 with gcd(48, 36) = 12 gives 48/36 = 4/3. This is the most direct application of GCD in elementary mathematics.
2. Finding Common Denominators
To add fractions a/b and c/d, find the least common denominator lcm(b, d). For example, 1/4 + 1/6 requires lcm(4, 6) = 12, so 1/4 + 1/6 = 3/12 + 2/12 = 5/12.
3. Scheduling and Periodicity โ The Core LCM Scenario
Why LCM? When two periodic events repeat with periods a and b, they next coincide at time lcm(a, b).
- Traffic lights: If one intersection has a 60-second red cycle and another has 90 seconds, they synchronize every lcm(60, 90) = 180 seconds = 3 minutes.
- Planetary conjunction: Mars orbits in 687 days, Earth in 365 days; the synodic period relates to LCM.
- Work scheduling: Employee A has a day off every 3 days, Employee B every 5 days; they both have the same day off every lcm(3, 5) = 15 days.
4. Cryptography: Modular Inverse in RSA
Core steps of RSA public-key encryption:
- Choose two large primes p and q, compute n = p × q
- Compute λ(n) = lcm(p−1, q−1) (Carmichael's totient function)
- Choose public key e, use the extended Euclidean algorithm to find d ≡ e−1 (mod λ(n))
Without efficient GCD/extended GCD algorithms, modern public-key cryptography would be impossible. See Prime Factorization Calculator.
5. Music: Polyrhythms
Why LCM? When one voice plays in a cycle of 3 beats and another in 4 beats (a 3:4 polyrhythm), the two rhythms realign every lcm(3, 4) = 12 beats. This is why a 3-against-4 polyrhythm loops every 12 beats. This principle is fundamental to West African drumming and Indian tabla playing.
6. Tiling
To tile a floor with a × b tiles into a perfect square, the minimum square side length is lcm(a, b). For example, 3cm × 5cm tiles require a 15cm × 15cm square to tile perfectly.
Multiple Numbers
Because GCD and LCM are both associative, they extend naturally to multiple numbers:
For n numbers, simply compute pairwise from left to right:
JavaScript:
Caveats
- The LCM of multiple numbers can grow extremely fast (exponentially). For example, the LCM of the first 20 primes exceeds 1022.
- For large sets of numbers, sorting first or using a divide-and-conquer strategy can optimize computation.
- In programming, beware of intermediate overflow โ always use (a / gcd) * b rather than a * b / gcd.
FAQ
1. What is the difference between GCD and HCF?
There is none. GCD (Greatest Common Divisor) and HCF (Highest Common Factor) are different names for exactly the same concept. American mathematics textbooks typically use GCD, while British textbooks prefer HCF.
2. What is gcd(0, 0)?
By convention, gcd(0, 0) = 0. While literally "the largest integer dividing both 0 and 0" is undefined (every positive integer divides 0, so the set of common divisors has no maximum), defining gcd(0, 0) = 0 preserves the clean algebraic property that gcd(a, 0) = a for all non-negative integers a.
3. How do you compute GCD of negative numbers?
GCD is conventionally defined as a positive integer. gcd(−12, 18) = gcd(12, 18) = 6. Simply take absolute values: gcd(a, b) = gcd(|a|, |b|).
4. How much faster is the Euclidean algorithm than prime factorization?
Much faster. The Euclidean algorithm runs in O(log n) time, while general prime factorization (trial division) takes O(√n). For a 100-digit number, the Euclidean algorithm needs only a few hundred steps, while factoring is practically impossible with current computing power โ this is exactly the security basis of RSA encryption.
5. How large a number can the calculator handle?
This page's calculator uses JavaScript's native number type, with a safe integer range of ±253−1 (approximately 9 × 1015). Numbers beyond this range may produce precision errors. For larger numbers, use Python's built-in math.gcd() (Python supports arbitrary-precision integers).