GCD & LCM Calculator
Find the greatest common divisor and least common multiple of two integers or a whole list — with Euclid’s algorithm step by step, prime factorisations, a coprimality test and Bézout’s identity.
Written by Suhaib Hassan. The algorithms are Euclid’s, and every worked example is re-derived by hand. Our methodology.
It runs Euclid’s division algorithm on arbitrary-size integers, then gets the LCM from gcd(a, b) · lcm(a, b) = |a · b| and the Bézout coefficients from the extended algorithm.
It shows both the fast route (Euclid) and the intuitive one (shared prime factors) side by side, so the two can be checked against each other.
—
Shared and separate prime factors
The overlap multiplies to the GCD; everything together multiplies to the LCM.
Euclid’s algorithm
—
| Step | Division | Quotient | Remainder |
|---|
Step-by-step working
—
Identities to remember
Key results about greatest common divisors and least common multiples.
| Identity | Statement | Note |
|---|---|---|
| Euclidean algorithm | gcd(a, b) = gcd(b, a mod b) | At most about 5 × the number of digits of the smaller number of steps |
| Bézout’s identity | ax + by = gcd(a, b) | Solutions x, y always exist over the integers |
| Product duality | gcd(a, b) · lcm(a, b) = |a · b| | Holds for two numbers, not three or more |
| Prime exponents | min(eₐ, e_b) for gcd, max for lcm | Compare exponents of each prime |
| Associativity | gcd(a, b, c) = gcd(gcd(a, b), c) | Reduce a list pair by pair |
| Coprime | gcd(a, b) = 1 | No shared prime factor |
Worked examples
Tiling a floor
What is the largest square tile that exactly covers a 12 × 18 floor?
Tiles are 6 × 6, and (12 ÷ 6) × (18 ÷ 6) = 6 tiles
Bus timetable
Two routes leave a station every 12 and every 18 minutes. When do they leave together again?
Gear teeth
Gears with 19 and 30 teeth are coprime. How long before the same teeth meet again?
lcm = 19 × 30 = 570 teeth — every tooth meets every other tooth, spreading wear evenly
What are the GCD and LCM?
The greatest common divisor (GCD, also called highest common factor) of two integers is the largest integer that divides both. The least common multiple (LCM) is the smallest positive integer that both divide. They are used to simplify fractions, to add fractions (the LCM of denominators), and to synchronise repeating cycles.
Two methods
- Prime factorisation: write each number as a product of primes. The GCD takes the smallest exponent of each shared prime; the LCM takes the largest exponent of every prime present.
- Euclid’s algorithm: repeatedly replace (a, b) by (b, a mod b) until the remainder is 0; the last non-zero remainder is the GCD. It is far faster for large numbers, because it never needs to factorise.
By Suhaib Hassan · Reviewed 28 September 2026 · How CalculatePilot verifies formulas →
Sources
- Euclid, Elements, Book VII, Propositions 1–2, and Book X — the Euclidean division algorithm.
- Gauss, C. F. (1801). Disquisitiones Arithmeticae. Leipzig — unique prime factorisation.
- Knuth, D. E. (1997). The Art of Computer Programming, Vol. 2, 3rd ed., section 4.5.2 (the greatest common divisor).
- ISO 80000-2:2019, Quantities and units — Part 2: Mathematics.
Frequently asked questions
Does gcd(a, b) · lcm(a, b) = a · b hold for three or more numbers?
No. The product identity is true only for two numbers. For a list you compute the GCD by repeatedly taking gcd of the running result with the next number, and the LCM likewise. For 4, 6 and 10: gcd = 2 and lcm = 60, but 2 × 60 = 120 while 4 × 6 × 10 = 240.
What happens if one or both inputs are zero?
gcd(a, 0) = |a| because every number divides 0. gcd(0, 0) is conventionally 0. lcm with 0 is 0 by convention. Negative inputs give the same results as their absolute values.
Why is Euclid’s algorithm so much faster than factorisation?
Each division at least halves the larger number every two steps, so it needs about log₂(min(a, b)) × 2 steps at most. Factorising large numbers has no known comparably fast method, which is why RSA cryptography relies on it being hard.
What is Bézout’s identity used for?
It guarantees integers x and y with ax + by = gcd(a, b). When gcd(a, b) = 1, x is the modular inverse of a modulo b, which is how RSA computes a private key from a public exponent.
How do I use the GCD to simplify a fraction?
Divide the numerator and denominator by their GCD. For 48/180, gcd = 12, so 48/180 = 4/15. If the GCD is 1 the fraction is already in lowest terms.
What does “coprime” mean?
Two integers are coprime (relatively prime) when their only common positive divisor is 1, i.e. gcd = 1. They need not be prime themselves: 8 and 15 are coprime. A set is pairwise coprime if every pair in it is coprime.
Related calculators
Continue with number theory.