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.