Least common multiple

This page should be merged with L.C.M. and H.C.F.|} 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 $a, b$ is equal to the product of their greatest common divisor and least common multiple. Proof $\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 $a = 1$ , then $\gcd(a,b)=1$ and $\text{lcm}(a,b)=b$ , then $\gcd(1,b)\cdot\text{lcm}(1,b)=1\cdot b=b$ , which is already equal to $ab$ . The same goes when $b=1$ . The conclusion is now true when either $a$ or $b$ is equal to 1. We now list the prime factorizations of the numbers: $a=a_1^{c_1}a_2^{c_2}\cdots a_p^{c_p}$ $b=b_1^{d_1}b_2^{d_2}\cdots b_q^{d_q}$ If a factor $a_i$ or $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: $a=k_1^{c_1}k_2^{c_2}\cdots k_n^{c_n}$ $b=k_1^{d_1}k_2^{d_2}\cdots k_n^{d_n}$ Let's take an example. Suppose $a=12,b=16$ . Their factorizations are: $12=2^2\cdot3^1$ $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: $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: $\gcd(a,b)=k_1^{\min(c_1,d_1)}\cdots k_n^{\min(c_1,d_1)}$ $\text{lcm}(a,b)=k_1^{\max(c_1,d_1)}\cdots k_n^{\max(c_1,d_1)}$ Multiplying, $\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)}]$ $=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 $\min(x,y)+\max(x,y)$ , we would find out that it is just equal to $x + y$ , since one of them would be the minimum and the other would be the maximum, and it still holds when $x = y$ . $=k_1^{c_1+d_1}\cdots k_n^{c_n+d_n}$ $=[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 $a, b$ . $=ab$ QED See also Greatest common divisor Table of least common multiples (to 32)