Results 1 to 5 of 5

Thread: Given this modification to Euclid's algorithm, prove that z = 2 ⋅ LCM(a,b).

  1. #1
    s3a
    s3a is offline
    Super Member
    Joined
    Nov 2008
    Posts
    607

    Given this modification to Euclid's algorithm, prove that z = 2 ⋅ LCM(a,b).

    PROBLEM STATEMENT:
    dpaste: 1MMV7ZZ

    BOOK'S SOLUTION:
    dpaste: 2S4900N

    How does the author go from m ⋅ u + n ⋅ v = 2ab and GCD(a,b) ⋅ LCM(a,b) = ab to z = 2 * LCM(a,b)?

    All I can think of is (m ⋅ u + n ⋅ v)/2 = GCD(a,b) ⋅ LCM(a,b) ⇒ (m ⋅ u + n ⋅ v) / GCD(a,b) = 2 ⋅ LCM(a,b). Is z = (m ⋅ u + n ⋅ v) / GCD(a,b)? If so, could someone please elaborate on the book's solution for that part? I don't see how one would go from it either being the case that z = u or that z = v (from the Pascal-style pseudo-code) to it being the case that z = (m ⋅ u + n ⋅ v) / GCD(a,b). Otherwise, if I'm completely off, could someone please just generally clarify how to solve this problem?

    I would GREATLY appreciate it if someone could help me fully understand the solution to this problem!

    P.S.
    Also, what's the significance of all this? In other words, in addition to the solving of the problem itself, what's the big-picture takeaway from all this? Like, in simple terms, what was E. Dijkstra's motivation for doing this?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    1,124
    Thanks
    467

    Re: Given this modification to Euclid's algorithm, prove that z = 2 ⋅ LCM(a,b).

    Here's the algorithm written as an actual C function (even if you don't know C, I hope you can follow):

    Code:
    /* upon entry a and b are POSITIVE! recturn is 2lcm(a,b) */
    int lcm2(int a, int b) {
       int m = a, n = b, u = b, v = a, z;
       while (m != 0 && n != 0) {
          if (m >= n) {
             m = m - n;
             v = v + u;
          } else {
             n = n - m;
             u = u + v;
          }
       }
       if (m == 0) { // gcd(a,b) is then n
          z = v;
       } else { // gcd(a,b) is now m
          z = u;
       }
       return(z);
    }
    This is an exercise on loop invariants. A loop invariant is a statement true upon entry to a loop and it remains true after each iteration of the loop. For the while loop in the above function, there are 2 invariants:
    1. mu + nv = 2ab
    This is obviously true prior to execution of the while loop. Suppose m>=n. Then the new value of the expression mu+nv is (m-n)u + n(u+v) = mu + nv =2ab (in these equations m, n, u and v are the "old" values before execution of the loop body).

    2. gcd(m,n) = gcd(a,b). Clear upon entry. You need to show if x >= y, then gcd(x,y) = gcd(x-y,y). I leave this to you.

    Now at termination of the while loop, exactly one of m and n is 0; you need to convince yourself of this. Suppose m = 0. Then gcd(a,b)=gcd(0,n)=n (last equation should be clear). Thus 2ab=mu+nv=nv=gcd(a,b)z or
    z = 2ab/gcd(a,b) = 2lcm(a,b). If n is 0 at loop termination, the proof is entirely similar.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    s3a
    s3a is offline
    Super Member
    Joined
    Nov 2008
    Posts
    607

    Re: Given this modification to Euclid's algorithm, prove that z = 2 ⋅ LCM(a,b).

    Thank you very much, johng!

    Your reply answered the most important question(s) of my post, but the book seems to imply that this modification (or some similar variation of it) to Euclid's algorithm was done by E. Dijkstra (because it says "(E. Dijkstra)," right before giving the problem statement), who probably had a good reason for doing it (it=adding the three variables u, v, z to Euclid's algorithm). Would you happen to know what that reason was, by any chance? When I search online, all I seem to find is an algorithm for finding the shortest path in a graph.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    s3a
    s3a is offline
    Super Member
    Joined
    Nov 2008
    Posts
    607

    Re: Given this modification to Euclid's algorithm, prove that z = 2 ⋅ LCM(a,b).

    Quote Originally Posted by s3a View Post
    Thank you very much, johng!

    Your reply answered the most important question(s) of my post, but the book seems to imply that this modification (or some similar variation of it) to Euclid's algorithm was done by E. Dijkstra (because it says "(E. Dijkstra)," right before giving the problem statement), who probably had a good reason for doing it (it=adding the three variables u, v, z to Euclid's algorithm). Would you happen to know what that reason was, by any chance? When I search online, all I seem to find is an algorithm for finding the shortest path in a graph.
    Oh, wait, the algorithm is just Dijkstra's and not Euclid's, right? It's just that Dijkstra's algorithm, which uses subtraction, is based on a similar algorithm, which is Euclid's, which uses the modulo operator, and the addition of the u,v and z variables is simply for this textbook's problem (and this aforementioned addition is not a variation of any well-known problem), right?

    Source:
    "GCD Algorithm 2: Euclid's Algorithm" and "GCD Algorithm 3: Dijkstra's Algorithm" from:
    Recursive Algorithms
    Last edited by s3a; Dec 5th 2017 at 04:51 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    1,124
    Thanks
    467

    Re: Given this modification to Euclid's algorithm, prove that z = 2 ⋅ LCM(a,b).

    This algorithm is somewhat similar to the "binary gcd algorithm"; you might be interested in the Wikipedia article: https://en.wikipedia.org/wiki/Binary_GCD_algorithm
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclid Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Jan 15th 2012, 12:32 PM
  2. Euclid's Algorithm
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: Mar 29th 2009, 05:54 AM
  3. Another GCD using Euclid's Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Sep 23rd 2008, 10:03 AM
  4. Euclid's algorithm
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Aug 3rd 2008, 06:18 AM
  5. Euclid Algorithm
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Apr 10th 2008, 06:28 AM

/mathhelpforum @mathhelpforum