Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

## #1 2006-07-30 11:22:21

Ricky
Moderator

Offline

### gcd and lcm

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..."

## #2 2006-07-30 11:56:58

Zhylliolom
Real Member

Offline

### Re: gcd and lcm

Alright, captain. Consider the set of all primes that divide a and/or b:

Then for some suitable nonnegative exponents

we have

Now pq divides pr 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-30 13:05:30)

## #3 2006-07-30 15:14:43

Ricky
Moderator

Offline

### Re: gcd and lcm

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..."

## #4 2006-08-24 17:44:31

krassi_holmz
Real Member

Offline

### Re: gcd and lcm

Let

If we use the identities:

,
we can have interestiong results:

pp: lots of LaTeX!

Last edited by krassi_holmz (2006-08-24 18:05:30)

IPBLE:  Increasing Performance By Lowering Expectations.