Question

Show that if a and b are positive integers, then ab = gcd (a, b). lcm (a, b) . [Hint: Use prime factorizations of a and b and the formulae for gcd(a ,b) and lcm (a, b)in terms of these factorization.]

Answer 1

Answer:

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

Step-by-step explanation:

Using the hint, write a and b in the following prime factorization:

$a=p_1^{x_1}p_2^{x_2}\cdots p_t^{x_t}\cdot q,$

$b=p_1^{y_1}p_2^{y_2}\cdots p_t^{y_t}\cdot r,$

where  $\gcd(p_i,r)=1,\ \gcd(p_i,q)=1,\ \gcd(r,q)=1,\ \gcd(p_i,p_j)=1,$ for i ≠ j.

Then by the formulae for gcd(a,b) and lcm(a,b) we know that:

$\gcd(a,b)=p_1^{\min(x_1,y_1)}p_2^{\min (x_2,y_2)} \cdots p_t^{\min(x_t,y_t)}$

$\text{lcm}(a,b)= q\cdot r\cdot p_1^{\max(x_1,y_1)}p_2^{\max(x_2,y_2)}\cdots p_t^{\max(x_t,y_t)}$

Note that the expression $\min(x_i,y_i)+\max(x_i,y_i)=x_i+y_i$ for all i, since if the minimum is, without loss of generality, $x_i$, then the maximum must be $y_i$, and viceversa. Then, it is straightforward to verify that when we multiply gcd(a, b) and lcm(a, b) its prime factorization matches the prime factorization of ab, and so we can see the equaility holds:

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