Primes and the Euclidean algorithm

Prime decomposition

A prime has exactly two factors: 1 and itself. Composite numbers can be broken into smaller factors, and if you keep breaking until only primes remain — by a factor tree, or by repeatedly dividing by 2, then 3, then 5, and so on — you get the prime decomposition, usually written in index form: $90 = 2 \times 3^2 \times 5$.

The fundamental theorem of arithmetic says every number has exactly one prime decomposition, no matter how you find it. This is also why 1 is not counted as a prime: allowing factors of 1 would create endless “different” decompositions.

LCM and GCD from primes

Write each number as a product of primes first, then:

• gcd (HCF): take only the primes common to both, each at its lowest index.
• lcm: take every prime that appears, each at its highest index.

For $18 = 2 \times 3^2$ and $60 = 2^2 \times 3 \times 5$:

$$\gcd(18, 60) = 2 \times 3 = 6 \qquad \mathrm{lcm}(18, 60) = 2^2 \times 3^2 \times 5 = 180$$

Coprime numbers

If two numbers share no prime factors, their gcd is 1 and they are called coprime (or relatively prime) — for example $21 = 3 \times 7$ and $40 = 2^3 \times 5$. For coprime numbers the lcm is simply their product.

The Euclidean algorithm

Factorising big numbers is hard work, and the Euclidean algorithm finds a gcd without any factorising. The idea: any common divisor of two numbers also divides their difference — and therefore the remainder after division. So repeatedly replace the larger number with the remainder:

• $\gcd(252, 105)$: $252 \div 105 = 2$ remainder $42$, so look at $(105, 42)$
• $105 \div 42 = 2$ remainder $21$, so look at $(42, 21)$
• $42 \div 21 = 2$ remainder $0$ — stop.

The gcd is the last positive remainder: $\gcd(252, 105) = 21$.

Choose your tool: prime decomposition when the numbers factorise easily, the Euclidean algorithm when they are large or awkward.