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,

(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.

If you are reading this, your browser is not set to run Java applets. Try IE11 or Safari and declare the site https:///www.cut-the-knot.org as trusted in the Java setup.

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., 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,

	MS∩T(s)	= min (MS(s), MT(s))
	MS∪T(s)	= max (MS(s), MT(s))

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.

For other members of S and T we have

	MS(5)	= 1,
	MT(5)	= 2,
	MS(7)	= 0,
	MT(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 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

	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.)

Related material Read more...
	Factoring with the Factor Tree
	GCD and LCM by Plain Factorization
	Common Multiples and the Least Common Multiple
	GCD(M, N) x LCM(M, N) = M x N
	Divisibility Criteria
	Euclid's Algorithm
	Algorithm for Computing the LCM
	Factors And Multiples
	Two Properties of Greatest Common Divisor
	Properties of GCD and LCM
	A Line in a Square Grid
	Number of Factors of an Integer
	Extension of Euclid's Game

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

Copyright © 1996-2018 Alexander Bogomolny