# GCD and LCM via Factor Tree

Given two integers, N and M such that M divides N then

(1) | N × M = gcd(N, M) × lcm(N, M). |

Perhaps, surprisingly, this is true for any two integers. The applet below sheds more light on why this is so.

Here we use the Factor trees to find and then compare the prime factorizations of the two numbers.

What if applet does not run? |

I would like to consider the collections of all the factors of the two numbers, N and M. These are not sets in the common sense of the word because some factors may be repeated, e.g., *multiset* - a collection that allows repetition, like

In a multiset, the number of inclusions of a particular element is called its *multiplicity*. Quite consistently, if an element is absent from a multiset, its multiplicity there is zero. The notion of multiplicity is instrumental in extending set operations, like union and intersection, to the multisets.

If M_{S}(s) and M_{T}(s) are the multiplicities of s in S and T, then, by definition,

M_{S∩T}(s) | = min (M_{S}(s), M_{T}(s)) | |

M_{S∪T}(s) | = max (M_{S}(s), M_{T}(s)) |

For example, compare two multisets, _{S}(2) = 2,_{T}(2) = 1.

M_{S}(5) | = 1, | |

M_{T}(5) | = 2, | |

M_{S}(7) | = 0, | |

M_{T}(7) | = 1. |

Each of the numbers, 2, 5, 7, has two multiplicities: one in S, another in T. Taking, in each case, the smallest of the two gets us the *intersection*

S∩T | = {2, 5}. |

Taking the largest of the two multiplicities gives the *union*

S∪T = {2, 2, 5, 5, 7}.

In this example, sets S and T are the sets of all prime factors of _{R} for the product of all the elements of a multiset R (assuming, of course, that all are integers.) Then, in our example, _{S}_{T}.

Assume, in general, that for two multisets S and T of integers, _{S}_{T}.

gcd(N, M) | = Π_{S∩T} and | |

lcm(N, M) | = Π_{S∪T}. |

So, in our example, N = 20, M = 350, gcd(N, M) = 10, lcm(N, M) = 700. (1) is obviously true. In general, (1) is the consequence of the foregoing definitions of operations on multisets and the properties of maximum and minimum of two numbers:

(2) | min(s, t) + max(s, t) | = s + t, |

which holds simply because of the two given (distinct) numbers one is larger and the other is smaller. (The above also holds if the two numbers are equal.)

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny69637015