2
$\begingroup$

I'm trying to show that if $\operatorname{gcd}(a,b) = 1$, then $\operatorname{gcd}(ab,a+b)=1$.

I've tried to use the gcd properties: $$\operatorname{gcd}(a,b)=1 \implies \operatorname{gcd}(a,a+b)=1\\\operatorname{gcd}(a,b)\implies\operatorname{gcd}(ab,b^2)=b$$ but I got stuck. Any hint will help.

$\endgroup$
  • $\begingroup$ $\gcd(ab,a+b) = \gcd(ab - (a+b)b,a+b)$ $\endgroup$ – Daniel Fischer Aug 17 '14 at 15:24
1
$\begingroup$

Hint:

Supose $k:=\gcd(ab,a+b) > 1$. Let $p$ be a prime that divides $k$.

Then $p$ divides $ab$ wich means that it divides $a$ or $b$ (but not both because $\gcd(a,b) = 1$.

Can $p$ divide $a+b$?

$\endgroup$
  • 2
    $\begingroup$ No. because you will always be left out with a part (a or b) which p can't divide. so p cannot be greater than 1? $\endgroup$ – user170198 Aug 17 '14 at 15:48
0
$\begingroup$

If integer $d$ divides $ab,a+b;$

$d$ must divide $(a+b)b-ab=b^2$ and $(a+b)a-ab=a^2$

$\implies d$ must divide $(a^2,b^2)=(a,b)^2$

But, $(a,b)=1$

$\endgroup$
0
$\begingroup$

A good method to tackle such problems would be to start by assuming that there is a prime $p$ dividing both $ab$ and $a+b$.

If $p$|$ab$ then $p$|$a$ or $p$|$b$. WLOG assume the former to hold. Then, $p$ will not divide $b$ otherwise $gcd(a,b)=1$ does not hold.

But $p$ divides $a$ and $p$ divides $a+b$. It follows that $p$ divides $b$ also. This is a contradiction to our hypothesis, so our assumption is false.

$\endgroup$
0
$\begingroup$

$\begin{eqnarray}{\bf Hint}\ \ &&{\rm prime}\ p\mid (xy,\,x+y)\\ \iff &&\qquad\ \ \, p\mid\ xy,\, x+y\\ \iff && {\rm mod}\ p\!:\ \color{#c00}{xy\equiv 0}\equiv x+y\\ \iff && {\rm mod}\ p\!:\ [\color{#c00}{x\equiv 0\ \ {\rm or}\ \ y\equiv 0}]\ \ {\rm and}\ \ y\equiv -x,\ \ {\rm \color{#c00}{by}\ unique\ factorization}\\ \iff && {\rm mod}\ p\!:\ \ x\equiv 0\equiv y \end{eqnarray}$

i.e. the union of $\rm\color{#c00}{both\ axes}$ intersects line $\,y\equiv -x\,$ at the origin (viewed geometrically).

$\endgroup$
  • $\begingroup$ See here for a generalization. $\endgroup$ – Bill Dubuque Sep 19 '19 at 18:02
0
$\begingroup$

Proof by contrapositive:

Let (ab, a+b)= d > 1.

Then $d \vert ab$ and $d \vert a+b$.

WLOG, let $d \vert a$.

Since $d \vert a$ and $d \vert a+b$, $d \vert b$ [easy to show]

Therefore, (a,b) is not 1.

$\endgroup$
0
$\begingroup$

Hint $$a^2=a(a+b)-ab$$ $$b^2=b(a+b)-ab$$

Use this to show that for all $a,b$ we have $\mbox{gcd}(ab, a+b)$ divides $\mbox{gcd}(a^2,b^2)$.

$\endgroup$
0
$\begingroup$

We get following two conclusions : $ gcd(a,\;a+b)=1$, $\;\;gcd(b,\;a+b)=1$, thus $gcd(ab, a+b)=1$ otherwise one(or both) of the two conclusions will be wrong.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy