← All blog posts

GCD and LCM Calculator formula — how it actually works

WhiteUI · A plain-English guide to the GCD and LCM Calculator

Every answer from the GCD and LCM Calculator comes from two pieces of maths: Euclid's algorithm finds the GCD, and one division turns the GCD into the LCM. Here is how each piece works.

The formulas

GCD by Euclid's algorithm: replace the larger number by its remainder on division, and repeat until the remainder is zero
LCM = (first × second) ÷ GCD
Check: GCD × LCM = first × second

Worked example — Euclid on 48 and 180

Divide 180 by 48: 48 goes in 3 times with a remainder of 36. Now divide 48 by 36: it goes in once with a remainder of 12. Now divide 36 by 12: it goes in exactly 3 times with a remainder of 0. The last divisor before the zero remainder, 12, is the GCD.

180 ÷ 48 = 3 remainder 36
48 ÷ 36 = 1 remainder 12
36 ÷ 12 = 3 remainder 0
GCD = 12, so LCM = 48 × 180 ÷ 12 = 720

At a glance

Euclid's algorithm ends at 1248 = 4 groups of 12180 = 15 groups of 12Each step replaces the larger number with a remainder.
Euclid's algorithm on 48 and 180 ends at 12, which is why 48 is 4 groups of 12 and 180 is 15 groups.

Why the LCM formula works

The product 48 × 180 counts every shared factor twice, and the GCD is exactly the shared part. Dividing the product by the GCD removes one copy of the shared part, leaving the smallest number both divide into: 8,640 ÷ 12 = 720.

The mistake to avoid

Stopping Euclid too early. After the first division, the remainder is 36 — but 36 is not the GCD, because it does not divide 48 exactly. The algorithm only stops when a remainder is zero, and the GCD is the last divisor used. Keep going until the remainder is zero.

Calculator or factor tree — which route is quicker?

Euclid’s algorithm is not the only way to find a GCD, and for small numbers a factor tree is just as good. Take 72 and 120. A factor tree breaks each number into primes — 72 is 2 × 2 × 2 × 3 × 3 and 120 is 2 × 2 × 2 × 3 × 5 — and the shared factors, 2 × 2 × 2 × 3, multiply to a GCD of 24. Euclid reaches the same answer in three divisions: 120 ÷ 72 leaves 48, 72 ÷ 48 leaves 24, and 48 ÷ 24 leaves 0, so the GCD is 24 and the LCM is 72 × 120 ÷ 24 = 360.

The factor tree shows you why the answer is what it is, which makes it the better route when you are learning. Euclid is the quicker route once the numbers grow, because it only needs remainders — no prime factors, no lists. For two-digit numbers, use whichever you find clearer; for three digits and above, Euclid wins, and the calculator wins over both.

What to check before you trust the answer

Use the same three checks as for any GCD and LCM pair, this time on 72 and 120. First, the product check: GCD × LCM must equal the product of the two numbers, and 24 × 360 = 8,640, which is exactly 72 × 120. Second, the GCD must divide both numbers: 72 ÷ 24 = 3 and 120 ÷ 24 = 5, both exact. Third, the LCM must be a multiple of both numbers: 360 ÷ 72 = 5 and 360 ÷ 120 = 3.

If the product check fails, the GCD and the LCM cannot both be right — one of them is wrong, and the Euclid steps are the place to look. A single wrong remainder anywhere in the chain changes every answer that follows it, so rework the divisions one at a time rather than guessing which answer to fix.

Frequently asked questions

What is the Euclidean algorithm?

A way to find the GCD by repeated division: divide the larger number by the smaller, replace the larger with the remainder, and repeat until the remainder is zero.

Why does LCM equal the product divided by the GCD?

The product counts every shared factor twice. Dividing by the GCD removes one copy of the shared part, leaving the smallest number both divide into.

How do I check the answer?

Multiply the GCD by the LCM. The result must equal the product of the two numbers you started with.

Does the formula work when one number is zero?

The LCM formula does not apply, because division by the GCD is not the whole story then. The GCD of 0 and 24 is 24, and the LCM is 0.

More guides on the GCD and LCM Calculator

Try it yourself

Find the GCD and LCM of any two whole numbers — free, in your browser.

Open the GCD and LCM Calculator