   SEARCH HOME Math Central Quandaries & Queries  Question from Brenda, a student: why does multiplying lcm of (n,s) by gcd (n,s) give n times s. when (n,s) are any two numbers? Brenda,

The easiest way is to look at the canonical representations of n and s as a product of primes (generalize the content of my note on the MathCentral website), but if you're not familiar with that we can do it as follows.

I'll use (n,s) for the gcd of n and s and use [n,s] for the lcm of n and s.

Write n = (n,s)r and s = (n,s)t; then (t,r)=1 and ns = (n,s)r(n,s)t. Thus ns/(n,s) = r(n,s)t which is clearly a multiple of both n and s.

Suppose there is a smaller integer, m = [n,s], which both n and s divide, then m = un and m = vs for some integers u and v. Write (n,s) = nx + sy for some integers x and y (this can be done as a consequence of the Euclidean Algorithm) then m/(ns/(n,s)) = m(n,s)/ns = (mnx+msy)/ns = (vsnx+unsy)/ns = vx + sy, an integer, thus m is divisible by ns/(n,s) and m ≥ ns/(n,s), a contradiction.

Penny.     Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.