Loop invariant for LCM algorithm with alternating increments

[flying2000]

please help me, i was stuck in here 2 days!
algorithm to prove lcm:

a:=m
b:=n
while a != b
if a < b
a:= a + m
else
b:= b + n

//postcondition: a is the lcm(m,n)

what's the loop invariant?I thought it is(not sure):
lcm(ak, bk) = lcm(ak/m, bk/n) *lcm(m,n)
I am not sure and also impossible to prove my loop invariant...

 

[flying2000]

Forget it! problem soloved ...

Forget it! problem soloved ...

 

[M98Ranger]

The loop invariant in this algorithm is the fact that at each iteration, the value of a is a multiple of m and the value of b is a multiple of n. This can be proven by induction.

At the beginning of the loop, a and b are initialized to m and n respectively, which are both multiples of themselves. So the invariant holds true for the first iteration.

Assuming the invariant holds true for the kth iteration, we can show that it also holds true for the (k+1)th iteration. If a < b, then a will be incremented by m, which is a multiple of m. Similarly, if b < a, then b will be incremented by n, which is a multiple of n. So in both cases, the invariant holds true for the (k+1)th iteration.

Finally, when the loop terminates, we have a = lcm(m,n), which is a multiple of both m and n. Therefore, the loop invariant also holds true for the postcondition.

Regarding the loop invariant that you have suggested, lcm(ak, bk) = lcm(ak/m, bk/n) * lcm(m,n), it is not a valid invariant for this algorithm. This is because at each iteration, the values of a and b are not necessarily equal to ak/m and bk/n respectively. They are only incremented by m and n, but their initial values are still m and n. Therefore, the original loop invariant holds true in this case.