GCD and LCM

Divisors and multiples

Divisors and Greatest Common Divisors (GCD)

Divisors

The divisors \(d\) of a natural number \(n\) are the natural numbers such that \(\dfrac{n}{d}\in \mathbb{N}\).

For example, for \(6\) the divisors are \(1, 2, 3, 6\).

Divisors cannot be bigger than the number they are dividing.

Universal divisors

For any number \(n \in \mathbb{N}^+\):

\(\dfrac{n}{n}=1\)

\(\dfrac{n}{1}=n\)

Both \(1\) and \(n\) are divisors.

Common divisors

A common divisor is a number which is a divisor to two supplied numbers.

Greatest common divisor

The greatest common divisor of \(2\) numbers is as the name suggests.

So \(GCD(18,24)=6\)

Multiples and Lowest Common Multiples (LCM)

Multiples

The multiple of a number is it added to itself iteratively.

The multiples of \(18\) for example are:

\([18,36,54,72,90,...]\)

And for \(24\):

\([24,48,72,96,120,...]\)

Common multiples

Lowest common multiple

The lowest common multiple of \(2\) numbers is again as the name suggests.

So \(LCM(18,24)=72\).

Coprimes

Also known as relatively prime.

Greatest common divisor is 1.