The least common multiple of two given natural numbers is the smallest positive integer that is a multiple of both given numbers.

The product of any two numbers ${\displaystyle a, b}$ is equal to the product of their greatest common divisor and least common multiple.

Proof

${\displaystyle \gcd(a,b)\cdot\text{lcm}(a,b)=ab}$

Prerequisites:

• Proof that the prime factorization of an integer is unique
• Maximum and minimum
• Proof that the minimum exponent of each factor in the factorization of two integers make up the factorization of their greatest common divisor.
• Proof that the maximum exponent of each factor in the factorization of two integers make up the factorization of their least common multiple.

If ${\displaystyle a = 1}$ , then ${\displaystyle \gcd(a,b)=1}$ and ${\displaystyle \text{lcm}(a,b)=b}$ , then ${\displaystyle \gcd(1,b)\cdot\text{lcm}(1,b)=1\cdot b=b}$ , which is already equal to ${\displaystyle ab}$ .

The same goes when ${\displaystyle b=1}$ . The conclusion is now true when either ${\displaystyle a}$ or ${\displaystyle b}$ is equal to 1.

We now list the prime factorizations of the numbers:

${\displaystyle a=a_1^{c_1}a_2^{c_2}\cdots a_p^{c_p}}$

${\displaystyle b=b_1^{d_1}b_2^{d_2}\cdots b_q^{d_q}}$

If a factor ${\displaystyle a_i}$ or ${\displaystyle b_i}$ is not in the other factorization, we add them to the other factorization by assigning their exponents a 0. Thus, the number of factors should now be equal, and no distinction will be made between the factorizations:

${\displaystyle a=k_1^{c_1}k_2^{c_2}\cdots k_n^{c_n}}$

${\displaystyle b=k_1^{d_1}k_2^{d_2}\cdots k_n^{d_n}}$

Let's take an example. Suppose ${\displaystyle a=12,b=16}$ . Their factorizations are:

${\displaystyle 12=2^2\cdot3^1}$

${\displaystyle 16=2^4}$

Now since the factor 3 is not in 16, we'll add that to the factorization of 16 with an exponent of 0:

${\displaystyle 16=2^4\cdot3^0}$

We don't have anything to change in the factorization of 12.

Using the last two proofs stated in the prerequisites, we have:

${\displaystyle \gcd(a,b)=k_1^{\min(c_1,d_1)}\cdots k_n^{\min(c_1,d_1)}}$

${\displaystyle \text{lcm}(a,b)=k_1^{\max(c_1,d_1)}\cdots k_n^{\max(c_1,d_1)}}$

Multiplying,

${\displaystyle \gcd(a,b)\cdot\text{lcm}(a,b)=[k_1^{\min(c_1,d_1)}\cdots k_n^{\min(c_1,d_1)}]\cdot[k_1^{\max(c_1,d_1)}\cdots k_n^{\max(c_1,d_1)}]}$

${\displaystyle =k_1^{\min(c_1,d_1)+\max(c_1,d_1)}\cdots k_n^{\min(c_n,d_n)+\max(c_n,d_n)}}$

Evaluating ${\displaystyle \min(x,y)+\max(x,y)}$ , we would find out that it is just equal to ${\displaystyle x + y}$ , since one of them would be the minimum and the other would be the maximum, and it still holds when ${\displaystyle x = y}$ .

${\displaystyle =k_1^{c_1+d_1}\cdots k_n^{c_n+d_n}}$

${\displaystyle =[k_1^{c_1}\cdots k_n^{c_n}][k_1^{d_1}\cdots k_n^{d_n}]}$

Recall that the above expressions are equal to ${\displaystyle a, b}$ .

${\displaystyle =ab}$

QED

See also

• Greatest common divisor
• Table of least common multiples (to 32)