# Thread: lcm, gcd proof correct?

1. ## lcm, gcd proof correct?

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

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

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