GCD & LCM Calculator – Free Calculator

Understanding the GCD and LCM calculator — concept and principle

The greatest common divisor (GCD, also called the greatest common factor or HCF) is the largest whole number that divides every number in a list. The least common multiple (LCM) is the smallest positive number that every number in the list divides. The GCD is used to simplify fractions and split things into equal groups; the LCM is used for common denominators and for working out when repeating cycles line up, such as two buses that leave every 12 and 18 minutes.

The overlap gives the GCD; the whole picture gives the LCM.

How it is calculated

GCD uses the Euclidean algorithm: GCD(a, b) = GCD(b, a mod b), repeated until the remainder is 0; the last non-zero value is the GCD.
LCM of two numbers: LCM(a, b) = |a × b| ÷ GCD(a, b).
For more than two numbers, both are applied pairwise: GCD(a, b, c) = GCD(GCD(a, b), c) and likewise for the LCM.

Inputs are rounded to whole numbers.

The principle

Any number that divides both a and b also divides a − b, and therefore also the remainder a mod b. So the pair (a, b) and the pair (b, a mod b) have exactly the same common divisors, and the numbers shrink at every step until the answer appears. The LCM formula follows from prime factorizations: the GCD takes each prime to its lowest power, the LCM to its highest, and lowest + highest equals the sum of both exponents, so GCD × LCM = a × b.

Worked example

Inputs: 12, 18, 30.
GCD(12, 18): 18 = 1 × 12 + 6, then 12 = 2 × 6 + 0, so 6. Next GCD(6, 30) = 6. Result: GCD = 6.
LCM(12, 18) = 216 ÷ 6 = 36.
LCM(36, 30) = 1080 ÷ GCD(36, 30) = 1080 ÷ 6 = 180. Result: LCM = 180.
Check with factorizations: 12 = 2²·3, 18 = 2·3², 30 = 2·3·5. Lowest powers give 2·3 = 6; highest powers give 2²·3²·5 = 180.

How to read the result

A GCD of 1 means the numbers are coprime: they share no factor and any fraction built from two of them is already in lowest terms. The LCM is always at least as large as the biggest input, and it equals the product of the numbers only when they are pairwise coprime. In the bus example, buses every 12 and 18 minutes leave together every 36 minutes.

Common mistakes

Mixing up the two: the GCD is never larger than the smallest number, the LCM never smaller than the largest.
Using GCD × LCM = product for three or more numbers; that identity holds only for two.
Listing factors by hand and missing one, which the Euclidean algorithm avoids.

Keep in mind: Results above about 9 × 10¹⁵ exceed the exact integer range of standard double-precision numbers, so the LCM of many large inputs may not be exact.

Frequently asked questions

What is the GCD of a number and 0?

GCD(a, 0) = |a|, because every number divides 0. The LCM involving 0 is usually defined as 0.

How do I find the GCD of two large numbers by hand?

Use repeated division: divide the larger by the smaller, replace the larger with the remainder, and stop when the remainder is 0.

Are GCF, HCF and GCD the same thing?

Yes. They are regional names for the same quantity.

Sources: Euclid, Elements, Book VII, Propositions 1–3 and 34 · D. E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, Section 4.5.2

Checked 8 Nov 2026. Standard formulas, computed in your browser with double-precision numbers.

Your numbers