# “Least” common multiple of A and B, greater than C

Least common multiple of $A$ and $B$ that is greater than $C$.

Is there any algorithm to find it without prime factorization?

-
Please make the bodies of your posts self-contained; don't rely on the subject for key content. – Arturo Magidin Mar 24 '11 at 19:28
Thanks, Arturo. – medina Mar 24 '11 at 20:03

Any common multiple of $A$ and $B$ is a multiple of the least common multiple, $\mathrm{lcm}(A,B)$.

The least common multiple can be found using the identity $$\mathrm{lcm}(A,B)\gcd(A,B) = |AB|.$$ The $\gcd$ can be found using the Euclidean Algorithm, which does not require you to find the prime factorization. So you can find the least common multiple without knowing the prime factorization.

Once you know the lcm, call it $K$, then you are merely looking for the smallest integer $n$ such that $nK\gt C$. This is $n = \lceil \frac{C}{K}\rceil$ if $K\neq 0$. (And of course, if $K=0$, then that means that at least one of $A$ and $B$ is equal to $0$, and there is no solution).

In summary:

1. Find the greatest common divisor (e.g., using the Euclidean algorithm);
2. Compute $M=|AB|/\gcd(A,B)$.
3. Find the smallest integer $k$ greater than or equal to $C/M$.
4. The multiple you want is $kM$.
-
If $C$ is itself a multiple of $K$, then you'll need to take $n+1 = \frac{C}{K}+1$ instead. – Arturo Magidin Mar 25 '11 at 21:08

Sure, first find the least common multiple of A and B, which you can find by calculating:

$$\frac{|AB|}{\operatorname{gcd}(A,B)}$$

Then divide $C$ by the LCM. If it divides evenly, then C is your answer, otherwise, the next highest multiple. So the result is: $$L = AB/gcd(A,B)$$ $$C' ={ \left \lceil \frac{C}{L} \right \rceil } L$$ where $\left \lceil x \right \rceil$ is the smallest integer greater than or equal to $x$.

-

HINT $\:$ Any common multiple $\rm\:M\:$ is a multiple of the least common multiple $\rm\ m = AB/gcd(A,B)\:.\:$ So you seek the first multiple of $\rm\:m\:$ that is larger than $\rm\:C\:,\:$ computable simply by an obvious division.

Notice how the use use of $\rm\:lcm\:$ has allowed us to convert a problem from one with multiple divisibility relations to one involving a single divisibility relation $\rm\ A,\:B\ |\ M\ \iff\ lcm(A,B)\ |\ M\:.\:$ This, the universal definition of $\rm\:lcm\:,\:$ is what allows us to reduce complex divisibility problems to single divisions - as occurs here, after we adjoin the additional constraint that $\rm\: M > C\:,\:$ namely

$$\rm\ A\:,B\ |\ M > C\ \ \iff\ \ lcm(A,B)\ |\ M > C$$

For a universal proof of $\rm\ gcd(a,b)\ lcm(a,b)\ =\ a\ b\$ see my post here or here.

-