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

Question

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 ?

Answer 1

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 …

Answer 2

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.

Answer 3

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

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

Answer 4

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)$.