The two quantities
A common divisor of several whole numbers is a number that divides all of them with nothing left over. The largest such number is the greatest common divisor, GCD, also called the highest common factor or HCF. A common multiple is a number all of them divide into; the smallest positive one is the least common multiple, LCM. You reduce a fraction by dividing through by the GCD, and you add fractions by rewriting them over the LCM of the denominators.
Both fall straight out of prime factorisation. Take 84 = 22 x 3 x 7 and 36 = 22 x 32. For the GCD, take every prime they share at the lower exponent: 22 x 3 = 12. For the LCM, take every prime that appears in either at the higher exponent: 22 x 32 x 7 = 252.
Why the Euclidean algorithm is the one you actually use
Factoring is fine for small numbers and hopeless for large ones. The Euclidean algorithm never factors anything. Divide the larger number by the smaller, keep the remainder, then repeat with the divisor and that remainder, until the remainder hits zero. The last non-zero divisor is the GCD.
Worked on 1071 and 462:
| Step | Division | Remainder |
|---|---|---|
| 1 | 1071 = 462 x 2 + 147 | 147 |
| 2 | 462 = 147 x 3 + 21 | 21 |
| 3 | 147 = 21 x 7 + 0 | 0 — stop |
The GCD is 21. Three divisions, no factor tables. The number of steps grows only with the number of digits, not with the size of the numbers, which is why every computer algebra system and every fraction library uses this and not factorisation.
The identity, and the trap in it
For exactly two numbers, GCD x LCM = a x b. So once you have the GCD you get the LCM for free: LCM = a x b / GCD. For 1071 and 462 that is 494,802 / 21 = 23,562.
This identity does not extend to three or more numbers, and assuming it does is the most common error in this corner of arithmetic. Take 4, 6 and 15. Their GCD is 1 and their product is 360, which would suggest an LCM of 360. The actual LCM is 60. The correct method is to fold pairwise: LCM(4, 6) = 12, then LCM(12, 15) = 60. The GCD folds the same way, LCM(a, b, c) = LCM(LCM(a, b), c), and that is what this page does internally.
Edge cases this page refuses, and what they would mean
Inputs are restricted to whole numbers from 1 to a billion, so results stay exact and the factorisation stays fast. The mathematics is defined more widely than that:
- Negatives. GCD and LCM are conventionally taken as positive, so they are computed on absolute values. GCD(-12, 18) = 6.
- Zero. Every integer divides zero, so GCD(a, 0) = a. The LCM of anything with zero is 0, since zero is the only common multiple. Both are correct and both are useless in practice, which is why zero is excluded here.
- Above a billion. Excluded so that trial-division factorisation cannot stall the page. The GCD itself would still be instant; the prime factorisation is the slow part.
The least common multiple is also checked against the largest integer a browser represents exactly, 9,007,199,254,740,991. Five large coprime inputs will exceed it, and the page says so rather than printing a number that has silently lost its low digits.
Where these show up outside a maths class
The GCD reduces fractions to lowest terms, which is what the fraction calculator does on every result, and it also reduces gear and pulley ratios to their simplest form. The LCM gives the common denominator for adding fractions, the period at which two repeating cycles line up again — two machines on 12-minute and 18-minute cycles coincide every 36 minutes — and the smallest run length that divides evenly into several batch sizes at once.
Questions people ask
What is the difference between GCD, GCF and HCF?
Nothing. Greatest common divisor, greatest common factor and highest common factor are three names for the same quantity, differing only by country and textbook. GCD is standard in mathematics and computing, GCF is common in American school material, and HCF in British and Commonwealth material. Any of them means the largest whole number that divides all your inputs exactly. There is a matching spread of names on the other side too: least common multiple and lowest common multiple are the same thing.
Two numbers have an LCM equal to their product. What does that tell me?
That they are coprime — their greatest common divisor is 1. It follows directly from GCD x LCM = a x b: if the LCM is the full product, the GCD must be 1. Coprime does not mean either number is prime. 8 and 15 are coprime and neither is prime; they simply share no prime factor, since 8 is all twos and 15 is three times five. This is worth checking before adding fractions, because coprime denominators mean the common denominator is just the two multiplied together and there will be nothing to reduce at the end.
How do I get the GCD of more than two numbers by hand?
Fold it pairwise. Find the GCD of the first two, then the GCD of that result with the third, and so on. The order does not matter and the result is the same whichever way you group them. One practical shortcut: as soon as a running GCD reaches 1 you can stop, because nothing further can bring it back up. The same folding works for the LCM, with the important difference that the product identity does not carry over past two numbers, so you must fold rather than multiply and divide.
Why does the calculator show prime factorisations when it does not need them?
Because they are what makes the answer checkable. The Euclidean algorithm gives you a number with no visible justification, while the factorisations let you confirm by eye that the GCD really is the shared primes at their lowest powers and the LCM really is every prime at its highest. For a homework problem that asks you to show the method, the factorisation view is usually the one being marked, and the Euclidean table is the one you would use if the numbers were too large to factor.