Prove $\operatorname{lcm}(a, b) = ab / \gcd(a,b);\ $ $\gcd(a,b) \le |a - b|$ for $a \ne b$

247 Views Asked by At

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.

1

There are 1 best solutions below

4
On BEST ANSWER

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*}$$