# Find the lowest number that's $\geq N$ and that multiplying it with a set of numbers results in natural numbers

Given a set of numbers, I need to find the lowest number that multiplying it with each of the numbers in the set results in a natural number, while being bigger or equal to $N$.

For example, for the numbers $2.2$, $3$ and $4.2$, the result could be $5$, $10$, $15$, etc as they can multiply $2.2$ and $4.2$ and result in natural numbers. Then, I need the lowest one that's higher than a given number.

I'm trying to implement it as a software algorithm in an efficient way. How would I go about doing that?

-
If you are given the numbers as decimals instead of fractions, you may have a hard time finding the solution... –  TMM Oct 21 '12 at 20:07

First find the least common multiple of the denominators. You have to multiply by that to clear the fractions, so do so. Then if $a$ is the smallest number after multiplying by the LCM, divide $N$ by $a$ and round up to the next whole number. Call that $b$. The multiplier for the original set is $b*LCM$

-
Would that give me the smallest number possible? How would I go from there to finding the smallest one that's larger than N? –  shesek Oct 21 '12 at 19:52
@shesek: I misread the problem, thinking you just wanted the product larger than the largest in your original set. Fixed. –  Ross Millikan Oct 21 '12 at 21:59
When referring to "a is the smallest number", you mean after multiplying all the numbers by the lcm, right? –  shesek Oct 21 '12 at 22:24
@shesek: It would be clearer to make it so. I was thinking that $a$ was the original smallest number, which is why I said to divide by $a * lcm$. Now it will just be $a$. I will update –  Ross Millikan Oct 21 '12 at 22:28
@shesek: the LCM is taken over denominators. So if you have 3 and 7 and $N=50$, the LCM of the denominators is 1, then $b=17$ –  Ross Millikan Oct 21 '12 at 23:02
Suppose you are given a set of rationals $\left\{\frac{p_1}{q_1}, \ldots, \frac{p_n}{q_n}\right\}$ with $\gcd(p_i, q_i) = 1$ for $i = 1, \ldots n$. You have to multiply by a number $A$ that will make sure that $A / q_i$ is integral for all $i$, so that $A \cdot \frac{p_i}{q_i} \in \mathbb{Z}$ for all $i$. To find the smallest such $A$, you want to use the least common multiple of the $q_i$, i.e., $A^{*} = \mathrm{lcm}(q_1, \ldots, q_n)$. Note that any number $A$ such that $A/q_i \in \mathbb{Z}$ for all $i$ is an integer multiple of $A^{*}$.
So finally, if $A^{*} \geq N$, you can use this number as your $A$, while if $A^{*} < N$, you just have to find the least integer multiple $kA^{*}$ which is bigger than $N$. So you could just divide $N$ by $A^{*}$, and round up, to get $k = \lceil N/A^{*} \rceil$ and $A = k A^{*}$. This formula actually holds in general (if $A^{*} \geq N$ then $k = 1$), so the solution could be summarized in one line as
$$A = \left\lceil \frac{N}{\mathrm{lcm}(q_1, \ldots, q_n)}\right\rceil \cdot \mathrm{lcm}(q_1, \ldots, q_n).$$