GCD calculator
To find the GCD of 48 and 60, divide and keep the remainder: 60 mod 48 is 12, then 48 mod 12 is 0, so the answer is 12. It appears in Euclid Elements around 300 BC and remains the method every computer uses today, because its running time grows only with the number of digits rather than the size of the numbers.
The greatest common divisor is the largest number dividing all of them exactly. For 48, 60 and 72 it is 12. The lowest common multiple is the smallest number they all divide into: 720 in that case.
How to find the GCD
For two numbers, GCD times LCM always equals their product — 12 × 240 = 48 × 60. That identity makes one easy once you have the other, and it is why the Euclidean algorithm alone is enough to get both. It stops working the moment there are three numbers: for 4, 6 and 10 the GCD is 2 and the LCM is 60, but 2 × 60 = 120 while the product is 240. There is no repaired version of the shortcut for three, which is why the LCM has to be built up a pair at a time, and that is what this tool does. The GCD is also the answer to a question that does not look like number theory: two cogs of 48 and 60 teeth return to their starting alignment after LCM(48, 60) = 240 teeth have passed, which is five turns of the small one and four of the large.
Questions
Twelve. Both divide by 12 exactly, and nothing larger does, so 48/60 in lowest terms is 4/5.
Yes; highest common factor and greatest common divisor are the same thing.
For two numbers, their product divided by their GCD. For more, take the LCM of the first two, then of that and the next.
No, and this is where people come unstuck. For 4, 6 and 10 it gives 120 against a product of 240.
The numbers are coprime: they share no factor other than one. Two integers picked at random are coprime about 61 per cent of the time.
Replace the larger number with the remainder of dividing it by the smaller, and repeat until the remainder is zero: 60 mod 48 = 12, then 48 mod 12 = 0, so the answer is 12.
Because the number of steps grows with the number of digits, not with the size of the numbers. Doubling the digits roughly doubles the work, where trial division would square it.