# Show that lcm$(a,b)= ab$ if and only if gcd$(a,b)=1$

Not sure how to begin. If gcd$(a,b)=1$ what can I deduce from that?

• The answer to this question may depend on the particular theorems that you already have at your disposal. For example, are you permitted to use the fact that lcm(a,b)*gcd(a,b) = ab? Are you permitted to use the existence and uniqueness of the factorization of a positive integer as a product of primes? – Dave Sep 6 '14 at 0:54
• We have not yet learned existence and uniqueness of the factorization of positive integers. So I think I can use lcm$(a,b)*$gcd$(a,b) = ab$ – atherton Sep 6 '14 at 1:00
• @Mukr. Can you prove the identity or should I help you? – evinda Sep 6 '14 at 1:02
• @evinda I think I got it! We need to show that $gcd(a,b)*lcm(a,b)$ divides $ab$ and then vice versa. Since they are all positve integers, $gcd(a,b)*lcm(a,b) = ab$. Correct? – atherton Sep 6 '14 at 1:10

It is known that:

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

• IF $gcd(a,b)=1$: $$gcd(a,b) \cdot lcm(a,b)=a \cdot b \Rightarrow 1 \cdot lcm(a,b)=a \cdot b \Rightarrow lcm(a,b)=a \cdot b$$
• IF $lcm(a,b)=a \cdot b$: $$gcd(a,b) \cdot lcm(a,b)=a \cdot b \Rightarrow gcd(a,b) \cdot a \cdot b=a \cdot b \Rightarrow gcd(a,b)=1$$
• I doubt the OP would be asking the question if they already knew that stronger property. – Bill Dubuque Sep 6 '14 at 0:52

Hint  note that $n\mapsto ab/n\,$ bijects the common divisors of $\,a,b\,$ with the common multiples $\le ab.$ Being order-reversing it maps the greatest common divisor to the least common multiple, i.e. $\,\gcd(a,n)\mapsto ab/\gcd(a,b) = {\rm lcm}(a,b).\,$ Thus $\,\gcd(a,b)=1\iff {\rm lcm}(a,b) = ab$.

Remark $\$ For more on the (involution) duality between gcd and lcm see here and here.

Outside of the definition of $gcd(a,b)$ and $lcm(a,b)$, this proof only requires you to know that every integer can be expressed as a unique product of primes. I use a contrapositive proof to prove "$\implies$" and a direct proof to prove "$\impliedby$"

By contrapositive, assume $gcd(a,b)=d > 1$. Then $a=dr$ and $b=ds$. So $lcm(a,b) \leq drs < (dr)(ds) = ab$

Now assume $gcd(a,b) = 1$. Writing $a$ and $b$ as a product of primes we have:

$a=p_1p_2...p_n$

$b=q_1q_2...q_m$

Where $p$,$q$ are prime and $p_i \neq q_j$ $\forall i,j$ (or else a and b would have a common divisor greater than 1).

Then, any number divisible by a and b must be of the form:

$k(p_1...p_n)(q_1...q_n)$ for some natural number $k$. Then, the smallest such number that is still divisble by a and b is when k=1. So, $lcm(a,b)=ab$.

• Hello, quick question: Why is $lcm(a,b) \leq drs$? Could you please explain to this beginner? :) – numericalorange Jun 13 '18 at 0:31
• Never mind! I understand it now hehe... – numericalorange Jun 13 '18 at 0:58

If the highest power of prime $p,$ in $a,b$ be $A\ge0,B\ge0$

gcd$\displaystyle(a,b)=\prod p^{\text{min}(A,B)}$; lcm $\displaystyle(a,b)=\prod p^{\text{max}(A,B)}$

$\displaystyle ab=\prod p^{A+B}$

We need $A+B=\text{max}(A,B)$ for each prime $p$ that divides $ab$

But we know $A+B=\text{max}(A,B)+\text{min}(A,B)$

$\displaystyle\implies \text{min}(A,B)=0\implies$ at least one of $A,B$ must be $0$

$\displaystyle\implies$gcd$(a,b)=1$

In this answer, it is shown that $$\gcd(a,b)\,\mathrm{lcm}(a,b)=ab$$ From here it is pretty simple to show that $\mathrm{lcm}(a,b)=ab$ if and only if $\gcd(a,b)=1$.

• It can be proved even simpler via duality between common divisors and common multiples - see my answer. – Bill Dubuque Sep 6 '14 at 5:27