Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: √ ∞ ≠ ≤ ≥ ≈ ⇒ ∈ Δ θ ∴ ∑ ∫ π -

Login

Username

Password

Not registered yet?

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

Board footer

Powered by FluxBB