- #1

- 40

- 0

## Main Question or Discussion Point

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

Another loop invariant I thought is "ak=qm and bk=rn",but I don't know how to

show it's the lcm of m and n,

Thanks in advance!!

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

Another loop invariant I thought is "ak=qm and bk=rn",but I don't know how to

show it's the lcm of m and n,

Thanks in advance!!