I'm not sure how to go about this proof. I just need help getting started. Is there a way to prove it algebraically?
$\endgroup$ 47 Answers
$\begingroup$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}
$\endgroup$ 1 $\begingroup$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$.
$\endgroup$ 1 $\begingroup$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.
$\endgroup$ $\begingroup$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$.
$\endgroup$ 2 $\begingroup$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.
$\endgroup$ 2 $\begingroup$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.
$\endgroup$ $\begingroup$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$
$\endgroup$
