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

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

Proof:

$\displaystyle lcm(b,c) / gcd(a, lcm(b, c)) = lcm(a, lcm(b, c)) / a;$
Substitution: $\displaystyle k:= lcm(b, c);$
$\displaystyle k / gcd(a, k) = lcm(a, k) / a;$
$\displaystyle 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 ? $\displaystyle \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 $\displaystyle gcd(a, b, c) = 1$, then the equality holds, because $\displaystyle gcd(a, lcm(b, c)) = 1$, and $\displaystyle 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

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

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

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

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

which is a valid connection between $\displaystyle lcm$ and $\displaystyle 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 $\displaystyle lcm$, i.e. $\displaystyle lcm(b, c, d, e, f, g, ...)$ which happens to be what I actually need, not just two arguments (i.e. $\displaystyle lcm(b, c)$).

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