# Elementary Number Theory. Test Question.

If $a,b$ greater than or equal to 1 and if the $\text{gcd}(a,b)=1$ explain how we know that the $\text{lcm}(a,b)=ab$.

-
If $\gcd(a,b) = 1$, then $a \mid t$ and $b \mid t$ implies $ab \mid t$. –  Mikko Korhonen Sep 19 '12 at 15:04
Related to, if not a duplicate of math.stackexchange.com/questions/194961/… –  lhf Sep 19 '12 at 16:19

There are really two flavours of answers that one can give here. If you want an answer by prime factorization, then suppose we have $$a = p_1^{\alpha_1}\cdots p_k^{\alpha_k}$$ $$b = p_1^{\beta_1}\cdots p_k^{\beta_k}$$ where $\alpha_i$ and $\beta_i$ are non-negative integers (possibly zero). Since $\gcd(a,\ b)$ divides both $a$ and $b$, it must be composed of only the primes listed here. To make a number which is large as possible and still divides both numbers, we must take the largest possible exponent for each prime and to do that we are limited by $\min(\alpha_i,\ \beta_i)$ for each prime. Therefore we have $$\gcd(a,\ b) = p_1^{\min(\alpha_1,\ \beta_1)}\cdots p_k^{\min(\alpha_k,\ \beta_k)}$$ In contrast, to make $\mathrm{lcm}(a,\ b)$ we must take the smallest exponent for each prime such that $a$ and $b$ still divides the resulting number. Again, we are limited this time by $\max(\alpha_i,\ \beta_i)$ for each prime exponent and we get $$\mathrm{lcm}(a,\ b) = p_1^{\max(\alpha_1,\ \beta_1)}\cdots p_k^{\max(\alpha_k,\ \beta_k)}$$ Since $$\alpha_i + \beta_i = \max(\alpha_i,\ \beta_i) + \min(\alpha_i,\ \beta_i)$$ we have the following equality $$ab = p_1^{\alpha_i + \beta_i}\cdots p_k^{\alpha_i + \beta_i}$$ $$=p_1^{\max(\alpha_1,\ \beta_1) + \min(\alpha_1,\ \beta_1)}\cdots p_k^{\max(\alpha_k,\ \beta_k) + \min(\alpha_k,\ \beta_k)}$$ $$=\mathrm{lcm}(a,\ b)\cdot \gcd(a,\ b)$$ So your formula is a special case of $$gcd(a,\ b)\cdot \mathrm{lcm}(a,\ b) = ab$$

There is another standard proof which exploits divisibility properties of gcds and lcms in which all this prime mechanism is hidden away.

For that proof let us write the lcm as $m$ and the gcd as $d$. Let us write $a = a'd$ and $b=b'd$. Then since $d\mid ab$ we have $nd = ab$. Also $nd = a'db \implies n = a'b$ so that $b\mid n$. Similarly, $a\mid n$.

From Bezout's Lemma, we can write $$d = ax + by$$ for some integers $x$ and $y$. Now if we express the lcm in terms of $a$ and $b$ we have $m = ak$ and $m = b\ell$. Finally we have $$md = amx + bmy = ab(\ell x + ky) = nd(\ell x + ky)$$ therefore $n\mid m$ and by definition of lcm we have $m\mid n$ therefore $m=n$. So again we have $$gcd(a,\ b)\cdot \mathrm{lcm}(a,\ b) = ab$$

-

Since gcd$(a, b) = 1$, there exist integers $x, y$ such that $ax + by = 1$. Let $d$ be an integer such that $a|d, b|d$. Since $d = adx + bdy$, $ab|d$. Hence lcm$(a, b) = ab$.

-

For any two integers $a,b$

$lcm(a,b)\cdot gcd(a,b)=ab$

As $gcd(a,b)=1$ (given) $\implies lcm(a,b)=?$

-

Hint $\rm\quad \begin{eqnarray}\rm b\:|\:m\ \Rightarrow\ ab\:|\:am\\ \rm a\:|\:m\ \Rightarrow\ ab\:|\:bm\end{eqnarray}\ \ \Rightarrow\ ab\:|\:(am,bm)\, =\, (a,b)m\, =\, m\ \$ by $\rm\ \ (a,b) = 1.$

Thus $\rm\:ab\:$ is a common multiple of $\rm\:a,b\:$ that, by above, divides every common multiple $\rm\:m\:$ of $\rm\:a,b.\:$ Therefore $\rm\:ab\:$ is the least common multiple, since $\rm\:ab\:|\:m\:\Rightarrow\: ab\le m.$

Remark $\$ If above one employs the linear representation of the gcd (Bezout's Identity), replacing $\rm\:(a,b)\:$ by $\rm\:ax + by,\:$ then one obtains essentially the proof in Makoto's answer (this trades off use of the gcd distributive law for the distribute law in $\Bbb Z).\:$ The above proof is more general since there are rings with gcds not of linear (Bezout) form. Further, the above presentation highlights the key role played by the distributive law for gcds, i.e. $\rm\:(a,b)\,c = (ac,bc).$

A similar proof yields the generalization $\rm\ gcd(a,b)\,lcm(a,b)\, =\, ab,\ \$ the gcd $*$ lcm law, which yields the sought equality for the special case $\rm\:gcd(a,b) = 1.$

-