What is the fastest way to find a greatest common divisor by hand?

The Euclidean algorithm: replace the larger number with its remainder against the smaller, and repeat until one is zero. For 252 and 198 that is 252 mod 198 = 54, 198 mod 54 = 36, 54 mod 36 = 18, 36 mod 18 = 0, so the answer is 18. It needs no factorisation at all.

How are the GCD and the LCM related?

Their product is the product of the two numbers: gcd(a,b) x lcm(a,b) = a x b. So once you have one, the other is a division away.

Math & Statisticsnumber theory

GCD / HCF Calculator

Greatest common divisor and lowest common multiple of any list of integers, by the Euclidean algorithm.

Also called: hcf calculator, greatest common factor, highest common factor.

Greatest common divisor

The GCD of 3 numbers is 6, and their LCM is 5,040.

Lowest common multiple

5,040

Numbers given

How this is calculated

Method and background

How this is calculated

Euclid's algorithm replaces the larger number with the remainder of dividing it by the smaller, repeatedly, until one is zero. Extending to a list is just applying it pairwise. The LCM follows from the identity that the product of two numbers equals their GCD times their LCM.

euclidean algorithm, applied pairwise

a, b: The two numbers

Worked examples

Each of these is asserted on every build. If a change to the engine ever moved one of these answers, the build would fail before the page could print it.

gcd of 48, 180, 210

Numbers: 48, 180, 210

Greatest common divisor6

independently verified by prime factorisation

Open this example

coprime numbers have gcd 1

Numbers: 9, 28

Greatest common divisor1

boundary

Open this example

a single number is its own gcd

Numbers: 17

Greatest common divisor17

degenerate case

Open this example

Frequently asked questions

What is the fastest way to find a greatest common divisor by hand?: The Euclidean algorithm: replace the larger number with its remainder against the smaller, and repeat until one is zero. For 252 and 198 that is 252 mod 198 = 54, 198 mod 54 = 36, 54 mod 36 = 18, 36 mod 18 = 0, so the answer is 18. It needs no factorisation at all.
How are the GCD and the LCM related?: Their product is the product of the two numbers: gcd(a,b) x lcm(a,b) = a x b. So once you have one, the other is a division away.