Prove the LCM (Least Common Multiple).

$\newcommand{\lcm}{\operatorname{lcm}}$

Let $m,n$ $\in$ $\Bbb N$. The least common multiple ($\lcm$) of $m,n$ is the smallest natural number $x$, such that $m \mid x$ and $n \mid x$. Prove that the $\lcm$ of $m,n$ is equal to ${m,n\over \gcd(m,n)}$.

Here is my proof so far:

${m,n\over \gcd(m,n)}$ is a common multiple of m and n.

I am assuming that $q_m$ and $q_n$ are coprime.

If $m = q_m \gcd(m,n)$ & $n = q_n \gcd(m,n)$, then ${m,n\over \gcd(m,n)}$ becomes ${q_m \gcd(m,n)q_n \gcd(m,n)\over \gcd(m,n)}$ which equals $q_m q_n \gcd(m,n)$.

So, $m \mid q_m \gcd(m,n)q_n$ & $n \mid q_n \gcd(m,n)q_m$.

Taking $x$ into consideration, $m \mid x$ and $n \mid x$, $x = k_1 m$ and $x = k_2 n$ which is $x = k_1 q_m \gcd(m,n)$ and $x = k_2 q_n \gcd(m,n)$. Since $x$ is equal to itself, we set these equal to each other:

$k_1 q_m \gcd(m,n) = k_2 q_n \gcd(m,n)$

$k_1 q_m = k_2 q_n$

${k_1 \over q_n} = {k_2 \over q_m}$.

So now I'm not really sure where to go from this point. It doesn't really feel like I've proven anything at all...

Update After using the suggestions below and amending my homework, I turned it in to my professor and he said absolutely none of what I said made any sense and refused to give me any homework points. Without a doubt in my mind I believe that my answer was correct, or at least made sense, so I am leaving this question up here to assist other users. I'm just forewarning you that my professor made it fairly clear to me that none of what I had written made any sense so please use this problem with caution. Thank you to everyone that helped me better understand this proof, I really appreciated it.

• I changed $gcd$ to $\gcd$, $lcm$ to $\operatorname{lcm}$, and $a\ | \ b$ to $a\mid b$. That is standard $\TeX$ usage. Commented Nov 11, 2012 at 20:32

3 Answers

Hint $$\rm\,\ m,n\mid x\!\iff\! mn\mid mx,nx\!\iff\! mn\mid\overbrace{(mx,nx)}^{\textstyle (m,n)x}\!$$ $$\rm\iff\! \overbrace{mn/(m,n)}^{\textstyle \ell}\mid x$$

Let $$\rm\:x = \ell\:$$ in $$\,(\Leftarrow)\,$$ to get $$\rm\:m,n\mid \ell,\:$$ i.e. $$\rm\:\ell\:$$ is a common multiple of $$\rm\:m,n,\:$$ necessarily the least common multiple, since $$(\Rightarrow)$$ shows $$\rm\:m,n\mid x\:\Rightarrow\:\ell\mid x\:\Rightarrow\:\ell\le x.$$

Remark $$\$$ That $$\rm\: m,n\mid x\iff \ell\mid x\,$$ is a definition of $$\rm\,{\rm lcm}(m,n)\,$$ in more general rings since - as above - it implies that $$\,\ell\,$$ is a common multiple of $$\rm\,a,b\,$$ that is divisibly least, i.e. it divides every common multiple. See this answer for this universal approach to LCMs and GCDs.

• Above we used the GCD Distributive Law $\,\rm (mx,nx) = (m,n)x,\,$ (which ends up being the distributive law for integers if you replace the gcd by its Bezout linear representation). Commented Jul 3, 2022 at 5:41

When $$m,n$$ are coprime $$\newcommand{\lcm}{\operatorname{lcm}}\lcm(m,n)=mn$$, now consider $$dm,dn$$ (every pair of numbers may be written this way) $$\lcm(dm,dn)=d \lcm(m,n)=dmn = \frac{(dm)(dn)}{d} = \frac{(dm)(dn)}{\gcd(dm,dn)}$$.

• Note that this argument assumes (w/o proof) the law $\,{\rm lcm}(dm,dn) = d\,{\rm lcm}(m,n).\,$ This may yield a circular proof in many contexts, since often that law is proved by replacing lcm by gcd using the sought result here. See here for a proof of the lcm distributive law that avoids such circularity. Commented Jul 3, 2022 at 5:59

You are almost at the end! We have $k_1q_m=k_2q_n$. But $q_m$ and $q_n$ are relatively prime. That will tell us something about $k_1$, and therefore about the size of $x$.