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 http:///www.cut-the-knot.org as trusted in the Java setup.

GCD and LCM via Factor Tree


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 MS(s) and MT(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: MS(2) = 2, MT(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| |Store|

    Copyright © 1996-2017 Alexander Bogomolny

     62012892

    Search by google: