GCD and LCM calculator: Euclid's algorithm step by step

Type two or more numbers, and the solver finds the greatest common divisor and the least common multiple in two ways and shows why the answer is right.

Examples: 84 and 126 lcm(12, 18, 30) 1071, 462 coprime 35 and 64 Bezout 240 and 46 84x + 126y = 42 6x + 9y = 7

Loading the solver…

What you can type

Two or more numbers, separated by spaces, commas or “and”: 84 and 126, 12, 18, 30. The solver finds both the GCD and the LCM; if you only need one, say so: gcd(84, 126), lcm 12 18 30 (the British hcf, highest common factor, works too). It can also check whether numbers are coprime (coprime 35 and 64), find Bézout coefficients (Bezout 240 and 46) and solve equations like 84x + 126y = 42 in integers.

Negative numbers are fine: $-12$ has the same divisors as $12$, so the solver takes absolute values. Zero is fine too: $\gcd(0, 7) = 7$, since zero is divisible by anything, and $\operatorname{lcm}(0, 7) = 0$.

Euclid’s algorithm: how to find the GCD

The greatest common divisor of two numbers is the largest number that divides both. For small numbers you can see it at once: $\gcd(12, 18) = 6$. For big ones, going through divisors takes a long time, and factorising the numbers into primes takes even longer. Euclid’s algorithm needs neither. It was described in Euclid’s Elements (Book VII) more than two thousand years ago, and it’s how computers compute the GCD today.

Divide the larger number by the smaller with remainder: $a = b \cdot q + r$.
If the remainder is zero, the answer is the smaller number $b$.
Otherwise replace the pair $(a, b)$ with $(b, r)$ and repeat.

The answer is the last non-zero remainder. The numbers melt away very fast: the French mathematician Gabriel Lamé proved in 1844 that the number of divisions needed is at most five times the number of digits of the smaller number. For two twenty-digit numbers that’s at most a hundred divisions, whereas factorising would mean trying hundreds of millions of divisors.

The larger of the two numbers.

The smaller one, the divisor.

The remainder, $0 \le r < b$. It is less than $b$, so the pair of numbers shrinks at every step and eventually reaches zero.

Why the GCD doesn’t change: anything that divides $a$ and $b$ also divides $r = a - bq$; and conversely, anything that divides $b$ and $r$ also divides $a = bq + r$. The pairs $(a, b)$ and $(b, r)$ have exactly the same common divisors, and so the same greatest one. Example: $126 = 1 \cdot 84 + 42$, so $\gcd(126, 84) = \gcd(84, 42)$, and $84 = 2 \cdot 42$ divides exactly, so the answer is $42$.

The algorithm has a visual geometry, shown in the solver’s picture. Take an $a \times b$ rectangle and keep cutting off the largest squares you can. From $126 \times 84$ a square $84 \times 84$ comes off, leaving a strip $84 \times 42$, which is covered exactly by two $42 \times 42$ squares. The side of the last square is the GCD: squares of that size tile the whole original rectangle without gaps, and no larger squares can.

How to find the LCM

The least common multiple is the smallest positive integer divisible by both numbers. Listing multiples to find it is awkward; through the GCD it’s a single division.

In the product $a \cdot b$ the common prime factors of the numbers appear twice: once from $a$ and once from $b$. Dividing by the GCD removes the extra copy. This holds for positive integers $a$ and $b$.

Example: $\operatorname{lcm}(84, 126) = \frac{84 \cdot 126}{42} = 2 \cdot 126 = 252$. It’s easier to divide one of the numbers by the GCD first and then multiply: the numbers stay smaller. It also shows that $\gcd \cdot \operatorname{lcm} = a \cdot b$, a good check of the answer.

The second way is through prime factorisation. Factorise both numbers: $84 = 2^2 \cdot 3 \cdot 7$, $126 = 2 \cdot 3^2 \cdot 7$. The GCD takes only the common primes, each to the smaller of its powers: $2 \cdot 3 \cdot 7 = 42$. The LCM takes all the primes, each to the larger power: $2^2 \cdot 3^2 \cdot 7 = 252$. For small numbers this is quick and visual (the solver draws circles with the shared factors); for big ones you’d first have to spend a long time factorising.

For three or more numbers you work along a chain: $\gcd(a, b, c) = \gcd(\gcd(a, b), c)$, and the same for the LCM. But the formula “product divided by the GCD” no longer works for three numbers: $\operatorname{lcm}(2, 2, 2) = 2$, not $8 \div 2 = 4$.

Worked examples

Example 1. Simplify the fraction $\frac{391}{527}$

Neither number is divisible by $2$, $3$ or $5$, but Euclid’s algorithm finds a common divisor in four divisions:

$$527 = 1 \cdot 391 + 136,\quad 391 = 2 \cdot 136 + 119,\quad 136 = 1 \cdot 119 + 17,\quad 119 = 7 \cdot 17.$$

The last non-zero remainder is $17$. So $391 = 17 \cdot 23$, $527 = 17 \cdot 31$ and $\frac{391}{527} = \frac{23}{31}$. Along the way, $\operatorname{lcm}(391, 527) = 23 \cdot 527 = 12{,}121$.

Example 2. Three numbers: 12, 18 and 30

The factorisations: $12 = 2^2 \cdot 3$, $18 = 2 \cdot 3^2$, $30 = 2 \cdot 3 \cdot 5$. The common primes are $2$ and $3$, each to its smallest power: $\gcd = 2 \cdot 3 = 6$. All the primes to their largest powers: $\operatorname{lcm} = 2^2 \cdot 3^2 \cdot 5 = 180$.

Along the chain, the same: $\gcd(12, 18) = 6$, $\gcd(6, 30) = 6$; $\operatorname{lcm}(12, 18) = 36$, $\operatorname{lcm}(36, 30) = 180$. Check: $180 = 12 \cdot 15 = 18 \cdot 10 = 30 \cdot 6$, and the factors $15$, $10$, $6$ have no common divisor other than $1$, so there’s no smaller common multiple.

Example 3. Bézout’s identity for 240 and 46

Euclid’s algorithm: $240 = 5 \cdot 46 + 10$, $46 = 4 \cdot 10 + 6$, $10 = 1 \cdot 6 + 4$, $6 = 1 \cdot 4 + 2$, $4 = 2 \cdot 2$. The GCD is $2$. Now go backwards and express the two in terms of the original numbers, each time substituting the remainder from the line before:

$$2 = 6 - 4 = 6 - (10 - 6) = 2 \cdot 6 - 10 = 2(46 - 4 \cdot 10) - 10 = 2 \cdot 46 - 9 \cdot 10 = 2 \cdot 46 - 9(240 - 5 \cdot 46) = 47 \cdot 46 - 9 \cdot 240.$$

We get $240 \cdot (-9) + 46 \cdot 47 = 2$. Check: $-2160 + 2162 = 2$.

Example 4. The equation $84x + 126y = 42$ in integers

$\gcd(84, 126) = 42$, and $42$ is divisible by $42$, so solutions exist. One is obvious: $84 \cdot (-1) + 126 \cdot 1 = 42$. All the others come from shifting: add $126 \div 42 = 3$ to $x$ and subtract $84 \div 42 = 2$ from $y$, and the left-hand side doesn’t change. Answer: $x = -1 + 3k$, $y = 1 - 2k$, where $k$ is any integer. The solver writes the same thing starting from the smallest non-negative $x$: $x = 2 + 3k$, $y = -1 - 2k$.

The equation $6x + 9y = 7$, on the other hand, has no solutions: for any integers $x$ and $y$ the left-hand side is divisible by $\gcd(6, 9) = 3$, and $7$ isn’t.

Bézout’s identity and equations in integers

Two integers, at least one of them non-zero.

Integer coefficients, found by running Euclid’s algorithm backwards. The pair isn’t unique: along with $(x, y)$, every $\left(x + \frac{b}{d}k,\ y - \frac{a}{d}k\right)$ works too, where $d = \gcd(a, b)$.

The GCD is the smallest positive integer that can be written as $ax + by$. Everything that can be written this way is divisible by the GCD.

Example: $1071 \cdot (-3) + 462 \cdot 7 = -3213 + 3234 = 21 = \gcd(1071, 462)$.

Bézout’s identity gives the rule for the equation $ax + by = c$ at once: it has integer solutions exactly when $c$ is divisible by $\gcd(a, b)$. That explains the old jug puzzle: with $3$-litre and $5$-litre jugs you can measure out $4$ litres, because $\gcd(3, 5) = 1$, while with $4$-litre and $6$-litre jugs no odd volume can ever be measured. More in the chapter on divisibility.

Common mistakes

Mixing up the GCD and the LCM. The GCD is no bigger than the smaller number, and the LCM is no smaller than the larger. If your “GCD” came out bigger than one of the numbers, something’s wrong.
Dividing the wrong thing in Euclid’s algorithm. The next step divides the previous divisor by the remainder, not the original number by the remainder.
Writing the last quotient or zero as the answer. The GCD is the last non-zero remainder, that is, the divisor in the last line.
Taking the largest powers for the GCD and the smallest for the LCM. It’s exactly the other way round: a common divisor can’t contain more twos than each of the numbers has.
Taking the LCM to be the product. $a \cdot b$ is a common multiple, but it’s the least one only for coprime numbers: $\operatorname{lcm}(4, 6) = 12$, not $24$.
Dividing the product of three numbers by the GCD. That formula works only for two numbers; for three, work along a chain.