Prove that $\gcd(M, N)\times \mbox{lcm}(M, N) = M \times N$.

I'm not sure how to go about this proof. I just need help getting started. Is there a way to prove it algebraically?

Solution 1:

Take the prime-power decomposition of $m$ and $n$. We have \begin{array} .m &=&p_1^{a_1}\times p_2^{a_2} \times \ldots \times p_k^{a_k} \\ n &=&p_1^{b_1}\times p_2^{b_2}\times \ldots \times p_k^{b_k} \end{array} where each of the $p_i$ are distinct primes and each of the $a_j$ and $b_{\ell}$ are non-negative integers. For example, if $m=4$ and $n=18$ then we write $m = 2^2 \times 3^0$ and $n = 2^1 \times 3^2$.

The important part of this trick is that we write both $m$ and $n$ as a product of the same primes, even if some of the powers are zero. By definition: \begin{array} .\text{lcm}(m,n) &=& p_1^{\max(a_1,b_1)}\times \cdots \times p_k^{\max(a_k,b_k)} \\ \text{gcd}(m,n) &=& p_1^{\min(a_1,b_1)}\times \cdots \times p_k^{\min(a_k,b_k)} \end{array} Clearly $\max(a_i,b_i) + \min(a_i,b_i) = a_i + b_i$ and hence \begin{array} .\text{lcm}(m,n) \times \gcd(m,n) &=& p_1^{a_1+b_1} \times \cdots \times p_k^{a_k+b_k} \\ &=& (p_1^{a_1} \times p_1^{b_1}) \times \cdots \times (p_k^{a_k} \times p_k^{b_k}) \\ \\ &=& m \times n \end{array}

Solution 2:

There are many proofs. We give two, one that uses the Unique Factorization Theorem, and another that uses Bezout's Identity.

First Proof: Let $p_1, p_2,p_k$ be the primes that occur in the prime power factorization of $M$ or $N$ or both. Let $$M=p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k}\quad\text{and}\quad N=p_1^{\beta_1}p_2^{\beta_2} \cdots p_k^{\beta_k}.$$ Note that we are allowing some of the $\alpha_i$ and $\beta_j$ to be $0$.

You may have already seen the theorem that the gcd of $M$ and $N$ is equal to $$ p_1^{\delta_1}p_2^{\delta_2} \cdots p_k^{\delta_k},$$ and their lcm is $$ p_1^{\mu_1}p_2^{\mu_2} \cdots p_k^{\mu_k},$$ where $\delta_i=\min(\alpha_i,\beta_i)$ and $\mu_i=\max(\alpha_i,\beta_i)$.

Then the theorem follows from the fact that $\delta_i+\mu_i=\alpha_i+\beta_i$. (The minimim of two numbers, plus the maximum of two numbers, is the sum of the two numbers.)

Second Proof: We use Bezout's Identity, which says that if $d$ is the gcd of $M$ and $N$, there exist integers $x$ and $y$ such that $Mx+Ny=d$.

Note that $d$ divides $MN$. Let $m=\frac{MN}{d}$. We show that $m$ is the lcm of $M$ and $N$. This will finish things.

Certainly $m$ is a common multiple of $M$ and $N$. Let $n$ be a common positive multiple of $M$ and $N$. We will show that $m$ divides $n$. That will show that $m\le n$, making $m$ the least common multiple.

We have $$\frac{n}{m}=\frac{nd}{MN}==\frac{n(Mx+Ny)}{MN}=\frac{n}{N}x+\frac{n}{M}y.\tag{1}$$ The right-hand expression in (1) is an integer, and therefore $\frac{n}{m}$ is an integer, that is, $n$ is a multiple of $m$.

Solution 3:

Theorem 1: For any $N,M$, $$\gcd\left(\frac{N}{\gcd(N,M)},\frac{M}{\gcd(N,M)}\right)=1$$

Theorem 2: For any $N,M,K$, $$\mathrm{lcm}(NK,MK)=K\cdot\mathrm{lcm}(N,M)$$

Theorem 3: If $\gcd(N,M)=1$ then if $N|K$ and $M|K$ then $NM|K$.

Corollary: If $\gcd(M,N)=1$ then $\mathrm{lcm}(N,M)=NM$.

From these, you can prove the above result.

(1) and (3) have nice proofs using Bézout's identity. (2) is a direct proof. The corollary follows from Theorem (3), and the final result follows from (1) and the corollary.

Solution 4:

I don't know what you mean by ''algebraically''. I'll show you a proof.

I write $(m,n)$ for $gcd$ and $[m,n]$ for $lcm$. If $(m,n) = 1$, then $m$ and $n$ both divide some integer $r$ if and only if $mn$ divides it (easy consequence of the Euclidean algorithm); it means that $[m,n] = mn$. Otherwise, let $(m,n) = d$. Then since $(m/d, n/d) = 1$ and $[km,kn] = k[m,n]$ for any integer $k$, we have $$ [m,n] = \left[ \frac md d , \frac nd d \right] = \left[ \frac md, \frac nd \right] d = \frac md \frac nd d = \frac {mn}{d}, $$ hence $[m,n](m,n) = [m,n]d = mn$.