0
$\begingroup$

What's the simplest proof that the least common divisor of $a$ and $b$ is equal to the product of $a$ and $b$ divided by the greatest common divisor, i.e.:

$$\operatorname{LCM}(a,b)=\frac{ab}{gcd(a,b)}$$

and that

$$\gcd(a,b)\le |a-b|,\ \ {\rm for}\ \ a\neq b$$

Note: $ $ the original version was: $\ \,\gcd(a,b) < |a-b|,\,$ but that has trivial counterexamples, e.g. see the comments below.

$\endgroup$
4
  • 2
    $\begingroup$ The second is false, let $a=b=1$ or let $a=2$ and $b=1$. $\endgroup$ Nov 15, 2014 at 17:09
  • $\begingroup$ Is it true in this form: $gcd(a,b)\leq |a-b|$? $\endgroup$
    – chen h.
    Nov 15, 2014 at 18:21
  • $\begingroup$ @chenh. $\gcd(1,1) = 1 > 0 = |1-1|$, so no. $\endgroup$
    – Tacet
    Nov 15, 2014 at 18:34
  • 1
    $\begingroup$ It is true with $\le$ and $a\ne b$. $\endgroup$ Nov 15, 2014 at 18:53

1 Answer 1

1
$\begingroup$

Let $a = \prod{p_i^{k^a_i}} \wedge b = \prod{p_i^{k^b_i}}$, then note that:

$$\begin{align*}\begin{split} ab &= \prod{p_i^{k^a_i + k^b_i}} \\ \gcd(a, b) &= \prod{p_i^{\min(k^a_i,~k^b_i)}}\\ \mathrm{LCM}(a, b) &= \prod{p_i^{\max(k^a_i,~k^b_i)}} \end{split}\end{align*}$$

Now transform LCM: $$\begin{align*}\begin{split} \mathrm{LCM}(a, b) &= \prod{p_i^{\max(k^a_i,~k^b_i)}}\\ &= \prod{p_i^{(k^a_i + k^b_i) -\min(k^a_i,~k^b_i)}}\\ &=\prod{\frac{p_i^{k^a_i+k^b_i}}{p_i^{\min(k^a_i,~k^b_i)}}}\\ &=\frac{\prod{p_i^{k^a_i+k^b_i}}}{\prod{p_i^{\min(k^a_i,~k^b_i)}}}\\ &=\frac{ab}{\gcd(a,b)} \end{split}\end{align*}$$

Second thesis isn't true. But you can prove $\gcd(a,b) \leq |a-b|$ for $a\neq b$. Assume that $gcd(a,b) = d \wedge a' = \frac{a}{d} \wedge b' = \frac{b}{d}$ and note $a \neq b \Longrightarrow a' \neq b'$, then

$$\begin{align*}\begin{split} &\left(\left(|a'-b'| \neq 0 \wedge a',b' \in \mathbb{Z}\right) \Longrightarrow |a'-b'| \geq 1 \wedge\\ |a-b| = |d\cdot a' - d \cdot b'| = d |a'- b'|\right) \\ &\Longrightarrow |a-b| = d |a'- b'| \geq d = \gcd(a,b) \Longleftrightarrow\\ &|a-b| \geq gcd(a,b) \end{split}\end{align*}$$

$\endgroup$
4
  • $\begingroup$ Thanks. Is the second true if a and b are distinct and greater than 2?? $\endgroup$
    – chen h.
    Nov 15, 2014 at 18:37
  • $\begingroup$ @chenh. Not good enough, $a=m$ and $b=2m$ fail for any $m>0$. $\endgroup$
    – Erick Wong
    Nov 15, 2014 at 19:21
  • $\begingroup$ You need $\leq$ and $a\neq b$ to make it work. $\endgroup$ Nov 15, 2014 at 19:57
  • $\begingroup$ @JoshuaBiderman It wrote André Nicolas in comment and proof to this is in my answer... $\endgroup$
    – Tacet
    Nov 15, 2014 at 20:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .