Greatest common divisor and Least common multiple

Greatest common divisor

If, for example, numbers $12$ and $16$ are given, a question that might arise is whether both numbers can be divided by the same number, i.e., whether they have a common divisor or they do not..$$\begin{gathered} 12=2\times 3\times 2 \\ 16=2\times 2\times 2\times 2 \end{gathered}$$In this case, both can be divided by number $2$, giving the result:$$\begin{gathered} 12÷2=6 \\ 16÷2=8 \end{gathered}$$But again, both numbers might be divided by $2$:$$\begin{gathered} 6÷2=3 \\ 8÷2=4 \end{gathered}$$This way, two large numbers $(12,16)$ have been simplified into two smaller ones $(3,4)$. In fact, this exercise can be done using fewer steps. The idea is to find a common divisor of two numbers that simplifies them as much as possible. In other words, the point is to find the largest divisor that is common to those two numbers, which is called the greatest common divisor ($g.c.d$).

Take two numbers, for instance, $40$ and $60$. The first thing to do is to factorise both numbers:

$\begin{array}{rcl}40& |& 2\\ 20& |& 2\\ 10& |& 2\\ 5& |& 5\\ 1& & \end{array}$

$\begin{array}{rcl}60& |& 2\\ 30& |& 2\\ 15& |& 3\\ 5& |& 5\\ 1& & \end{array}$

$$\begin{gathered} 40=2\times 2\times 2\times 5=2^3\times 5 \\ 60=2\times 2\times 3\times 5=2^2\times 3\times 5 \end{gathered}$$ Now, how to find the greatest common divisor ($g.c.d$): all the common prime divisors with the smallest exponent have to be multiplied.

In this case:

$g.c.d.(40,60)=2^2\times 5=20$

Least common multiple

We can do more things with the factorisations of numbers $40$ and $60$.

If one wants to find out the smallest multiple shared by those two numbers, the answer is based, as it was before, on a simple rule: in order to find the least common multiple ($l.c.m$) of two numbers, one has to multiply the common and not common prime divisors with the highest exponent.

Namely, in this case: $l.c.m.(40,60)=2^3\times 3\times 5=120$

Knowing the greatest common divisor of two numbers, we can calculate their least common multiple, and the other way round. One just has to follow this formula:$${\displaystyle l.c.m(a,b)=\frac{a\times b}{g.c.d.(a,b)}}$$