You are not logged in.
Pages: 1
Anyone know how to prove this:
gcd(a, b)*lcm(a, b) = a*b
I tried a few different ways with no luck. I'll post a few of my attempts a bit later when I get the chance, to see if it sparks an idea in anyone else.
"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."
Offline
Alright, captain. Consider the set of all primes that divide a and/or b:
Then for some suitable nonnegative exponents
we have
Now p[sup]q[/sup] divides p[sup]r[/sup] if and only if q ≤ r, so
But we can also tell that for ab ≠ 0,
Now consider the product
Also, consider the product
Because of the fact that
we have
Thus we can conclude that the two products are equal, so
Is that good enough?
Last edited by Zhylliolom (2006-07-29 15:05:30)
Offline
It certainly seems valid, but it also seems too complex. Maybe it's just me, but I hate dealing with primes when I don't have to.
So I went back, and one of my methods was to show that lcm(a, b) = ab / gcd(a, b), which would suffice for this proof. But in my work, I went in circles because I didn't realize a little trick. So try this:
Let l = lcm(a, b) and g = gcd(a, b). Also, let n = ab / g for some integer n, since g must divide both a and b. What we wish to show is that n = l.
Since g = gcd(a, b), it stands that g | a and g | b. So let a = g*i and b = g*j for some integers i and j. Since a | l and b | l, it must be that ga'b' | l. But notice that n = ab / g = ga'gb' / g = ga'b'. So n | l and so n <= l.
Also, since g | a and g | b, it must be that (a/g) and (b/g) are integers. Thus, n = a(b/g) and n = (a/g)b, so a | n and b | n. So n is a multiple of a and b. Since l is the least such multiple, it must be that l <= n.
So l = n.
"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."
Offline
Let
If we use the identities:
pp: lots of LaTeX!
Last edited by krassi_holmz (2006-08-23 20:05:30)
IPBLE: Increasing Performance By Lowering Expectations.
Offline
Pages: 1