Maths Number theory

GCD calculator

Numbers

Greatest common divisor 12

Euclid algorithm across every value

Lowest common multiple 720

Numbers entered 3

GCD × LCM = the product, for two numbers

Euclid algorithm is 2,300 years old and still optimal

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

1 Enter two or more numbers.

2 Read the greatest common divisor and lowest common multiple.

3 Use the GCD to simplify a fraction.

4 Use the LCM to find a common denominator.

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 does not extend directly to three or more numbers, where the LCM has to be built up pairwise, which is what this tool does.

Questions

What is the GCD of 48 and 60? −

Twelve. Both divide by 12 exactly, and nothing larger does.

Is HCF the same as GCD? +

How do I find the LCM? +

What if the GCD is 1? +

How does Euclid algorithm work? +

Was this tool any good?

INTERNAL SIGNAL ONLY · WE USE IT TO FIND TOOLS WORTH REBUILDING