4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – sharris Jun 9 '15 at 18:11
  • $\begingroup$ 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). $\endgroup$ – anakhro Jun 9 '15 at 18:13
10
$\begingroup$

Hint $\,\ n,m\mid k \!\iff\! nm\mid nk,mk\!\iff\! nm\mid (nk,mk) = (n,m)k\!\iff\! nm/(n,m)\mid k$

Remark $\ $ If we bring to the fore the implicit reflection symmetry we obtain a simpler proof: $\,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.

$\endgroup$
2
$\begingroup$

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

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

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.