Results 1 to 3 of 3

Thread: lcm, gcd proof correct?

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    2

    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
    Last edited by loopology; Feb 26th 2010 at 06:35 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    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 ...
    Last edited by Bacterius; Feb 26th 2010 at 03:18 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2010
    Posts
    2
    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
    Last edited by loopology; Feb 26th 2010 at 06:47 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Is this proof correct?
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Jul 23rd 2010, 07:04 AM
  2. Is this proof correct?
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: Mar 11th 2010, 12:13 PM
  3. Did I do this proof correct?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 3rd 2007, 08:19 PM
  4. Proof of n^5 = n mod 5 .. is this correct?
    Posted in the Algebra Forum
    Replies: 4
    Last Post: Nov 9th 2006, 08:24 PM
  5. Is proof correct?
    Posted in the Algebra Forum
    Replies: 13
    Last Post: Jan 13th 2006, 10:35 AM

Search Tags


/mathhelpforum @mathhelpforum