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

You are not logged in.

#1 2006-07-29 13:22:21

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

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

Offline

#2 2006-07-29 13:56:58

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

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

#3 2006-07-29 17:14:43

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

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

Offline

#4 2006-08-23 19:44:31

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

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-23 20:05:30)


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

Board footer

Powered by FluxBB