Highest common factor and lowest common multiple
Give it any number of whole numbers and it gives you both — with Euclid's method written out, and the factorisation that explains the answer. Nothing you type here leaves your browser — it is worked out on your own device, so there is nothing to send and nothing to log.
The same two things under four names
Britain says highest common factor and lowest common multiple; America says greatest common divisor and least common multiple. HCF, GCF, GCD and LCM, LCD, LCM. They are the same two numbers, and this page answers to all of them.
What they are for
| Highest common factor | The biggest number that divides all of them. Use it to cancel a fraction: 48/180 divided top and bottom by 12 is 4/15, and 12 is the HCF. |
|---|---|
| Lowest common multiple | The smallest number they all divide into. Use it to add fractions, or to work out when two repeating things next coincide — buses every 12 and every 18 minutes meet every 36. |
Two routes to the same answer
Factorise both numbers and the answers fall out: the HCF takes the lowest power of each shared prime, the LCM takes the highest power of every prime that appears in either. That is the version worth understanding, and it is shown below the answer.
The version actually used here is Euclid's, which is older than the factorisation and much faster: divide the larger by the smaller, keep the remainder, repeat until the remainder is nothing. The last non-zero remainder is the HCF. It never factorises anything, which matters when the numbers are large.
Why the LCM divides before it multiplies
The LCM of two numbers is a × b ÷ HCF. Written in that order it breaks: browsers hold whole numbers exactly only up to about nine quadrillion, and a × b can pass that while the answer sits comfortably below it. The LCM of 128,121,150 and 365,925,498 is 7,813,799,269,680,450, and the multiply-first route returns 7,813,799,269,680,451 — out by one, with nothing to suggest anything went wrong. Dividing first cannot overflow, so that is what happens here.
The awkward cases, answered
- Zero. Every number divides 0, so the HCF of 0 and 7 is 7. The LCM is 0, because 0 is the only multiple 0 has.
- Coprime numbers. If the HCF is 1 they share no factors, and the LCM is simply the two multiplied.
- Negatives. Signs are dropped. Factors and multiples are questions about size.
What it will not do
- It will not take fractions. The HCF of 1/2 and 1/3 is a defined thing but almost nobody means it.
- It will not go past 9,007,199,254,740,991, for the reason in the section above.
- It will not cancel your fraction for you. It gives you the number to divide by and says which.