Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove the algorithm for LCM

  1. Mar 5, 2005 #1
    algorithm to prove lcm:

    while a != b
    if a < b
    a:= a + m
    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!!
  2. jcsd
  3. Mar 5, 2005 #2
    Forget it! problem soloved ...

    Forget it! problem soloved ...
  4. Mar 6, 2005 #3
    I'm curious, how do you solve that?
  5. Mar 7, 2005 #4
    loop invariant..

    the loop invariant should be
    1)ak >=m and bk> =m
    2)ak mod m=0 and bk mod n=0
    3)ak<=lcm(m,n) and bk<=lcm(m,n)

    U can prove a is the lcm(m,n) by these LI..
  6. Mar 8, 2005 #5
    Cool, I see.
  7. Mar 8, 2005 #6
    Wait, I think you also need ak > a(k-1) and bk > b(k-1)

    That's not really a loop invariant though because it's not true until the second iteration.

    I guess you could say something like "if k is > 1, then (that condition) is true."
    Last edited: Mar 8, 2005
  8. Mar 9, 2005 #7
    U right..

    I forget to mention that.. m,n>=1 is the precondition..
  9. Mar 10, 2005 #8
    No, that's not what I said. For example, what if the loop were:
    for(i = 0; i < 10; i++)
    a = m;
    b = n;

    That satisfies the loop invariants you gave, but it's not going to find the LCM.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook