gizmobench

Greatest Common Factor Solver

Type two whole numbers and read the largest number that divides both, with Euclid's algorithm written out line by line beside it: one long division per line, down to the remainder of zero that ends it. Most pages on this search print the answer and stop, which is no use to anyone who was asked to show their working. The least common multiple is on the same stage, because the same two numbers answer both questions and the same people ask both. Add boxes for a third number and a fourth and the factor covers all of them at once. The arithmetic runs in BigInt, so numbers past the point where a calculator starts rounding are still exact.

GCF of 252 and 19818LCM 2,772
Euclid4 steps
252 = 1 x 198 + 54
198 = 3 x  54 + 36
 54 = 1 x  36 + 18
 36 = 2 x  18 +  0
remainder 0, so the factor is 18
First number
Second number
Factor
18
Multiple
2,772
Lead with

The greatest common factor of 252 and 198 is 18, in 4 steps. Their least common multiple is 2,772.

Whole numbers only, one to a box, or several in one box separated by spaces. Add a number for a third and a fourth: both answers then cover all of them.

  • Coprime pairnothing in common but 1
    GCF 1 · LCM 391
  • Three numbersthe factor of all three at once
    GCF 6 · LCM 360
  • Past the safe integerworked in BigInt, so it stays exact
    GCF 9,007,199,254,740,993
Factor or multiple, and which one you want. The greatest common factor is the largest number that divides all of yours with nothing left over, so it is the one to divide by when you are reducing a fraction or splitting things into equal groups. The least common multiple is the smallest number they all divide into, which is what you need for a common denominator or for two repeating schedules that must line up. Multiples never run out, so there is no largest one to find and the least is the useful answer. Euclid’s algorithm gives both: divide the larger by the smaller, keep the remainder, repeat until the remainder is zero, and the last divisor is the factor. Then the multiple is the first number divided by that factor and multiplied by the second. The Euclidean algorithm on whole numbers, with every step shown, and exact past the usual safe-integer limit because it works in BigInt. It cannot take a decimal or a fraction, and it says so rather than rounding one for you.

Common questions

What is the greatest common factor?
It is the largest whole number that divides every number you gave with nothing left over. For 252 and 198 it is 18, because 252 is 18 times 14 and 198 is 18 times 11, and no number bigger than 18 goes into both. It is also called the greatest common divisor or the highest common factor: the same number under three names. It is what you divide by to reduce a fraction to its lowest terms, and what you use to split two amounts into equal groups of the largest possible size. Two numbers that share nothing come back as 1, which is the honest answer rather than an error: 17 and 23 are both prime, so 1 is all they have in common.
How does Euclid's algorithm work?
Divide the larger number by the smaller, keep the remainder, and repeat with the two numbers you just used until the remainder is zero. The last divisor is the factor. The stage shows exactly that for 252 and 198: 252 = 1 x 198 + 54, then 198 = 3 x 54 + 36, then 54 = 1 x 36 + 18, then 36 = 2 x 18 + 0, and the closing line says remainder 0, so the factor is 18. Each line is a real long division you can check by hand, and the count of lines is in the corner of the pane. It works because any number dividing both a number and its remainder also divides the number it came from, so each line swaps the pair for a smaller pair with the same factor.
Is there such a thing as a greatest common multiple?
No, and that is worth saying plainly, because it is a common way to type the search. The multiples of two numbers carry on for ever, so there is no largest one to find: 2,772 and 5,544 and 8,316 are all multiples of both 252 and 198, and you can always double again. What exists, and what people who type that phrase almost always want, is the least common multiple, the smallest number both divide into. This page gives you that beside the factor, so whichever of the two you needed is already on the screen. The Lead with control decides which of them fills the stage.
How do I do three or more numbers?
Press Add a number and another box appears, up to ten of them. The factor is then folded two at a time, which is what the working shows: 24 and 30 share 6, then 6 and 72 share 6, so 6 divides all three. The multiple works the same way and comes out at 360. You can also type several numbers into one box separated by spaces. One thing to watch: a comma here separates one number from the next, so write 1234 rather than 1,234, and the tool says so rather than guessing which you meant.
Can it take a decimal, a fraction or a negative number?
No, and it refuses rather than rounding. A common factor is defined for whole numbers, so 12.5 comes back with a message saying it is a decimal and suggesting you multiply both numbers up until they are whole. A fraction like 3/4 is asked to be entered as its top and bottom instead, which is the useful thing anyway: the factor of 3 and 4 is what reduces it. A minus sign is refused too, since the factor of 8 and 12 is the same as the factor of -8 and 12. Each of those messages names what you typed, so you can see which box to fix.
How big a number can it take?
Up to 200 digits each, which is far past the point where an ordinary calculator gives up. Everything is worked in BigInt rather than in floating point, so nothing rounds on the way through. That matters more than it sounds: 9,007,199,254,740,993 is the first odd number a normal JavaScript number cannot hold, and a page that used one would quietly answer a slightly different question. Try it on the third example row, where two multiples of that number come back with their exact factor. The 200 digit and ten number limits are only there to keep the working readable.
Is anything uploaded, and are my numbers kept?
Nothing is uploaded. The arithmetic runs in your browser and the page makes no request while you type. The numbers in the boxes and which answer you had leading are remembered in this browser alone, so the page opens where you left it, and the Start over button at the top of the page forgets them. The Copy button puts the answer and the whole working on your clipboard as plain text, spaced so the columns still line up when you paste it into a document.

The Euclidean algorithm on whole numbers, with every step shown, and exact past the usual safe-integer limit because it works in BigInt. It cannot take a decimal or a fraction, and it says so rather than rounding one for you.