Determining lowest common multiple with prime factorisation, when to stop factoring

Question

I was calculating the lowest common multiple $$ \operatorname{lcm}(150, 210, 735, 1365) $$ I factored each up to $7$ and got the answer wrong because I didn't factorise with $13$. So my question is when do we stop testing factors, is it as simple as starting from the bottom and working up until you exhaust all options?

Answer 1

This answer addresses the question of how to factor a number into primes, which is a necessary step in implementing the technique that you allude to for finding a least common multiple.

Observe: When two numbers are multiplied together to obtain a fixed product, as one gets larger the other gets smaller, e.g., if we are looking at the number $100$, \begin{array}{rcrcr} 1 &\times & 100 &= & 100 \\ 2 &\times & 50 &= & 100 \\ 4 &\times & 25 &= & 100 \\ 5 &\times & 20 &= & 100 \\ 10 &\times & 10 &= & 100 \\ 20 &\times & 5 &= & 100 \\ 25 &\times & 4 &= & 100 \\ 50 &\times & 2 &= & 100 \\ 100 &\times & 1 &= & 100 \end{array} Thus, if you're looking for a prime $p$ that divides a given number, there's no need to go past the "middle". For example, if we didn't know how to factor $100$, there would be no need to try the prime $11$ because if it divided $100$, then the other factor would be smaller, and you would have already discovered it!

Say you are trying to factor the number $391$ into primes. You don't need to consider any prime $p$ for which $p^2 > 391$. Since $20^2 = 400$, you only need to consider primes up to $19$. But before you get there, you find that $17$ divides $391$, with the other factor $23$, also a prime, so you're done: $$ 391 = 17 \times 23 $$

For example, say you were trying to factor $997$ into primes. It will turn out that it's prime itself, but how can you be sure doing as little arithmetic as possible? Find the square root (and round down to the nearest integer): $$ \bigl\lfloor \sqrt{997} \bigr\rfloor = 31 $$ This means that you only have to try factors that are primes at most $31$. This is a pretty short list: $$ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 $$ Each leaves a remainder when $997$ is divided by it, hence $997$ is itself prime, guaranteed! The smallest number that could have $37$ (the next prime) as its smallest factor is $37^2 = 1369$, so this list of candidate factors suffices up to that number, at which point we tack $37$ onto the end of the list of candidates for even larger numbers.

This ancient method which builds up a list of primes, as we iteratively discover the next prime is called the Sieve of Eratosthenes, and is useful for limiting your search.

Answer 2

This answer addresses the question of how to determine the least common multiples of (multiple) numbers (by hand). It turns out that we do not even need prime factorizations for this problem. We can use the relation that (if $a, b \in \mathbb N_{>0}$) $$\operatorname{lcm} (a, b) = \frac{a \cdot b}{ \operatorname {gcd}(a, b)}$$ where $\operatorname {gcd}$ denotes the greatest common divisor of $a$ and $b$. This makes sense if you think about the prime factorizations of $a$ and $b$ since $\operatorname {gcd}(a, b)$ are the factors you can omit from the least common multiple.

We use the relation that if $a\neq b$ we have $\operatorname{gcd}(a, b) = \operatorname{gcd}(a-b, b) = \operatorname{gcd}(a, b-a)$ to determine that $\operatorname{gcd}(1365, 735)$ $= \operatorname{gcd}(1365-735, 735)$ $= \operatorname{gcd}(630, 735-630)$ $= \operatorname{gcd}(630-5\cdot 105, 105)$ $= \operatorname{gcd}(105, 105)=105$. It turns out that $735/105=7$ and hence $\operatorname{lcm}(1365, 735) = 1365\cdot 7$, which we leave in this form for later.

Likewise, $\operatorname{gcd}(150, 210)$ $= \operatorname{gcd}(150, 210-150)$ $= \operatorname{gcd}(150-2\cdot 60, 60)$ $= \operatorname{gcd}(30, 30) = 30$. Hence (note that $210/30=7$) we get $\operatorname{lcm}(150, 210) = 150 \cdot 7 $.

The answer can now be written as \begin{align} \operatorname{lcm}(150, 210, 735, 1365) &= \operatorname{lcm}(\operatorname{lcm}(150, 210), \operatorname{lcm}(735, 1365)) \\ &= \operatorname{lcm}(150 \cdot 7, 1365 \cdot 7) \\ &= 7\operatorname{lcm}(150, 1365) \end{align} We have $\operatorname{gcd}(150, 1365) = \operatorname{gcd}(150, 1365-9\cdot 150) = \operatorname{gcd}(150, 15) = 15$. Thus, the final answer is $\operatorname{lcm}(150, 210, 735, 1365) = 7 \cdot \frac{150 \cdot 1365}{15} = 7\cdot13650 = 95550$.