GCD and LCM via Factor Tree

Given two integers, N and M such that M divides N then M = gcd(N, M) and M = lcm(N, M). So, in this case,

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.

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., 12 = 2²3 while the set of prime factors is {2, 3}, missing another 2. The way around that problem is to consider what is known as a multiset - a collection that allows repetition, like {2, 2, 3} which, as a multiset has three elements, two of which are equal.

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,

For example, compare two multisets, S = {2, 2, 5} and T = {2, 5, 5, 7}. The multiplicity of 2 in S is 2 and in T it's 1: M_S(2) = 2, M_T(2) = 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

Taking the largest of the two multiplicities gives the union

In this example, sets S and T are the sets of all prime factors of N = 20 and M = 350, respectively. Let's write Π_R for the product of all the elements of a multiset R (assuming, of course, that all are integers.) Then, in our example, N = Π_S and M = Π_T. The convenience of these notions stems from the following formulas result:

Assume, in general, that for two multisets S and T of integers, N = Π_S and M = Π_T. Then

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:

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| |Store|