GCD and LCM Calculator formula — how it actually works
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
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
- How to use the GCD and LCM Calculator — step by step
- GCD and LCM Calculator explained with worked examples
- GCD and LCM Calculator for beginners — start here
- Common mistakes people make with the GCD and LCM Calculator
- GCD and LCM Calculator vs doing it by hand — which is faster?
- gcd lcm calculator — the complete guide
- How to get an accurate result from the GCD and LCM Calculator
- GCD and LCM Calculator for students — with examples
- GCD and LCM Calculator for homeowners and DIYers
Find the GCD and LCM of any two whole numbers — free, in your browser.