why is the method of prime factorization help in finding the lcm?

Question

why does finding the prime factors help in finding the lcm of two or more numbers. I know how to do it but why is this the case?

Edit

I found this answer from just thinking on my own.I don't know if it is correct. The prime factors give us the minimum prime factors required to make up any number. Anything multiplied on top those factors still is a multiple of the number. example

primefactors(18) = 2*3*3
this means you need to at least have one 2 and two 3 to have a multiple of 18.
(2*3*3)*n = (18)*n, n could be any number, the product will always be a multiple of 18.

Knowing this we could combine the primefactors of two numbers in such a way that we meet the minimum requirement of each prime factor to have multiple of both numbers. example

lcm(10,24)
primefactors(10) = 2*5, this means we atleast need a factor of one 2 and one 5 to have a multiple of 10.
primefactors(24) = 2*2*2*3,  this means we atleast need a factor of three 2 and one 3 to have a multiple of 24.

we start with minimum factors we need for a multiple 10
2*5
we add the missing minimum factors we need for a multiple of 24
2*2*2*3*5

this is the same as
2*2*2*3*5 = (10) * 12 = (24) * 5

I hope this makes sense, I don't know any math notation, this is just from my brain.

Answer 1

Suppose you have two numbers written in their prime factorization

$$n = \prod_{i=1}^\infty p_i^{a_i} \;\;\;\;\; m = \prod_{i=1}^\infty p_i^{b_i}$$

where your exponents $a_i,b_i$ can be a nonnegative integer (i.e. including zero) and $p_i$ denotes the $i^{th}$ prime number. Then

$$\text{lcm}(n,m) = \prod_{i=1}^\infty p_i^{\max(a_i,b_i)}$$

Obviously, the process generalizes to as many numbers you're finding the lowest common multiple of in an easy manner.

---

Explanation of Notation

To clear things up for more elementary learners, let's explain the notation, particularly the "$\prod$" bit. This denotes an iterated product. It's sort of like a "for" loop from programming, but for math, if you're familiar with the context. The idea is quite simple:

• The bottom indicates you start at $i=1$.
• The top indicates where you end. Sometimes it's finite, and it's obvious where you end. Sometimes it's infinity, in which case it just goes on and on forever.
• The $\prod$ itself denotes the operation you're doing. Here, it's multiplication (because that's the convention mathematicians went with). If you had $\sum$, by similar convention, it'd mean you add. $\bigcup$ would denote union of sets. And so on and so forth.

So what you do is plug in your start variable (here, $i=1$). Then you take that result, add one to your index variable $i$, and then find the result with that, i.e. plug in $i=2$. Then plug in $i=3$, $i=4$, and so on, successively multiplying each result.

Some examples might help you understand:

$$\begin{align} \prod_{i=1}^5 i &= 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5\\ \prod_{i=4}^7 \frac{1}{2i} &= \frac{1}{2 \cdot 4} \cdot \frac{1}{2 \cdot 5} \cdot \frac{1}{2 \cdot 6} \cdot \frac{1}{2 \cdot 7}\\ \sum_{i=2}^\infty \frac{1}{2^i} &= \frac{1}{2^2} + \frac{1}{2^3} + \frac{1}{2^4} + \frac{1}{2^5} + \frac{1}{2^6} + \cdots \end{align}$$

With the iterated product notation out of the way, the only other thing I think that needs explaining is the $\max$ function, but that's far more intuitive: whatever is in the function, the result is the largest value. Some examples:

• $\max(1,2,3) = 3$
• $\max(1, 1/2, 1/3, 1/4, \cdots) = 1$
• $\max(10, 20, 30, 40) = 40$

Thus, $\max(a_i,b_i)$ just means "take the bigger of the two values".

If the iterated product notation confuses you despite this, then I'll rewrite the formulas for $n,m$ and their lowest common multiple. Even so, remember that $p_i$ is the $i^{th}$ prime number. So $p_1=2$, $p_2=3$, $p_3=5$, and so on.

$$\begin{align} n &= 2^{a_1} \times 3^{a_2} \times 5^{a_3} \times 7^{a_4} \times \cdots \times p_i^{a_i} \times \cdots\\ m &= 2^{b_1} \times 3^{b_2} \times 5^{b_3} \times 7^{b_4} \times \cdots \times p_i^{b_i} \times \cdots\\ \text{lcm}(n,m) &= 2^{\max(a_1,b_1)} \times 3^{\max(a_2,b_2)} \times 5^{\max(a_3,b_3)} \times 7^{\max(a_4,b_4)} \times \cdots \times p_i^{\max(a_i,b_i)} \cdots \times \end{align}$$

Or, in words,

Write out the prime factorizations of $n$ and $m$, including $0$ for numbers not included in the prime factorization (so $14 = 2^1 \times 3^0 \times 5^0 \times 7^1 \times 11^0 \times \cdots$ for example). Then rewrite the prime factorization one more time, but this time, for the corresponding prime factor, just take the bigger of the exponents that appear in $n$ or $m$ and use that for the $\text{lcm}$.

---

An Example:

Find the $\text{lcm}$ of $20$, $27$, and $35$.

We note that

$$\begin{align} 20 &= 2^2 \times 5\\ 27 &= 3^3\\ 35 &= 5 \times 7 \end{align}$$

(For any missing prime factors, just assume they're zero in their exponents again. Like with $27$, $27 = 2^0 \times 3^3 \times 5^0 \times \cdots$.)

Compare prime factors and take the largest exponent among them.

• Largest exponent for $2$: $2$
• Largest exponent for $3$: $3$
• Largest exponent for $5$: $1$
• Largest exponent for $7$: $1$
• There are no larger prime factors

Therefore,

$$\text{lcm}(20,27,35) = 2^2 \times 3^3 \times 5 \times 7 = 3780$$

The comparisons are particularly easy to see if you just write them out in a table like this. The relevant exponent is the largest in a given column.

$$\begin{array}{c|c|c|c|c|c|c} & 2 & 3 & 5 & 7 & 11 & 13 & \cdots \\ \hline 20 & 2 & & 1 & & & & \cdots \\ 27 & & 3 & & & & & \cdots \\ 35 & & & 1 & 1 & & & \cdots \\ \hline \text{lcm} & 2 & 3 & 1 & 1 & & & \cdots \\ \end{array}$$

Blank spaces obviously are synonymous with an exponent of $0$; feel free to use them or leave them out, same difference in the end.