To prove:
ab=gcd(a,b)*lcm(a,b)
We will show that they have the same set of divisors.
That is, we will show that the largest non-negative power
of any prime which is a factor of ab is also the largest
non-negative power of that prime which is a factor of
gcd(a,b)lcm(a,b).
let p be any prime. Then c and d exist so that
c*p^n = a and d*p^m = b where n and m are maximum
so that neither c nor d is divisible by p.
(Remark: either n or m or both could be zero)
Then ab = c*p^n*d*p^m = c*d*p^(n+m)
Without loss of generality, let us assume m < n
Then gcd(a,b) = e*p^m, and lcm(a,b) = f*p^n, where
neither e nor f is divisible by p. Therefore
gcd(a,b)lcm(a,b) = (e*p^m)(f*p^n) = ef*p^(m+n)
Therefore the largest power of p which is a factor of
gcd(a,b)lcm(a,b) is p^(m+n).
Also the largest power of p which is a factor of
ab is p^(m+n).
Since this is true for any prime p, there can be no
power of a prime which one contains as a factor that
the other doesn't also contain as a factor. And, let's
face it, every factor is a power of a prime or the
product of powers of primes, if we count the 0 power of
a prime, which is 1.
Edwin
