Given two numbers a and b, the least common multiple (lcm) of a and b is the smallest number m such that both a and b are factors of m. For example, lcm(15, 21) = 105 because it

Given two numbers a and b, the least common multiple (lcm) of a and b is the smallest number m such that both a and b are factors of m. For example, lcm(15, 21) = 105 because it is the smallest number that has both 15 and 21 as factors.

Formally, we will work with the following decision problem:

                      LCM = {a, b, m | lcm(a, b) = m}

(a) Explain why the following algorithm that decides LCM does not run in polynomial time:

                  a) Check if m is a multiple of a and b; if not reject a, b, m

                  b) For i = 1, 2, . . . , m − 1 do:

                            i. If i is a multiple of a and b, a multiple smaller than m was found.

                             Reject a, b, m.

                  c) If it reached the end of the loop without finding a multiple less than m, accept a, b, m.

(b) Prove that LCM ∈ P.