This page should be merged with L.C.M. and H.C.F.|}
The 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.
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} $
- $ 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.
- $ \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)} $
- $ \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 $
## See also |