3
$\begingroup$

Could someone please tell me whether my proof is okay? I was inspired by this proof and yet I was confused what they meant by common divisor and how it connects to common multiple.

If $\gcd(a,b)=1$, then $\operatorname{lcm}(a,b)=ab$.

Assume $\gcd(a,b)=1$. Then $a$ and $b$ are relatively prime. Then let $a=p_{1}p_{2}\cdots p_{n}$ and $b=q_{1}q_{2}\cdots q_{m}$ for primes $p_{i}$ and $q_{j}$ with $p_{i}\neq q_{j}$ for all $i,j$. Let $m$ be a common multiple of $a$ and $b$. Then $a \mid m$ and $b \mid m$. Since $\gcd(a,b)=1$, $ab \mid m$. Then there exists a positive integer $k$ such that $m=abk=(p_{1}p_{2}\cdots p_{n})(q_{1}q_{2}\cdots q_{m})k$. Then the least common multiple of $a$ and $b$ would be when $k=1$. Then $\operatorname{lcm}(a,b)=ab$.

I really do not find my proof very good. I get confused in the last part, connecting $abk$ with $\operatorname{lcm}(a,b)$. Any help is appreciated…

$\endgroup$
  • 3
    $\begingroup$ "Then let $a=p_1p_2...p_n$." This might not be true. For example, $4=2^2$. You need to put the powers on as well. $\endgroup$ – abc... Jun 13 '18 at 2:01
  • 3
    $\begingroup$ The $p_i$'s are not required to be pairwise distinct. $\endgroup$ – Suzet Jun 13 '18 at 2:15
5
$\begingroup$

Your proof is correct, but you need not use the decomposition of an integer into prime factors. More elementary arguments work here.

As you said, because $\operatorname{gcd}(a,b)=1$, any common multiple of $a$ and $b$ is in fact a multiple of $ab$. Conversely, any multiple of $ab$ is a common multiple of $a$ and $b$.

Hence, the least common multiple must be $ab$ itself.

NB: to justify that any common multiple of $a$ and $b$ is in fact a multiple of $ab$, we can proceed by using Bézout's theorem. We are given a relation $$au+bv=1$$ where $u,v$ are integers. Now, let $m$ be a common multiple of $a$ and $b$. Let us write $m=aa'=bb'$. Then $$m=aa'=(a^2u+abv)a'=(aa')au+(ab)a'v=(bb')au+(ab)a'v=ab(b'u+a'v)$$ With this, the proof is complete with only elementary arguments.

NB2: As @abc... stated, it is in general true that $ab=\operatorname{gcd}(a,b)\operatorname{lcm}(a,b)$. We can now prove this without using the decomposition into prime factors, thanks to the fact that if $k$ is any integer, then $k\operatorname{gcd}(a,b)=\operatorname{gcd}(ka,kb)$ and $k\operatorname{lcm}(a,b)=\operatorname{lcm}(ka,kb)$.

Indeed, given $a,b$, it follows from this property than $\operatorname{gcd}(\frac{a}{\operatorname{gcd}(a,b)},\frac{b}{\operatorname{gcd}(a,b)})=1$. Applying the proven result, we know that $\operatorname{lcm}(\frac{a}{\operatorname{gcd}(a,b)},\frac{b}{\operatorname{gcd}(a,b)})=\frac{ab}{\operatorname{gcd}(a,b)^2}$. Now, multiply both sides by $\operatorname{gcd}(a,b)^2$ to get the result.

$\endgroup$
  • 1
    $\begingroup$ Thank you for taking the time to reply and explain in a very clear way another way of looking at the proof. :) $\endgroup$ – numericalorange Jun 13 '18 at 2:31
4
$\begingroup$

There is an easier proof. By the fundamental theorem of arithmetic, $$a=\prod_{i=1}^{i=n}p_i^{a_i}$$ and $$b=\prod_{i=1}^{i=n}p_i^{b_i}$$ $a_i$ and $b_i$ can be $0$.

Now, $$lcm(a,b)=\prod_{i=1}^{i=n}p_i^{\max(a_i,b_i)}$$ while $$gcd(a,b)=\prod_{i=1}^{i=n}p_i^{\min(a_i,b_i)}$$ Thus, lcm(a,b)*gcd(a,b)=ab.

Since gcd(a,b)=1, lcm(a,b)=ab.

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