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

1. ## 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?

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

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

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

Originally Posted by s3a
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

5. ## 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