31.08 - Greatest common divisor and least common multiple

Greatest common divisor

Divisors: integers that can be divided by the same dividend to get a different integer Example: 12 has the divisors 1,2,3,4,6 and 12

Common divisors: integers that are divisors of two different dividends Example: 30 and 12 have the common divisors 1,2,3 and 6

The greatest common divisor of two number is like the name says: the biggest number of the common divisors of two numbers. The mathematical notation for this is: $gcd(x,y)$

Least common multiple

Multiples: integers that are dividends of a certain divisor Example: multiples of 3 are 3,6,9,12,15…

Common multiples: integers that are dividends of two different divisors Example: Common multiples of 4 and 6 are: 12,24,36

The least common multiple of two numbers is again like the name says: the smallest number of the common multiples of two numbers. The mathematical notation for this is: $lcm(x,y)$

Calculating the LCM and GCD

Calculating the least common multiple and greatest common divisor is actually really simple.

take 600 and 750 for example. Very big numbers right? It must be hard.. Start by calculating the prime factors for both.

$$\begin{array}{r}600=2^3\times 3^1\times 5^2\\ 750=2^1\times 3^1\times 5^3\end{array}$$

Now if we want to calculate the least common multiple, we go over each prime number and take the greatest exponent and calculate its solution.

$$\begin{array}{rl}{2}^{\boxed{3}}\times 3^{\boxed{1}}\times 5^2& =600\\ 2^1\times 3^1\times 5^{\boxed{3}}& =750\\ 2^3\times 3^1\times 5^3& =3000\end{array}$$
For the **greatest common divisor** we do the opposite, we go over each prime number and take the **smallest** exponent and calculate its solution. $$\begin{array}{rl}{2}^3\times 3^{\boxed{1}}\times 5^{\boxed{2}}& =600\\ 2^{\boxed{1}}\times 3^1\times 5^3& =750\\ 2^1\times 3^1\times 5^2& =150\end{array}$$

Explanation

The explanation goes as follows:
Take this division of primes with their exponents:

$$2^{a_1}\times 3^{a_2}\times 5^{a_3}\times 7^{a_4}÷2^{b_1}\times 3^{b_2}\times 5^{b_3}\times 7^{b_4}$$

Let’s write it as a fraction and omit the multiplication symbols for clarity:

$$\frac{2^{b_1}{3}^{b_2}{5}^{b_3}{7}^{b_4}}{2^{a_1}{3}^{a_2}{5}^{a_3}{7}^{a_4}}...$$

For this fraction to be an integer (a whole, valid number), $b_n$ has to be smaller or equal to $a_n$, where $n$ is the nth prime number. (you can check this for yourself with any number)

So since $b$ is our divisor, that means that for it to be the greatest common divisor, it has to be less than or equal to both exponents. Now look at the equation again:

$$\begin{array}{r}{2}^3\times 3^1\times 5^2=600\\ 2^1\times 3^1\times 5^3=750\\ 2^1\times 3^1\times 5^2=150\end{array}$$

The greatest common divisor is smaller or equal to both exponents.

The opposite is true for the least common multiple. In this case, both numbers have to be divisible by the multiple, so you can apply the principle in reverse; the greatest common divisor has to be greater than or equal to both exponents

$$\begin{array}{r}{2}^3\times 3^1\times 5^2=600\\ 2^1\times 3^1\times 5^3=750\\ 2^3\times 3^1\times 5^3=3000\end{array}$$

Cool, isn’t it?