Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Is there any algorithm to find it without prime factorization?

share|improve this question
    
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

3 Answers 3

up vote 12 down vote accepted

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$.
share|improve this answer
2  
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$.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.