5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Dave Sep 6 '14 at 0:54
  • $\begingroup$ 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$ $\endgroup$ – atherton Sep 6 '14 at 1:00
  • $\begingroup$ @Mukr. Can you prove the identity or should I help you? $\endgroup$ – evinda Sep 6 '14 at 1:02
  • $\begingroup$ @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? $\endgroup$ – atherton Sep 6 '14 at 1:10
1
$\begingroup$

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 $$
$\endgroup$
  • 4
    $\begingroup$ I doubt the OP would be asking the question if they already knew that stronger property. $\endgroup$ – Bill Dubuque Sep 6 '14 at 0:52
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

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

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$

$\endgroup$
0
$\begingroup$

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

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

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.