Everyday Life · General Mathematics
LCM and GCD Calculator
Calculates the Least Common Multiple (LCM) and Greatest Common Divisor (GCD) of two integers using the Euclidean algorithm.
Calculator
Formula
a and b are the two positive integers. gcd(a, b) is found by repeatedly replacing (a, b) with (b, a mod b) until the remainder is zero — the last non-zero remainder is the GCD. The LCM is then derived by dividing the absolute product of a and b by their GCD, avoiding any double-counting of shared prime factors.
Source: Euclid, Elements Book VII (c. 300 BCE); confirmed in Knuth, The Art of Computer Programming Vol. 2, §4.5.2.
How it works
The Greatest Common Divisor (GCD) — also called the Highest Common Factor (HCF) — of two integers is the largest positive integer that divides both numbers without leaving a remainder. For example, the GCD of 48 and 36 is 12, because 12 is the largest number that goes into both evenly. The GCD is foundational in simplifying fractions: to reduce 36/48 to its lowest terms, you divide both numerator and denominator by their GCD of 12, giving 3/4.
The Least Common Multiple (LCM) is the smallest positive integer that is divisible by both numbers. For 4 and 6, multiples of 4 are 4, 8, 12, 16 … and multiples of 6 are 6, 12, 18 … so the LCM is 12. The LCM is essential when adding or subtracting fractions with different denominators — you need the LCM as the common denominator. It is also used in scheduling: if event A repeats every 4 days and event B every 6 days, they next coincide in 12 days. This calculator uses two well-known results: the Euclidean algorithm for GCD, which repeatedly applies the modulo operation (a mod b) until the remainder is zero; and the identity lcm(a, b) = |a × b| / gcd(a, b), which derives the LCM directly from the GCD.
The Euclidean algorithm is one of the oldest known algorithms, described by Euclid around 300 BCE, and it remains highly efficient for modern computing. It runs in O(log min(a, b)) steps, meaning even very large numbers are resolved in microseconds. Practical applications appear in cryptography (RSA key generation relies on GCD), music theory (finding rhythmic cycles), gear design (meshing teeth counts), and software engineering (memory alignment and buffer sizing).
Worked example
Suppose you want to add the fractions 5/12 and 7/18. You need a common denominator, which is the LCM of 12 and 18.
Step 1 — Find the GCD using the Euclidean algorithm:
gcd(18, 12): 18 mod 12 = 6 → gcd(12, 6): 12 mod 6 = 0 → GCD = 6
Step 2 — Find the LCM:
lcm(12, 18) = (12 × 18) / 6 = 216 / 6 = 36
Step 3 — Add the fractions:
5/12 = 15/36 and 7/18 = 14/36
15/36 + 14/36 = 29/36
Another example: a bus on Route A departs every 8 minutes and a bus on Route B departs every 14 minutes. Both depart together at 9:00 AM. When is the next simultaneous departure?
gcd(8, 14): 14 mod 8 = 6 → 8 mod 6 = 2 → 6 mod 2 = 0 → GCD = 2
lcm(8, 14) = (8 × 14) / 2 = 112 / 2 = 56 minutes
The buses next depart together at 9:56 AM.
Limitations & notes
This calculator is designed for positive integers only. Entering zero for both inputs is undefined (GCD is indeterminate); entering zero for one input returns the other number as GCD and 0 as LCM, which follows the standard mathematical convention. Decimal or fractional inputs are rounded to the nearest integer before calculation — if you need GCD of rational numbers, convert to integers first (e.g., gcd(0.5, 0.75) can be reframed as gcd(2, 3) after multiplying by 4). Negative integers are handled by taking absolute values, consistent with the standard definition. For three or more numbers, apply the formula iteratively: gcd(a, b, c) = gcd(gcd(a, b), c) — this calculator handles only two values at once. Very large integers (beyond JavaScript's safe integer range of 2^53 − 1, approximately 9 quadrillion) may produce inaccurate results due to floating-point precision limits.
Frequently asked questions
What is the difference between GCD and LCM?
The GCD (Greatest Common Divisor) is the largest number that divides both integers exactly, useful for simplifying fractions. The LCM (Least Common Multiple) is the smallest number that both integers divide into exactly, useful for finding common denominators. For 12 and 18, GCD = 6 and LCM = 36.
How does the Euclidean algorithm find the GCD?
The Euclidean algorithm works by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller. For gcd(48, 18): 48 mod 18 = 12, then 18 mod 12 = 6, then 12 mod 6 = 0 — so GCD is 6. It stops when the remainder reaches zero, and the last non-zero remainder is the GCD.
Can the GCD or LCM be used with more than two numbers?
Yes. Apply the operation iteratively: gcd(a, b, c) = gcd(gcd(a, b), c). For example, gcd(12, 18, 24) = gcd(gcd(12, 18), 24) = gcd(6, 24) = 6. The same principle applies to LCM. This calculator computes results for two numbers at a time, so run it in sequence for three or more.
What is the relationship between GCD, LCM, and prime factorisation?
The GCD consists of the shared prime factors raised to their minimum powers, while the LCM consists of all prime factors raised to their maximum powers. For 12 = 2² × 3 and 18 = 2 × 3², GCD = 2¹ × 3¹ = 6 and LCM = 2² × 3² = 36. This is why GCD × LCM always equals |a × b|.
Why is GCD important in cryptography?
In RSA encryption, two large prime numbers p and q are chosen, and the public exponent e must satisfy gcd(e, (p−1)(q−1)) = 1, meaning e and the totient are coprime. The Extended Euclidean Algorithm is also used to compute the private key exponent d. Without efficient GCD computation, modern public-key cryptography would not be practical.
Last updated: 2025-01-15 · Formula verified against primary sources.