GCD(M, N) × LCM(M, N) = M × N
The applet below attempts to demonstrate an engaging property of GCD (the Greatest Common Divisor) and LCM (the Least Common Multiple) of two number, to boot,
|(1)||GCD(M, N) × LCM(M, N) = M × N,|
where M and N are two natural numbers.
Given two (natural) numbers M and N, we may form a grid M×N rectangle. Call it R. G =
In the applet, the leftmost M×N rectangle represents R tessellated by G×G squares. The number of such squares is
Call it S = (M/G)×(N/G). Obviously,
In the applet, there are two additional rectangles of the same size as R. These suggest the two ways in which L can be obtained: (M/G)×N and M×(N/G). In one, the G×G squares are split vertically into G×1 rectangles. In the other, they are split horizontally into 1×G rectangles. The total number of small rectangles in both cases is L.
|What if applet does not run?|
I claim that
The relation GCD(M, N) × LCM(M, N) = M × N, has its root in the obvious identity
|(2)||A + B = min(A, B) + max(A, B),|
because, if the numbers are not equal, then one of them is smaller and one is larger than the other. (If the number are equal, the (2) holds vacuously.)
We shall use the prime number decomposition of N and M:
M = paqb· ... · rc,|
N = pαqβ· ... · rγ.
For example, for M = 12 and N = 10,
M = 223150,
N = 213051.
We see that it is always possible to write both M and N as the products of the same prime factors, albeit with different exponents. Some of the exponents will need to be zero.
Now, both GCD(M, N) and LCM(M, N) are products of the same prime factors where the exponents in G are the least of the corresponding two, whilst in L they are the largest:
GCD(M, N) = p min(a, α) q min(b, β)· ... · r min(c, γ),
LCM(M, N) = p max(a, α) q max(b, β)· ... · r max(c, γ).
Now, (2) thus insures that (1) holds. To continue the example:
GCD(12, 10) = 213050 = 2,
LCM(12, 10) = 223151 = 60.
Naturally, 12×10 = 2×60.
Copyright © 1996-2018 Alexander Bogomolny