Divisors & Multiples•Step-by-Step

GCD & LCM Calculator

Find the Greatest Common Divisor (GCD / HCF) and Least Common Multiple (LCM) with complete step-by-step division and prime factor breakdowns.

Greatest Common Divisor (GCD / HCF)
12
The largest positive integer that divides all inputs evenly without remainder.
Least Common Multiple (LCM)
720
The smallest positive integer that is divisible by all specified inputs.

Prime Factorization Method

48 = 2^4 × 3
180 = 2^2 × 3^2 × 5

Euclidean Algorithm (Division Steps)

48 = 180 × 0 + 48
180 = 48 × 3 + 36
48 = 36 × 1 + 12
36 = 12 × 3 + 0
Last non-zero remainder = 12

Euclidean Steps vs. Prime Factors

For small numbers, prime factor trees (like 24 = 2³ × 3) are quick to write down and compare. For much larger numbers, prime factoring takes a long time, but Euclid's division method finds the GCD in just a handful of remainder steps regardless of how large the numbers are.

Frequently Asked Questions

What is the Greatest Common Divisor (GCD or HCF)?

The GCD (also known as the Highest Common Factor or HCF) is the largest positive integer that divides two or more given numbers without leaving a remainder. For example, GCD(48, 180) = 12.

What is the Least Common Multiple (LCM)?

The LCM is the smallest positive integer that is divisible by all given numbers. For example, LCM(48, 180) = 720.

How does the Euclidean algorithm find the GCD?

The Euclidean algorithm divides the larger number by the smaller number and takes the remainder. It repeats by dividing the previous divisor by the remainder until the remainder is 0. The final non-zero divisor is the GCD.

What is the relationship between GCD and LCM?

For any two positive integers a and b, their product equals the product of their GCD and LCM: a × b = GCD(a, b) × LCM(a, b). This means LCM(a, b) = (a × b) ÷ GCD(a, b).