lcm, gcd proof correct?

**loopology** · February 26th 2010, 03:43 AM

I believe to have proven something that I need for an algorithm I'm developing.

The proposition is:

$lcm(b, c) / gcd(a, lm(b, c)) = lcm(a, b, c) / a;$

Proof:

$lcm(b,c) / gcd(a, lcm(b, c)) = lcm(a, lcm(b, c)) / a;$
Substitution: $k:= lcm(b, c);$
$k / gcd(a, k) = lcm(a, k) / a;$
$a \times k = lcm(a, k) \times gcd(a, k);$ // see Greatest common divisor - Wikipedia, the free encyclopedia

Is this correct?
Thank you
Bernhard

**Bacterius** · February 26th 2010, 04:01 AM

Hello Bernhard,
Is the == sign a congruence ? $\equiv$ ? If yes, what is the modulus considered ? Because a congruence without modulus is meaningless.
(Funny like we all get the same idea when we lack an congruence sign on the computer

)

Out of curiosity, what is the algorithm you are developing about, if not too indiscrete ?

EDIT : ah, no, I get it, this is the conditional equivalence sign in the C language. Well obviously, if $gcd(a, b, c) = 1$ , then the equality holds, because $gcd(a, lcm(b, c)) = 1$ , and $lcm(a, b, c) = a \times lcm(b, c)$ . I don't really get your proof (what does it show ? a proof needs words), but I think you might get somewhere if you consider dividing the right hand side with the left hand side ...

**loopology** · February 26th 2010, 07:32 AM

Hi Ray

Thanks for looking at my proof. Sorry for using a confusing notation (corrected it now).
I'm trying to prove that

$lcm(b, c) / gcd(a, lm(b, c)) = lcm(a, b, c) / a;$

holds, i.e. that $lcm(b, c) / gcd(a, lm(b, c))$ can be calculated by $lcm(a, b, c) / a;$

I believe to have proven the equivalence by applying what I hope are legal transformations to reach the equation

$a \times k = lcm(a, k) \times gcd(a, k);$

which is a valid connection between $lcm$ and $gcd$ (see Greatest common divisor - Wikipedia, the free encyclopedia) The cool thing about the substitution is that the equivalence applies for an arbitrary number of arguments to $lcm$ , i.e. $lcm(b, c, d, e, f, g, ...)$ which happens to be what I actually need, not just two arguments (i.e. $lcm(b, c)$ ).

The algorithm is used for calculating BPMs to represent arbitrary rhythmic patterns. See Boss Dr.Beat DB-88

Thread: lcm, gcd proof correct?

LinkBack

Thread Tools

Display

lcm, gcd proof correct?

Similar Math Help Forum Discussions

Is this proof correct?

Is this proof correct?

Did I do this proof correct?

Proof of n^5 = n mod 5 .. is this correct?

Is proof correct?

Search Tags