GCD and LCM calculator

Find the GCD and LCM online, with the working shown

The greatest common divisor (GCD, also called HCF or GCF) and the least common multiple (LCM) are two cornerstones of arithmetic: you meet them in middle school with fractions, then again in number theory with Euclid’s algorithm and Bézout’s identity. This calculator handles 2 to 20 whole numbers and shows how the answer is reached: successive divisions, prime factorization, Bézout coefficients and the simplified fraction.

Finding them quickly matters whenever you simplify a fraction, add fractions with different denominators, work out when two repeating events coincide or cut material into identical squares. Students revising, parents checking homework, teachers preparing answer keys and programmers dealing with cycles, gear ratios or RSA keys all get an exact result plus the full method to copy down.

1. Enter your numbers

   In the “Whole numbers (2 to 20)” field, type 2 to 20 integers separated by commas, spaces or semicolons, or click one of the examples.

2. Read the GCD and LCM

   The two cards update as you type; the “Copy” button puts the raw number (no separators) on your clipboard.

3. Check the properties

   Below the cards: whether the numbers are coprime (and, from three numbers on, whether they are pairwise coprime); for two numbers, the check GCD × LCM = a × b, the Bézout identity and the simplified fraction a/b.

4. Open the explanations

   “Euclidean algorithm, step by step” lists every division a = q × b + r; “Prime factorizations” shows the minimum and maximum exponents.

How to find the GCD and LCM: Euclid’s algorithm and prime factors

The tool runs the Euclidean algorithm: divide the larger number by the smaller, a = q × b + r, then repeat with b and the remainder r, because gcd(a, b) = gcd(b, r). The last non-zero remainder is the GCD. The LCM follows without any factoring: lcm(a, b) = a × b ÷ gcd(a, b).

For more than two numbers the results are chained: gcd(a, b, c) = gcd(gcd(a, b), c), and likewise for the LCM. The prime factor panel gives the second classroom method: writing a = 2α × 3β × …, the GCD takes each common prime with its smallest exponent and the LCM takes every prime with its largest exponent.

• a and b: the dividend and the divisor on each line (the larger number comes first).
• q: the whole-number quotient; r: the remainder, always between 0 and b − 1.
• GCD: the largest integer dividing every number; LCM: the smallest positive integer divisible by every number.
• u and v: the Bézout coefficients, integers (possibly negative) with u × a + v × b = gcd(a, b), produced by the extended Euclidean algorithm.
• α, β…: the exponents in the factorization, for example 12 = 2² × 3¹.

Worked examples of GCD and LCM

What are the GCD and LCM used for?

• Fractions: simplify 12/18 to 2/3 by dividing by the GCD 6, or add 5/12 + 7/18 over the common denominator 36 = LCM(12, 18): 15/36 + 14/36 = 29/36.
• Cycles and timetables: two buses leave together at 8:00, one every 12 minutes and one every 18; they leave together again at 8:36, after LCM = 36 minutes.
• Cutting and tiling: to cover a 120 cm × 84 cm board with the largest possible squares and no waste, use GCD(120, 84) = 12 cm squares, 10 × 7 = 70 of them.
• Gears and rhythms: gears with 12 and 18 teeth return to their starting position after 36 teeth have meshed, that is 3 turns of the small gear and 2 of the large one.
• Cryptography: in RSA the public exponent e must be coprime with φ(n), and the private key d is its inverse modulo φ(n), found with Bézout. With e = 17 and φ(n) = 3,120, the tool shows (−367) × 17 + 2 × 3,120 = 1, so d = −367 + 3,120 = 2,753; indeed, 17 × 2,753 = 15 × 3,120 + 1.

Common mistakes

• Mixing them up: the GCD is never larger than the smallest number and the LCM never smaller than the largest. For 12 and 18, a “GCD” of 36 is necessarily wrong.
• Multiplying the numbers to get the LCM: 12 × 18 = 216, but the LCM is 36. The product of two numbers equals their LCM only when they are coprime (17 × 31 = 527).
• Using GCD × LCM = product with three numbers: for 8, 12 and 20, 4 × 120 = 480, while 8 × 12 × 20 = 1,920.
• Typing thousands separators: commas and spaces split the list, so “1,071” is read as two numbers, 1 and 71. Type 1071 instead.

Everything is computed locally in your browser with exact integer arithmetic (BigInt): no number is sent to any server. Limits: 2 to 20 non-zero whole numbers of up to 15 digits; the prime factorization is shown only when every prime factor can be found quickly (trial division up to 1,000,000, then a primality test).