LCM and GCD Calculator

Background.

The Quanta LCM and GCD calculator takes two positive integers a and b — each up to one billion — and returns the five quantities you actually need: the greatest common divisor gcd(a, b), the least common multiple lcm(a, b), the two reduced quotients a/gcd and b/gcd, and a coprimality flag that is 1 when gcd(a, b) = 1 and 0 otherwise. Enter 12 and 18 and the calculator returns gcd = 6, lcm = 36, a/gcd = 2, b/gcd = 3, and coprime = 0 — because 6 is the largest integer dividing both 12 and 18, 36 is the first integer divisible by both, and the reduced fraction 12/18 collapses to 2/3, which is in lowest terms. The greatest common divisor is also known as the highest common factor (HCF) in British curricula and the greatest common factor (GCF) in American school texts; all three names denote exactly the same quantity.

The algorithm underneath is the oldest non-trivial algorithm in recorded mathematics. Euclid wrote it down as Proposition VII.2 of the Elements around 300 BCE — 'given two numbers not prime to one another, to find their greatest common measure' — and the procedure he describes (repeatedly subtract the smaller from the larger until one of them is zero, the other is the gcd) is in every essential respect the algorithm modern computers still run, with the single optimisation that we replace iterated subtraction by a single Euclidean division: gcd(a, b) = gcd(b, a mod b). Donald Knuth, in Volume 2 of The Art of Computer Programming, calls Euclid's algorithm 'the granddaddy of all algorithms, because it is the oldest non-trivial algorithm that has survived to the present day.' The algorithm is also astonishingly fast. Lamé proved in 1844 that the number of division steps required is at most five times the number of decimal digits of min(a, b) — the worst case is reached when a and b are consecutive Fibonacci numbers — so gcd(10⁹, 10⁹ − 1) terminates in fewer than 50 division steps regardless of how the two inputs were generated, which on modern hardware is well under a microsecond.

Once you have the gcd, the lcm comes essentially for free thanks to the identity gcd(a, b) · lcm(a, b) = a · b, valid for any pair of positive integers. The calculator computes lcm as (a / gcd) · b rather than (a · b) / gcd to avoid intermediate overflow when a and b are both large — at the upper end of our range a · b would exceed 2⁵⁹, beyond the safe integer range in IEEE 754 double-precision floating point.

The two quantities lcm and gcd are the cornerstones of an enormous amount of elementary and not-so-elementary mathematics. They are the right tool for adding fractions (the natural common denominator is lcm), for reducing fractions to lowest terms (divide both numerator and denominator by gcd), for solving scheduling problems (two events that repeat every a and b days respectively coincide every lcm(a, b) days), for finding the period of repeating decimals, for Chinese-remainder-style modular arithmetic (which works cleanly precisely when the moduli are pairwise coprime), for analysing the structure of cyclic groups, for the orbit-counting theorems of combinatorics, and for the multiplicativity of every classical arithmetic function — d(n), σ(n), φ(n), μ(n) — over coprime arguments.

They are also the gateway to Bezout's identity: for any pair of positive integers a, b there exist integers x and y, computable by running the Euclidean algorithm in reverse, such that ax + by = gcd(a, b). The extended Euclidean algorithm that produces those Bezout coefficients is how you compute multiplicative inverses modulo n, which is how RSA encryption recovers the private exponent d from the public exponent e and the totient φ(n), which is how every TLS handshake on the open web is bootstrapped.

This page covers all of that: how the Euclidean algorithm works in detail, why the gcd · lcm identity is true, how to compute either quantity by hand using prime factorization (and why that method is exponentially slower than Euclid's for large inputs), what coprimality means, where Bezout's identity comes from and what it lets you do, and worked examples from elementary fraction arithmetic up to a billion-scale gcd. Whether you are simplifying fractions for a homework problem, lining up cogs on a bicycle gear, scheduling two cron jobs, debugging modular arithmetic, or refreshing your memory before a competitive-programming round, the calculator above and the explainer below cover every variant of the question.

What is lcm and gcd calculator?

The greatest common divisor gcd(a, b) of two positive integers a and b is the largest positive integer d such that d divides a and d divides b. Equivalently, gcd(a, b) is the unique positive generator of the additive subgroup {ax + by : x, y ∈ ℤ} of the integers — a fact known as Bezout's identity. The least common multiple lcm(a, b) is the smallest positive integer m such that a divides m and b divides m. Both quantities are well-defined and finite for any two positive integers, and both are symmetric — gcd(a, b) = gcd(b, a) and lcm(a, b) = lcm(b, a). The fundamental identity linking them is gcd(a, b) · lcm(a, b) = a · b, which is the multiplicative reformulation of unique prime factorization (Fundamental Theorem of Arithmetic): if a = ∏ p_i^{α_i} and b = ∏ p_i^{β_i} are the canonical factorizations using the same indexed set of primes (some exponents possibly zero), then gcd(a, b) = ∏ p_i^{min(α_i, β_i)} and lcm(a, b) = ∏ p_i^{max(α_i, β_i)}, and min + max = α + β so the exponent of every prime on both sides of the identity matches. Two integers are coprime (also called relatively prime or mutually prime) when gcd(a, b) = 1, equivalently when they share no prime factor in common, equivalently when lcm(a, b) = a · b. Coprimality is the precondition for the Chinese Remainder Theorem (which gives a bijection ℤ/abℤ ≅ ℤ/aℤ × ℤ/bℤ when gcd(a, b) = 1), for the existence of multiplicative inverses modulo n (an integer x is invertible mod n iff gcd(x, n) = 1, by Bezout), and for the multiplicativity of arithmetic functions like Euler's totient φ: φ(mn) = φ(m) φ(n) holds when gcd(m, n) = 1 but fails in general. Bezout's identity states that gcd(a, b) is the smallest positive integer expressible as ax + by for integer coefficients x, y, and the extended Euclidean algorithm — a back-substitution of Euclid's reductions — produces such an x and y in the same O(log min(a, b)) steps that compute the gcd itself.

How to use this calculator.

1. 01Enter your two positive integers a and b in the two input fields. Each can be any whole number from 1 to one billion. The order does not matter — gcd and lcm are symmetric — but both fields must be filled.
2. 02Read the primary result, the greatest common divisor gcd(a, b), at the top of the results panel. This is the largest integer dividing both a and b. For a = 12 and b = 18 the gcd is 6; for two coprime inputs (say a = 14 and b = 15) the gcd is 1.
3. 03Read the least common multiple lcm(a, b) in the breakdown. This is the smallest integer that both a and b divide. For a = 12 and b = 18 the lcm is 36. Use this as the natural common denominator when adding fractions: 1/12 + 1/18 = 3/36 + 2/36 = 5/36.
4. 04Read the reduced quotients a/gcd and b/gcd in the breakdown. These are the numerator and denominator of the fraction a/b when written in lowest terms. For 12/18 the reduced quotients are 2 and 3, so the simplified fraction is 2/3.
5. 05Check the coprime flag. It returns 1 if gcd(a, b) = 1 and 0 otherwise. Coprime inputs satisfy the most useful identity in number theory — lcm = a · b — and are the precondition for the Chinese Remainder Theorem and for the existence of modular inverses.
6. 06For more than two inputs, the gcd and lcm extend associatively: gcd(a, b, c) = gcd(gcd(a, b), c) and similarly for lcm. Run the calculator pairwise — first gcd(a, b), then gcd of that result with c — to handle three or more numbers.

The formula.

The calculator runs the classical Euclidean algorithm. Given positive integers a and b with a ≥ b (and a swap step if not), it iterates the recurrence (a, b) ← (b, a mod b) until b reaches zero; the value of a at that point is gcd(a, b). The correctness argument is two lines. First, every common divisor of a and b is a common divisor of b and a mod b, because a mod b = a − ⌊a/b⌋ · b is an integer linear combination of a and b. Conversely every common divisor of b and a mod b also divides a = ⌊a/b⌋ · b + (a mod b). Therefore the set of common divisors is invariant under the recurrence, and in particular the greatest common divisor is. Second, the recurrence strictly decreases the second argument (0 ≤ a mod b < b), so it must terminate, and when it terminates with b = 0 the gcd is just a, since gcd(a, 0) = a for any a > 0. Lamé's theorem (1844) bounds the number of steps: if b has n decimal digits, the algorithm takes at most 5n divisions. The worst case is realised when a and b are consecutive Fibonacci numbers F_{k+1} and F_k, because in that case each Euclidean step produces the next pair of consecutive Fibonacci numbers in the sequence — gcd(F_{k+1}, F_k) = gcd(F_k, F_{k-1}) = … — and the Fibonacci numbers grow at the slowest possible exponential rate consistent with the recurrence. For inputs up to 10⁹ this means at most about 45 division steps, well under a microsecond. Once gcd is known, the lcm is computed via the identity gcd(a, b) · lcm(a, b) = a · b, rearranged as lcm = (a / gcd) · b to keep all intermediate values within the safe integer range (a · b alone could exceed 2⁵³ ≈ 9 × 10¹⁵ when both inputs approach 10⁹, but a/gcd is always at most a ≤ 10⁹ and the final product is at most 10¹⁸ which is fine for BigInt arithmetic but more comfortably handled this way for IEEE-754 doubles). The two derived quotients a/gcd and b/gcd are emitted as direct outputs because they are the most-asked-for downstream quantity — the numerator and denominator of the reduced fraction a/b — and the coprime flag is a single equality check against 1. Note one important convention: the calculator rejects inputs of 0 even though gcd(0, n) = n and lcm(0, n) = 0 are mathematically well-defined; rejecting 0 keeps the a/gcd and b/gcd outputs well-defined and avoids the degenerate lcm = 0 case that breaks every downstream use (you cannot use 0 as a common multiple for fraction addition or for scheduling).

A worked example.

Frequently asked questions.

References& sources.

1. [1]Euclid. Elements, Book VII, Propositions 1–2 (c. 300 BCE). Proposition 1 gives the algorithm for two numbers that turn out to be coprime ('two unequal numbers being set out, and the less being continually subtracted in turn from the greater, if the number which is left never measures the one before it until a unit is left, the original numbers will be prime to one another'); Proposition 2 gives the algorithm for the general case ('given two numbers not prime to one another, to find their greatest common measure'). English translation in Heath, T. L. The Thirteen Books of Euclid's Elements, Cambridge University Press, 1908; reprinted by Dover, 1956. Online edition by David E. Joyce at Clark University.
2. [2]Knuth, Donald E. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd edition. Addison-Wesley, 1997. §4.5.2 ('The Greatest Common Divisor') gives the definitive computer-science treatment of the Euclidean algorithm, the binary GCD algorithm (Stein 1967), Lehmer's variant, and the extended Euclidean algorithm. §4.5.3 analyses the running time in detail and proves Lamé's bound. Knuth's much-quoted remark that Euclid's is 'the granddaddy of all algorithms, because it is the oldest non-trivial algorithm that has survived to the present day' appears at the head of §4.5.2.
3. [3]Hardy, G. H. and Wright, E. M. An Introduction to the Theory of Numbers, 6th edition, revised by Heath-Brown and Silverman. Oxford University Press, 2008. Chapter II ('The Series of Primes') and Chapter V ('Congruences and Residues') develop the gcd, lcm, Euclid's lemma, the Fundamental Theorem of Arithmetic, Bezout's identity, and the Chinese Remainder Theorem from first principles. The canonical British undergraduate text on elementary number theory.
4. [4]NIST Digital Library of Mathematical Functions, Chapter 27 ('Functions of Number Theory'), by T. M. Apostol. §27.1 defines gcd and lcm and states the multiplicative identity gcd(a, b) · lcm(a, b) = ab; §27.14 covers the Euclidean algorithm and Bezout's identity. Online edition continuously updated by NIST.
5. [5]Weisstein, Eric W. 'Greatest Common Divisor' and 'Least Common Multiple', MathWorld — A Wolfram Web Resource. Comprehensive reference entries with the standard identities, links to related functions (Jacobi symbol, Möbius function, Euler's totient), and explicit worked examples of the Euclidean and extended Euclidean algorithms.
6. [6]Lamé, Gabriel. 'Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers.' Comptes Rendus de l'Académie des Sciences 19: 867–870, 1844. The first proof that the Euclidean algorithm runs in O(log min(a, b)) steps, with the Fibonacci numbers identified as the worst case — historically the first non-trivial worst-case analysis of an algorithm in mathematics.
7. [7]Shoup, Victor. A Computational Introduction to Number Theory and Algebra, 2nd edition. Cambridge University Press, 2009. Chapter 4 develops the Euclidean and extended Euclidean algorithms, Bezout's identity, modular inverses, and the Chinese Remainder Theorem with full algorithmic detail. Freely available from the author's website.