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

elementary-number-theorygcd-and-lcmleast-common-multipleproof-verification

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…

Best Answer

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.

Related Question