GCD & LCM Calculator | Up to 10 Numbers

The Greatest Common Divisor (GCD) of two or more integers is the largest positive integer that divides all of them without remainder. The Least Common Multiple (LCM) is the smallest positive integer that is a multiple of all input values. These two numbers are fundamentally linked by the identity GCD(a,b) × LCM(a,b) = |a × b| for any two integers.

This calculator uses the Euclidean algorithm, one of the oldest known algorithms, proven by Euclid around 300 BCE, to compute GCD efficiently in O(log min(a,b)) steps. LCM is then derived from GCD using the identity above. For multiple numbers, the algorithm is applied iteratively: GCD(a, b, c) = GCD(GCD(a, b), c).

The calculator also shows prime factorization of each input, which provides an alternative verification path: the GCD uses the minimum exponent of each shared prime, and the LCM uses the maximum exponent of every prime that appears. All calculations run in the browser, no data is sent to any server.

GCD and LCM in Number Theory

The GCD and LCM are foundational to elementary number theory and have been studied for over 2,300 years. Euclid's algorithm for computing GCD appears in Book VII of the Elements (c. 300 BCE) and is one of the oldest algorithms still in active use in modern computing. Every modern programming language has a GCD function built on this algorithm.

The Euclidean Algorithm in Detail

The key insight behind the Euclidean algorithm is that GCD(a, b) = GCD(b, a mod b). This follows from the fact that any common divisor of a and b must also divide a − k×b for any integer k, so it must divide the remainder. The algorithm terminates because the remainder strictly decreases at every step, and a non-negative integer cannot decrease forever without reaching zero.

• Time complexity: O(log min(a, b)) — extremely fast even for large numbers. Computing GCD(10^18, 10^18−1) takes fewer than 90 steps.
• Binary GCD: A variant using only bit shifts and subtraction, better suited for hardware without a division instruction. Produces the same result.
• Extended Euclidean: A version that also computes Bézout coefficients (integers x, y such that ax + by = GCD(a,b)), used in modular inverse computations for cryptography.

Why LCM Uses the GCD Formula

The identity LCM(a,b) = |a×b| / GCD(a,b) avoids computing LCM directly from the definition (which would require testing all multiples). Direct computation from prime factorizations is another option but requires full factorization, slower for large numbers. The GCD-based formula runs in the same time as computing the GCD itself.

Applications in Everyday Mathematics

• Simplifying fractions: Divide numerator and denominator by GCD to reach lowest terms. The fraction calculator on this site uses exactly this method.
• Finding a common denominator: LCD = LCM of all denominators. Using LCM rather than the product of all denominators keeps numbers manageable.
• Tiling problems: The largest square tile that can cover an m×n floor without cutting = GCD(m,n) metres on a side.
• Gear and rhythm synchronization: Two gears with tooth counts a and b return to their starting relative position every LCM(a,b) teeth — equivalent to scheduling repeated events.
• Modular arithmetic: GCD determines if a linear congruence ax ≡ b (mod n) has solutions (it does iff GCD(a,n) | b).