EN

GCD and LCM Calculator for Multiple Numbers

The GCD (greatest common divisor) and LCM (least common multiple) are usually taught for two numbers. For a list of several numbers, the same idea still works: reduce the list pair by pair, applying the Euclidean algorithm at each step. A comma or a space separates the entries.

The list of numbers

Positive whole numbers

2 to 20 strictly positive whole numbers, separated by a comma or a space.

Starred terms on first mention are unpacked in the glossary at the end of the page.

What the GCD of a list actually is

The GCD* of a collection of positive integers is the largest whole number that divides every one of them. Two numbers or twenty: same object. 12, 18 and 30 are all multiples of 6, and nothing larger than 6 divides all three.

School English is not one dialect. A GCSE paper almost always prints HCF* — highest common factor. Many US textbooks say GCF, greatest common factor. A-level, SAT and university work settle on GCD. Three labels, one integer. This page uses GCD, and treats the others as synonyms.

The LCM* is the other face of the same coin: the smallest positive integer that is a multiple of every number in the list. For 12, 18 and 30 that is 180. Nothing smaller is a multiple of all three. Arithmetic of this kind is older than algebra; the same pair of numbers later cancels a fraction, times a bus timetable, or finds a common denominator.

Euclid's algorithm: remainders until zero

Keep the remainder. Divide the larger integer by the smaller, discard the quotient, and keep what is left. Repeat with the old smaller number and that leftover. The last non-zero remainder is the GCD.

Each line is a = q·b + r, with 0 ≤ r < b. Then a becomes b, and b becomes r. A worked pair: 1,071 and 462.

  1. 1,071 = 2·462 + 147
  2. 462 = 3·147 + 21
  3. 147 = 7·21 + 0

Last non-zero remainder: 21. So gcd(1,071, 462) = 21.

a = q·b + r  (repeat until r = 0; the last non-zero remainder is the GCD)

The Euclidean algorithm* cannot run forever. Remainders are whole numbers, each strictly smaller than the previous divisor. A strictly decreasing sequence of non-negative integers hits zero. In practice it hits zero quickly. This page prints every one of those lines, for each successive pair in a list of 2 to 20 positive integers.

Folding a list pair by pair

A GCD of three integers is not a different gadget. It is the largest positive integer that divides all three. Associativity lets the two-argument routine do the work.

gcd(a, b, c) = gcd(gcd(a, b), c)

lcm(a, b, c) = lcm(lcm(a, b), c)

Take the first two, then fold in the next, and so on. Order does not matter. A list of twenty numbers is nineteen of these folds — which is what the calculator runs, showing a = q·b + r each time.

Take 8, 12 and 20. gcd(8, 12) = 4, then gcd(4, 20) = 4. On the multiple side, lcm(8, 12) = 24, then lcm(24, 20) = 120. Four divides all three; nothing larger does; 120 is the least common multiple. Shuffle the list: same two answers. The operation is commutative as well as associative.

Why LCM(a, b) = ab / GCD(a, b)

Listing multiples until a match appears is honest, and slow. 12, 24, 36, 48, 60… against 18, 36 — the meeting is 36, but the lists grow with the inputs. The two-number identity short-circuits that hunt.

lcm(a, b) = a · b ÷ gcd(a, b)

Once Euclid has returned the GCD, one division and one multiplication finish the LCM. The division is done first, so the intermediate product does not balloon. For 12 and 18: gcd = 6, then 12 × 18 ÷ 6 = 36.

The identity is exact for a pair. It is the reason this page never enumerates multiples. For three or more arguments the same formula is reused at every fold, never applied to the whole list in one go — a trap that has its own section later.

Min and max exponents from a prime factorisation

There is a picture-book method, useful while the numbers stay small: write each integer as a product of primes, then read off the exponents.

For the GCD, keep the smallest exponent of each prime that appears in every factorisation. For the LCM, keep the largest. A prime that shows up on only one side contributes nothing to the GCD and everything to the LCM.

60 and 84, for instance:

  • 60 = 22 × 3 × 5
  • 84 = 22 × 3 × 7
  • GCD = 22 × 3 = 12
  • LCM = 22 × 3 × 5 × 7 = 420

Fine on a whiteboard. Miserable once the integers run into five or six digits: factoring 999,983 is a chore; Euclid is done in a handful of remainders. This calculator sticks to Euclid on purpose. The factor picture still earns its keep as a check, and as the reason the identity lcm = ab / gcd is true — each exponent on the left is min + max, which is just the two original exponents added.

Coprime as a pair and coprime as a set

Two integers are coprime* (relatively prime) when their only positive common divisor is 1. Neither needs to be a prime number. 14 and 15 are coprime; so are 9 and 25; so are 8 and 9.

Consecutive integers are always coprime. Any common divisor of n and n+1 would divide their difference, which is 1. That is the whole argument.

For a longer list, “coprime as a set” means gcd(a, b, c, …) = 1. That is weaker than “coprime in pairs”. 6, 10 and 15 have gcd 1 as a triple, yet gcd(6, 10) = 2. A global GCD of 1 does not forbid some pair from sharing a factor. Number-theory texts mark the distinction carefully; a GCSE mark scheme that asks only for the HCF of three numbers is asking for the set version.

Cancelling a fraction with the GCD

To cancel a fraction down to lowest terms, divide top and bottom by their GCD. That is the whole rule. The fraction calculator does the cancelling; this page shows where the divisor comes from.

Back to 1,071 / 462. gcd = 21, so

1,071 / 462 = (1,071 ÷ 21) / (462 ÷ 21) = 51 / 22

51 and 22 are coprime, so the fraction will not cancel any further. If the GCD had been 1 from the start, the fraction was already in lowest terms — a test, not just a recipe. Divisibility tests for 2, 3, 5 and 9 often spot a shared factor by eye; they do not replace Euclid once the numbers leave two digits.

Cancelling a common factor that is not the GCD only goes part-way. 48/18 divided by 2 is 24/9, which still reduces. The GCD (6) is what reaches 8/3 in one step.

Least common multiple as a meeting time

The LCM answers a practical question: when do these repeating cycles next line up?

A train every 15 minutes, a bus every 20, both leaving the interchange together. They leave together again after lcm(15, 20) = 60 minutes. Three traffic signals of 12, 18 and 30 seconds go green together every lcm(12, 18, 30) = 180 seconds. Two gears with 14 and 21 teeth mesh back to the same teeth after 42 teeth — same arithmetic, workshop vocabulary.

More than two periods: fold pairwise, as above. Non-integer periods (every 2½ minutes and every 4) want a common unit first — here, half-minutes: 5 and 8. This form accepts only strictly positive whole numbers, so that conversion belongs on paper before the list is pasted in.

Adding fractions uses the same meeting. 1/6 + 1/8 + 1/10 needs a common denominator. Any common multiple of 6, 8 and 10 works (240, 480…); the cheapest is their LCM, 120. Then 20/120 + 15/120 + 12/120 = 47/120. GCD and LCM hand the job to each other.

Bézout's identity: the GCD as an integer combination

Bézout's identity* says that for any two integers a and b there are integers u and v — they may be negative — such that

a·u + b·v = gcd(a, b)

For 1,071 and 462 one choice is u = −3, v = 7: 1,071·(−3) + 462·7 = −3,213 + 3,234 = 21. Walking Euclid's remainders backwards (the extended Euclidean algorithm) recovers u and v. Modular inverses, linear Diophantine equations, a fair chunk of elementary cryptography: that is where these coefficients earn their keep.

This page does not print u and v. It stops at the GCD, the LCM, and the division steps. Bézout's coefficients are a second reading of the same remainders, not an output of the form. Once the unknown is squared rather than linear, the tool changes: that is a quadratic equation, not a GCD.

Fibonacci numbers and the worst case for Euclid

Euclid is cheap. The number of steps grows with the logarithm of the inputs, not with the inputs themselves.

The worst pair, Lamé showed in 1844, is two consecutive Fibonacci numbers. Every quotient is then 1, so the remainder crawls down as slowly as the theorem allows. gcd(34, 21) — F9 and F8 — goes 13, 8, 5, 3, 2, 1, 0. Seven remainders for two modest integers. In any case the number of divisions is at most five times the number of decimal digits of the smaller input.

That is why “factor first, then read exponents” is almost never the right machine strategy: Euclid has finished before a single prime factor has been found. Fibonacci inputs are not a trap in this form; they just fill the step table.

HCF on a GCSE paper, GCD on the SAT

The object does not change with the exam board. The wording does.

GCSE papers, and most English Key Stage 3 textbooks, print “highest common factor” and “lowest common multiple”. An SAT problem, and almost every US high-school sheet, prints “greatest common divisor” or “greatest common factor”, and “least common multiple”. Scottish National 5 sits with HCF. Further Maths and A-level number theory switch to GCD without comment.

A search box follows the same split. “HCF calculator” and “GCD calculator” are the same request. So is “LCM of three numbers”. This page answers all of them, with Euclid's remainders shown rather than a factor tree — the factor tree remains a valid GCSE method, just not the one the machine runs.

gcd(0, n) = n, and why zero is refused here

The usual convention is gcd(0, n) = n for n > 0. Zero is a multiple of every integer, so the common divisors of 0 and n are exactly the divisors of n, and the greatest is n. gcd(0, 0) is left undefined: every integer divides zero.

This calculator rejects zero, and negatives. It wants 2 to 20 strictly positive integers, each below 1,000,000. Euclid would cope with 0 under the convention above; the LCM would not. Every multiple of 0 is 0, and “least common multiple” becomes a word game this form is not playing.

The product identity does not extend to three arguments

For a pair, gcd(a, b) × lcm(a, b) = a × b. Always. It is the same identity used to compute the LCM without listing multiples.

It does not stretch to three arguments. For 2, 4 and 8: gcd = 2, lcm = 8, product of the three is 64, and 2 × 8 = 16, not 64. A “global” product formula of that shape does not exist.

Related confusion: a three-number GCD is not some extra operation besides the ordinary one. gcd(a, b, c) is gcd(gcd(a, b), c). This page folds left to right because the operation is associative. Shuffle the list, same answer. That is the whole of the “several numbers” trick: no new algorithm, just the two-number one, repeated.

Glossary

GCD
Greatest common divisor: the largest positive integer that divides every number in the list. Same object as HCF (highest common factor) and GCF (greatest common factor).
HCF
Highest common factor. The name printed on most GCSE papers. Identical to the GCD.
LCM
Least common multiple — “lowest common multiple” on a UK school sheet. The smallest positive integer that is a multiple of every number in the list.
Euclidean algorithm
The remainder method for the GCD: divide, keep the remainder, replace the pair, stop at remainder 0. The last non-zero remainder is the GCD. Euclid of Alexandria, Elements, Book VII.
Coprime
Two integers are coprime (relatively prime) when their GCD is 1. Neither has to be a prime number. A whole list is coprime as a set when the GCD of all of them is 1 — a weaker condition than being coprime in every pair.
Bézout's identity
For any two integers a and b there exist integers u and v, possibly negative, such that au + bv equals gcd(a, b). Recovered by running Euclid backwards (the extended Euclidean algorithm). Not printed by this calculator.

Related calculators