# prove that $\operatorname{lcm}(n,m) = nm/\gcd(n,m)$

I'm trying to prove that $\operatorname{lcm}(n,m) = nm/\gcd(n,m)$ I showed that both $n,m$ divides $nm/\gcd(n,m)$ but I can't prove that it is the smallest number. Any help will be appreciated.

• Have you tried using the Fundamental Theorem of Arithmetic? (I.e. every natural number has a factorization into powers of primes that is unique up to re-ordering) – sharris Jun 9 '15 at 18:11
• From what sharris said, it's a fairly standard proof for $m\cdot n = gcd(m,n) \cdot lcm(m,n)$ (which is equivalent to what you want to show). – anakhro Jun 9 '15 at 18:13

## 4 Answers

Hint $$\,\ n,m\mid k \!\iff\! nm\mid nk,mk\!\overset{\ \rm U}\iff\! nm\mid (nk,mk) \overset{\ \rm D_{\phantom |}}= (n,m)k\!\iff\! nm/(n,m)\mid k$$

where above we have applied $$\rm U =$$ GCD Universal Property and $$\rm D =$$ GCD Distributive Law.

Remark $$\$$ If we bring to the fore the implicit reflection symmetry we obtain a simpler proof: it's easy to show that $$\,d\,\mapsto\, mn/d\,$$ bijects the common divisors of $$\,m,n\,$$ with the common multiples $$\le mn.$$ Being order-$$\rm\color{#c00}{reversing}$$, it maps the $$\rm\color{#c00}{Greatest}$$ common divisor to the $$\rm\color{#c00}{Least}$$ common multiple, i.e. $$\,{\rm\color{#c00}{G}CD}(m,n)\,\mapsto\, mn/{\rm GCD}(m,n) = {\rm \color{#c00}{L }CM}(m,n).\,$$

See here more on this involution (reflection) symmetry at the heart of gcd, lcm duality.

Hint: For any $a,b$ real numbers: $\min(a,b)+\max(a,b)=a+b$.

Now, if we have $a=a_1^{p_1} a_2^{p_2}\ldots$ and similarly with $b$, if you use the equation I just mentioned for all $p_i$, you will get, that $\gcd(a,b)\cdot\operatorname{lcm}(a,b)=ab$.

• Shouldn't (a,b) be a + b? – steven gregory Jun 10 '15 at 2:09
• True on that. I correct it. – Atvin Jun 10 '15 at 5:15

Here is one way without using the Fundmental theorem of arithmetic just using the definitions

The definition of lcm(a,b) is as follows:

t is the lowest common multiple of a and b if it satisfies the following:

i)a | t and b | t

ii)If a | c and b | c, then t | c.

Similiarly for the gcd(a,b).

Here is my proof:

Case I: gcd(a,b) $\neq$ 1

Suppose gcd(a,b) = d.

Then $ab = dq_1b = dbq_1 = d*(dq_1q_2)$

Claim: $lcm(a,b) = dq_1q_2$

$a = dq_1$ | $dq_1q_2$

$b = dq_2$ | $dq_2q_1$.

Supppose lcm(a,b) = c. Hence c $\leq$ $dq_1q_2$ .

To get the other inequality we have $dq_1$ | a and $dq_2$ | b. Hence $dq_1$ $\leq$ a $\leq$ c $\leq$ $dq_1q_2$ similiarly for $dq_2$.

Suppose that c is strictly less than $dq_1q_2$, so we have $dq_1q_2$ < $cq_2$ and $dq_1q_2$ < $cq_1$.

So $dq_1q_2$ < c < $cq_2$ < $dq_2^2q_1$ and $dq_1q_2$ < c < $cq_2$ < $dq_1^2q_2$, but $dq_1^2q_2$ > $dq_1q_2$ so c < $dq_1q_2$ and

c > $dq_1q_2$ contradiction. Hence c = d$q_1q_2$

Notice that the case where gcd(a,b) = 1 we can just set $q_1 = a$ and $q_2$ = b, and the proof will be the same.

Let's just do this directly. Let $g = \gcd(m,n)$. We need to prove that $\operatorname{lcm}(m,n) = \dfrac{mn}{g}$.

STEP $0$. (Preliminary stuff.)

DEFINITION $1$. $L = \operatorname{lcm}(m,n)$ if and only if

 1. L is a multiple of m and of n.
2. If C is a multiple of m and of n, then C is a multiple of L.


LEMMA $2$. If $\gcd(a,b) = 1$ and $a \mid bc$, then $a \mid c$.

PROOF. If $\gcd(a,b) = 1$, then there exists integers $A$ and $B$ such that $aA + bB = 1$. It follows that $acA + bcB = c$. Since $a | acA$ and $a \mid bcB$, then $a \mid c$.

STEP $1$. $\dfrac{mn}{g}$ is a common multiple of $m$ and of $n$.

This is true because $\dfrac m g$ and $\dfrac n g$ are integers and $\dfrac{mn}{g} = \dfrac{m}{g}n = m \dfrac{n}{g}$.

STEP $2$. If $G$ is a common multiple of $m$ and of $n$, then $G$ is a multiple of $\dfrac{mn}{g}$.

Suppose $G = mM = nN$ for some integers $M$ and $N$. Then $\dfrac G g = \dfrac m g M = \dfrac n g N$.

Since $\gcd\left( \dfrac m g, \dfrac n g \right) = 1$, and $\dfrac m g M = \dfrac n g N$, then, by LEMMA $2$, $\dfrac m g \mid N$, say $N = \dfrac m g N'$ for some integer $N'$.

So $\dfrac{G}{g} = \dfrac{n}{g} N = \dfrac{m}{g} \dfrac{n}{g} N'$. It follows that $G = \dfrac{mn}{g} N'$ and so $G$ is a multiple of $\dfrac{mn}{g}$.

From STEP $1$, STEP $2$, and DEFINITION $0$, we can conclude that $\operatorname{lcm}(m,n) = \dfrac{mn}{\gcd(m,n)}$.