# 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?

• What tools do you want to use? It is an immediate consequence of Unique Factorization, and the representation of gcd, lcm in terms of the prime power factorization.Or else one can use more basic machinery. – André Nicolas Aug 19 '13 at 0:16
• The latter would be fine. – Susan Aug 19 '13 at 0:19
• It is also a consequence of the Chinese Remainder Theorem. – lhf Aug 19 '13 at 15:19

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}

• I believed the prime power factorization was more number theoretic as the Chinese Remainder Theorem is more in that flavor, although some algebraists like to think it's theirs because there's a generalization with PIDs and comaximal ideals... but anyway, you did a good description of that proof. +1 – Patrick Da Silva Aug 19 '13 at 0:28

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$.

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.

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$.

• Patrick, in the second line do you mean $[m,n]=mn$? – user84413 Aug 19 '13 at 0:35
• @user84413 : Yes, typo. I didn't pay enough attention, thanks! – Patrick Da Silva Aug 19 '13 at 0:51

Please correct me if I'm wrong (I mean it!), but it seems to me that unique factorization (let alone the Euclidean algorithm or Bezout's identity) is not needed to prove this. I'll give a proof of the generalization of the theorem for an arbitrary integral domain $R$ (but see notes right after the statement explaining how to specialize the theorem to the case $R = \mathbb{Z}$).

Let $R$ be an integral domain, and let $a, b$ be elements of $R$ having both a gcd $d$ and an lcm $m$ in $R$. Then there exists a unit $u \in R$ such that $dm = uab$.

Note: as the wording suggests, uniqueness of gcds and/or lcms is not assumed here. Also, when $R = \mathbb{Z}$, the only units (aka "invertible elements") are $\pm 1$, and furthermore, if one adopts the common convention that both the $\gcd(a, b)$ and the $\mathrm{lcm}(a, b)$ are defined to be positive, then the $\gcd(a, b)$ and $\mathrm{lcm}(a, b)$ are unique, and the theorem's punchline therefore reduces to $$\gcd(a, b) \times \mathrm{lcm}(a, b) = |ab|\;.$$

Proof: Since $ab$ is a common multiple of $a$ and $b$, it follows from the definition1 of lcm that there exists a $\delta \in R$ such that $\delta m = ab$. On the other hand, again by the definition of lcm, there exist $i,j\in R$ such that $ai = m = bj$. Multiplying through by $\delta$ yields

$$\delta ai = \delta m = \delta bj\,.$$

Replacing the middle term with $ab\;(=\delta m)$ and cancelling $a$ from the left equality, and $b$ from the right one, we get that $\delta i = b$ and $\delta j = a$. This shows that $\delta$ is a common divisor of both $a$ and $b$.

The definition of gcd now implies that there exists a $u \in R$ such that $\delta u = d$, and therefore,

$$dm = u\delta m = uab\;.$$

It remains to be shown that $u$ is a unit. Now, again by the definition of gcd, there exist $r, s \in R$ such that $dr = a$ and $ds = b$. Define $\mu = rds$. Then

$$d\mu = dr\,ds = a\,ds = dr\,b = ab\;.$$

Cancelling $d$ in the first three equalities above shows that $\mu = as = br.$ This means that $\mu$ is a common multiple of both $a$ and $b$, and therefore, by the definition of lcm, there exists $v\in R$ such that $\mu = vm$.

Substituting this expression for $\mu$ into the equality $d\mu = ab$ established above yields $d\,vm = vdm = ab$, which becomes $uvdm = uab$ after multiplying through by $u$. Putting this together with the previously obtained $dm = uab$ gives $uvdm = dm$, which, after cancelling out the $dm$ factor reduces to $uv = 1$. Hence $u$ is a unit.

1 This proof repeatedly invokes the definitions of gcd and lcm for a general integral domain; these definitions are entirely consistent with those for the gcd and lcm in $\mathbb{Z}$, but, for the sake of clarity and completeness, here they are: $d \in R$ is a divisor of $a \in R$ if there exists $r \in R$ such that $dr = a$; $d$ is a greatest common divisor (gcd) of $a, b\in R$ if (1) it is a divisor of both $a$ and $b$, and (2) any other divisor of $a$ and $b$ is also a divisor of $d$; note that, in general, for any $a, b \in R$ there may be any number of gcds—including none; if $d$ and $d^{\prime}$ are both gcds of $a$ and $b$, then they are associates (i.e. there exists a unit $u \in R$ such that $d = ud^{\prime}$); this is so because they must be divisors of each other. Similarly, $m \in R$ is a multiple of $a\in R$ if there exists $q \in R$ such that $m = aq$; $m$ is a least common multiple (lcm) of $a, b\in R$ if (1) it is a multiple of both $a$ and $b$, and (2) any other multiple of $a$ and $b$ is also a multiple of $m$. Similar considerations on uniqueness as those for gcds apply to lcms. In particular, if $m$ and $m^{\prime}$ are both lcms of $a, b\in R$ then $m$ and $m^{\prime}$ are associates.

• does this proof show that $\gcd(a,b)\cdot lcm(a,b) \sim ab$ (i.e., that the product of the gcd and lcm is associate to the product of the two elements)? – ALannister Apr 24 '17 at 16:41
• @ALannister: yes – kjo Apr 24 '17 at 17:24

Given $n,m$ and $d=\gcd(n,m)$, we can then denote $n=da$,$m=db$ where $a,b$ are coprime. In that language, $\operatorname{lcm}(n,m)$ would be $dab$ (it is fairly straightforward to show that they both divide each other), which gives us the claim.

CLAIM $\hspace{5.5 cm }(a,b)[a,b]=ab$

P. Let $d=(a,b), e=\dfrac{ab}{[a,b]}$. We will prove that $d=e$. Recall we define $d$ as the (unique) positive number such that $d$ divides both $a$ and $b$, and if $d'$ is any other common divisor, $d'\mid d$. We wish to show $e$ has these two properties. First, note that $$\frac{a}{e} = \frac{{\left[ {a,b} \right]}}{b} \in {\Bbb Z}$$ $$\frac{b}{e} = \frac{{\left[ {a,b} \right]}}{a} \in {\Bbb Z}$$ since both $a,b$ divide $[a,b]$, so $e$ is a common divisor. Now suppose $d'$ is another common divisor. Recall that $[a,b]$ is the unique positive number such that $a,b$ both divide $[a,b]$ and whenever $a,b$ both divide some $f$, $[a,b]$ divides this $f$. We will use this to finish off the proof. Since $d'$ is a common divisor, $\dfrac{ab}{d'}$ is an integer. Moreover, both $a,b$ divide it, so it is a common multiple. It follows that $$\frac{f}{{\left[ {a,b} \right]}} = \frac{{ab}}{{\left[ {a,b} \right]d'}} = \frac{e}{{d'}}$$ is an integer, do $d'\mid e$, whence $d=e$. $\blacktriangle$