Find smallest positive integer $N$ such that $N \times r_{k}$ is a positive integer for a collection of positive rationals $\{r_{1},\ldots,r_{K}\}$

Question

Let $\{r_{1},\ldots,r_{K}\}$ be a collection of $K$ positive rational numbers.

How do I find the smallest positive integer $N$ such that $Nr_{k}$ is a positive integer for all $k$?

(Ideally, I am interested in a formula that is computationally cheap when $K$ is relatively large.)

Answer 1

You just need the least common multiple of the denominators once you express them in lowest terms. If you are given a numerator and denominator, you can check whether they have a common factor by the Euclidean algorithm. Divide that out to get all fractions in lowest terms. Then take the first two denominators, check for common factor, and form the least common multiple. Continue with each denominator in turn. This takes just two passes through the fractions, or one if you are guaranteed they are in lowest terms at the start.