Results 1 to 3 of 3

Math Help - 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:

    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
    Last edited by loopology; February 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 ? \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 ...
    Last edited by Bacterius; February 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

    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
    Last edited by loopology; February 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: July 23rd 2010, 07:04 AM
  2. Is this proof correct?
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: March 11th 2010, 12:13 PM
  3. Did I do this proof correct?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 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: November 9th 2006, 08:24 PM
  5. Is proof correct?
    Posted in the Algebra Forum
    Replies: 13
    Last Post: January 13th 2006, 10:35 AM

Search Tags


/mathhelpforum @mathhelpforum