maths.free › Number Theory › GCD and LCM
GCD and LCM
Euclid's algorithm and the identity gcd × lcm = a × b.
The greatest common divisor is found without factoring at all: replace the larger number by the remainder when it is divided by the smaller, repeat, and the last non-zero remainder is the gcd. That is Euclid's algorithm, 2,300 years old and still what your computer uses. The lcm follows from gcd × lcm = a × b.
Worked example: gcd(48, 18)
Step by step
- \gcd(48, 18)
Use Euclid's algorithm: replace the larger number by its remainder on division by the smaller, until the remainder is 0.
- 48 = 2 \times 18 + 12
Divide 48 by 18: quotient 2, remainder 12.
- 18 = 1 \times 12 + 6
Divide 18 by 12: quotient 1, remainder 6.
- 12 = 2 \times 6 + 0
Divide 12 by 6: quotient 2, remainder 0.
- \gcd(48, 18) = 6
The last non-zero remainder is 6.
Reveal the answer
Try your own
More in Number Theory
Prime factorisationPrime numbersModular arithmeticDivisorsSequencesNumber bases