Euclidean Algorithm Calculator (GCD)

Math

The Euclidean Algorithm Calculator finds the greatest common divisor (GCD) of two integers using repeated division, and also gives the least common multiple (LCM). Enter two whole numbers.

Formula

gcd(a, b) = gcd(b, a mod b), repeated until the remainder is 0
  • The last non-zero remainder is the GCD.
  • LCM = a × b ÷ GCD.

48 and 36

Inputs
  • First Number: 48
  • Second Number: 36

48 = 1×36 + 12, 36 = 3×12 + 0, so GCD = 12 and LCM = 144.

Frequently asked questions

What is the Euclidean algorithm?
An efficient method to find the GCD by repeatedly replacing the larger number with the remainder of dividing the two.