# What is the proof of finding the LCM of numbers by prime factorization method?

Fir example on the internet I found this method to find the LCM :

Let's find the LCM of 30 and 45. One way to find the least common multiple of two numbers is to first list the prime factors of each number.

30 = 2 × 3 × 5

45 = 3 × 3 × 5

Then multiply each factor the greatest number of times it occurs in either number. If the same factor occurs more than once in both numbers, you multiply the factor the greatest number of times it occurs.

2: one occurrence  3: two occurrences  5: one occurrence

2 × 3 × 3 × 5 = 90 <— LCM

How would I go about proving that this method works for all numbers ? Is there a way ?

## 4 Answers

Hint: For each prime $p$, let $v_p(n)$ the exponent of $p$ in the prime decomposition of $n$ ($p$-valuation of $n$). Of course, $v_p(n)=0$ for all but a finite number of primes.

Prove this lemma:

$n$ is a multiple of $a$ if and only if, for all primes, $\;v_p(n)\ge v_p(a).$

Hence $n$ is a common multiple of $a$ and $b$ if and only if …

• I don't get it but thanks. – user57928 Sep 14 '18 at 0:10
• It is just a formalised way to say that each prime which is in the prime decomposition of $a$ must be in the decomposition of $n$ with at least the same exponent. – Bernard Sep 14 '18 at 0:20
• What topic is this Bernard.? So i can go and study it. – user57928 Sep 14 '18 at 18:57
• It's the simplest example of the notion of valuation, used in algebra, number theory (it leads to $p$-adic numbers) and algebraic geometry. You can look atthe Wikipedia page on valuations. – Bernard Sep 14 '18 at 21:32

There are several essentially correct answers here where you have commented that you do not understand. So I will try another explanation.

The fundamental theorem of arithmetic says that every positive integer can be factored into primes in just one way (other than reordering the factors). You have written $45$ that way, using the fundamental theorem: $$45 = 3 \times 3 \times 5 .$$ That factorization tells you that in order for some number $N$ to be a multiple of $45$, its prime factorization must have at least two $3$'s and at least one $5$.

Similarly, to be a multiple of $30$ its factorization must have at least one each of $2$, $3$ and $5$.

Put those facts together to conclude that the smallest number that's a multiple of both $30$ and $45$ must have at least one $2$, at least two $3$'s and at least one $5$. That tells you the least common multiple is $$2 \times 3 \times 3 \times 5 = 90.$$ To turn this into a "formal proof for all numbers" just carefully read @bernard 's answer. Think about the value of his $\nu_3 (45)$.

• What area of maths so I need to study to understand the proof. – user57928 Sep 14 '18 at 20:30
• Why does the LCM have to have at least one 2 and at least two 3's.? – user57928 Sep 14 '18 at 20:35
• This is the beginning of elementary number theory, but you don;t have to study that to follow the argument. If a number doesn't have at least one $2$ then it can't be a multiple of $30$ so it can't be the least common multiple. The rest of the argument works the same way. It's all just logical thinking once you understand the meanings of the words and the way numbers factor into primes. – Ethan Bolker Sep 15 '18 at 0:59
• Thank you so much it's good to know that i can solve things with basic logic. I have just watched a Khan Academy video on LCM and now I finally understand it. – user57928 Sep 15 '18 at 4:44

By having all the prime factors of each, one has a common multiple.

By having no additional (prime) factors, one has the least such.

• How is it that we don't have an additional prime factor ? – user57928 Sep 13 '18 at 23:49
• We take the bare minimum to cover all the prime factors of both. – Chris Custer Sep 13 '18 at 23:53
• I'm still failing to understand. They took the prime factor which occurs greatest number of times in either number . How is that taking the 'minimum to cover all factors' ? – user57928 Sep 14 '18 at 0:02
• True. But that is because it gives us just the prime factors which must be present in any common multiple. Remember, we need all the prime factors of each... – Chris Custer Sep 14 '18 at 0:06
• I still don't get it but thank you . – user57928 Sep 14 '18 at 0:09

Here is an alternate method. Since we know that $ab=$lcm$(a,b)\cdot$gcd$(a,b)$, one can find gcd$(a,b)$ using standard method or Euclid's algorithm. Then divide $ab$ by gcd$(a,b)$ yields the desired result.