GCD and LCM Explained: How to Find HCF and LCM (3 Methods)

Two of the most useful ideas in arithmetic are the greatest common divisor (GCD), also called the highest common factor (HCF), and the least common multiple (LCM). They power everything from simplifying fractions to working out when two buses next arrive together.

Definitions

GCD / HCF: the largest whole number that divides all the given numbers exactly.
LCM: the smallest positive whole number that all the given numbers divide into exactly.

For 12 and 18: GCD = 6, LCM = 36.

Method 1: Listing (small numbers)

Factors of 12: 1, 2, 3, 4, 6, 12 Factors of 18: 1, 2, 3, 6, 9, 18 Largest shared factor → GCD = 6

Multiples of 12: 12, 24, 36, 48… Multiples of 18: 18, 36, 54… Smallest shared multiple → LCM = 36

Fine for small numbers; painful for anything bigger.

Method 2: Prime factorisation

Break each number into primes. MathKit’s prime factorisation tool does this instantly.

12 = 2² × 3
18 = 2 × 3²
GCD: take each common prime at its lowest power → 2¹ × 3¹ = 6
LCM: take every prime at its highest power → 2² × 3² = 36

Three numbers: 12, 18 and 30 (30 = 2 × 3 × 5)

GCD = 2 × 3 = 6
LCM = 2² × 3² × 5 = 180

Method 3: Euclid’s algorithm (fast for big numbers)

Over 2,300 years old and still what computers use. Repeatedly replace the larger number with the remainder of dividing it by the smaller:

GCD(1071, 462)

1071 = 2 × 462 + 147
462 = 3 × 147 + 21
147 = 7 × 21 + 0

The last non-zero remainder is 21, so GCD = 21.

The GCD–LCM shortcut

For two numbers:

LCM(a, b) = (a × b) ÷ GCD(a, b)

LCM(1071, 462) = 1071 × 462 ÷ 21 = 23,562.

Where GCD and LCM are used

Simplifying fractions (GCD)

Divide top and bottom by their GCD: 84/126 → GCD 42 → 2/3.

Adding fractions (LCM)

The lowest common denominator is the LCM of the denominators: 1/4 + 1/6 → LCM 12 → 3/12 + 2/12 = 5/12.

Scheduling (LCM)

Bus A comes every 12 minutes, bus B every 18. If they leave together, they next coincide in LCM(12, 18) = 36 minutes.

Tiling and cutting (GCD)

The largest square tile that exactly covers a 240 cm × 180 cm floor is GCD(240, 180) = 60 cm.

Gears and cycles (LCM)

Two gears with 24 and 36 teeth return to their starting alignment after LCM(24, 36) = 72 teeth have passed.

Quick facts

GCD of two consecutive numbers is always 1. They are coprime.
If one number divides the other, the GCD is the smaller and the LCM the larger.
GCD(a, 0) = a.

MathKit calculates GCD and LCM for any list of whole numbers using exact big-integer arithmetic, so even very large values come out correct. Pair this with How to Solve Quadratic Equations: 3 Methods With Worked Examples when factoring is involved.