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

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

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

**Zhylliolom****Real Member**- Registered: 2005-09-05
- Posts: 412

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

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

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

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,906

Let

If we use the identities:

,

we can have interestiong results:

pp: lots of LaTeX!

*Last edited by krassi_holmz (2006-08-23 20:05:30)*

IPBLE: Increasing Performance By Lowering Expectations.

Offline

Pages: **1**