# If $(a,b)=1$ then prove $(a+b, ab)=1$.

Let $$a$$ and $$b$$ be two integers such that $$\left(a,b\right) = 1$$. Prove that $$\left(a+b, ab\right) = 1$$.

$$(a,b)=1$$ means $$a$$ and $$b$$ have no prime factors in common

$$ab$$ is simply the product of factors of $$a$$ and factors of $$b$$.

Let's say $$k\mid a+b$$ where $$k$$ is some factor of $$a$$.

Then $$ka=a+b$$ and $$ka-a=b$$ and $$a(k-l)=b$$.

So $$a(k-l)=b, \ a\mid a(k-1)$$ [$$a$$ divides the left hand side] therefore $$a\mid b$$ [the right hand side].

But $$(a,b)=1$$ so $$a$$ cannot divide $$b$$.

We have a similar argument for $$b$$.

So $$a+b$$ is not divisible by any factors of $$ab$$.

Therefore, $$(a+b, ab)=1$$.

Would this be correct? Am I missing anything?

Suppose that the gcd is not $1$. Then there is a prime $p$ that divides $ab$ and $a+b$.

But then $p$ divides one of $a$ or $b$, say $a$. Since $p$ divides $a+b$, it follows that $p$ divides $b$. This contradicts the fact that $a$ and $b$ are relatively prime.

• I like this proof. Short and sweet. – ireallydonknow Dec 20 '13 at 18:59

Your jump from "$k\mid a+b$ with $k\mid a$" to $ka=a+b$ seems to be wrong. Just because $k$ is a factor of $a$ doesn't mean at all that the number of times it divides $a+b$ is exactly $a$. That seems to kill the rest of your argument.

Instead, here is an approach that doesn't mention prime factors at all. It starts from the well-known property that $(a,b)=1$ exactly if there are $p,q\in\mathbb Z$ such that $pa+qb=1$.

Square $pa+qb=1$ to get $$p^2a^2 + q^2b^2 + 2pqab = 1$$ If we can show that each of the terms on the left-hand side of this is an integer combination of $a+b$ and $ab$, then the right-hand side is too.

But $2pqab$ is clearly an integer combination of $a+b$ and $ab$ namely $0(a+b)+2pq\cdot ab$.

And $a^2 = a(a+b)-ab$, so $p^2a^2 = p^2a(a+b)-p^2\cdot ab$.

Similarly $q^2b^2 = q^2b(a+b)-q^2\cdot ab$.

Collecting everything, $(p^2a+q^2b)(a+b)+(2pq-p^2-q^2)ab=1$, so $(a+b,ab)=1$.

• Nice. (+1) I came up with another Bezout Identity approach. The coefficient of $ab$ is the same, so I assume the coefficient of $a+b$ is, too; it is just not as obvious. – robjohn Dec 20 '13 at 20:17

HINT: Suppose that $p$ is a prime that divides $ab$ and $a^2+b^2$. Then $p$ divides both $a^2+2ab+b^2=(a+b)^2$ and $a^2-2ab+b^2=(a-b)^2$. This in turn implies that $p$ divides both $a+b$ and $a-b$. (Why?) Use this to show that $p$ divides both $a$ and $b$.

• If p is even, then both $ab$ and $a^2+b^2$ must be even as well. The second can only be true in a and b are both even or both odd. If they are both even, they are not coprime, and if they are both odd $ab$ is not even. – Miles Johnson Jan 10 '17 at 5:29
• Therefore p is not even. Since $p$ divides $a+b$ and $a-b$, for some integers $k$ and $z$, we may say $(a+b)/p=k, (a-b)/p=z$. Adding the two, we have $2a/p=k+z$, implying, since $p$ is not even, that $p$ divides $a$. Subtracting the second from the first, we have $2b/p=k-z$, implying for the same reason that $p$ divides $b$. But $p$ cannot divide both numbers, so we have found a contradiction. – Miles Johnson Jan 10 '17 at 5:36
• Just in case anyone was wondering how to finish the proof. – Miles Johnson Jan 10 '17 at 5:37

HINT: $a^2 + b^2 +2ab = (a+b)^2.$

$\begin{eqnarray}\rm{\bf Hint}\,\ \ 1\!=\!(a,b)\!\overset{Bexout}\Rightarrow\! 1=\color{sienna}{ia\!+\!jb}\, \Rightarrow &&\rm \color{#0a0}{ab}c\!+\!(\color{blue}{a\!+\!b})d\! =\! (\color{sienna}{ia\!+\!jb})^2\! = \color{#c00}1\\ \rm thus\quad n\,\mid &&\rm \color{#0a0}{ab}\ \, \&\, \ \color{blue}{a\!+\!b}\,\ \Rightarrow\,\ n\mid\color{#c00} 1\end{eqnarray}\!$ $\!\begin{eqnarray}\rm \ \overset{\phantom{B}}for\ \ \ c &=&\rm\, 2ij\!-\!i^2\!-\!j^2 \\ \rm d &=&\rm \, i^2a\!+\!j^2b\end{eqnarray}$

Remark $\$ The genesis of the proof is ideal-theoretic, as is explained in this post, which presents a handful of proofs of the more general identity $\rm\ (a\!+\!b,\ lcm(a,b)) = (a,b).$ The above is essentially a Bezout form of the the last proof there (which is more general than a proof using primes, since it works in any gcd domain - where primes need not exist).

• Everything looks good. It takes a bit of work to verify that your $c$ and $d$ work, but they do. +1 – robjohn Dec 20 '13 at 19:22
• I just noticed that your solution looks pretty close to Henning's with $p=i$ and $q=j$. – robjohn Dec 20 '13 at 20:14
• @robjohn I hadn't read that. I agree, they do appear to use the same form of the Bezout identity. I derived it as in the linked post. In some sense the Bezout proofs will all be the same, modulo a shift by $\,\pm k\, (a+b, -ab)$ to obtain another solution $\,ab\,x +(a+b)\,y = 1.$ – Bill Dubuque Dec 20 '13 at 20:24

You say:

Let’s say $k\mid a+b$ where $k$ is some factor of $a$.

Then $ka=a+b$ ...

This step really doesn’t make any sense as written. If $k\mid a+b$, there is some integer $m$ such that $km=a+b$, but there’s certainly no reason to think that $m=a$. What you want to do at this point is use the hypothesis that $k\mid a$: there is some integer $n$ such that $a=kn$, and therefore $km=kn+b$. Now you can solve for $b$ and observe that $k\mid b$. But then $k$ is a common divisor of $a$ and $b$, so $k=\pm1$, and you’ve shown that $\gcd(a,a+b)=1$.

A similar argument shows that $\gcd(b,a+b)=1$, and then your last step is fine.

Here is another proof using Bezout's Identity: \begin{align} ma+nb&=1\tag{1}\\ (n-m)b&=1-m(a+b)\tag{2}\\ (m-n)a&=1-n(a+b)\tag{3}\\ -(m-n)^2ab&=1-(m+n)(a+b)+mn(a+b)^2\tag{4}\\ 1&=((m+n)-mn(a+b))\color{#C00000}{(a+b)}-(m-n)^2\color{#C00000}{ab}\tag{5} \end{align} Explanation:
$(1)$: $(a,b)=1$ and Bezout's Identity
$(2)$: subtract $m(a+b)$ from both sides of $(1)$
$(3)$: subtract $n(a+b)$ from both sides of $(1)$
$(4)$: multiply $(2)$ and $(3)$
$(5)$: rearrange and collect terms of $a+b$ and $ab$ from $(4)$

Bezout's Identity and $(5)$ say that $(a+b,ab)=1$.

Henning Makholm and Bill Dubuque also give Bezout Identity based proofs. The coefficient of $ab$ is the same in all of our answers, but the coefficient of $a+b$ in mine looks different from theirs. They are the same however: \begin{align} (m+n)-mn(a+b) &=(m+n)\overbrace{(ma+nb)}^{1}-mn(a+b)\\ &=m^2a+n^2b+mn(a+b)-mn(a+b)\\ &=m^2a+n^2b \end{align}

Intuitively, if a factor divides $a$ but not $b$ then it divides $ab$ and $a^2$ but not $b^2$, hence not $a^2+b^2$.

More formally, notice that if $a$ and $b$ are coprime then they are also coprime to $a+b$ and hence $ab$ is coprime to $(a+b)^2 = a^2 + 2ab+b^2$.

• I quite like this one; +1. – Brian M. Scott Jan 10 '17 at 5:59

By contradiction, let $d>1$ divide both $ab$ and $a^2+b^2$. Then $d$ has a prime divisor $p$, which divides both $ab$ and $a^2+b^2$.

Then, $p|a(a+b) - ab = a^2$ Since $p$ is a prime which divides $a^2$ $\implies$ that $p|a$.

And $p|b(a+b) - ab = b^2$ $\implies$ $p|b$.

Hence $p|a$ and also, $p|b$, so $p$ divides $gcd(a,b) = 1$. However, this forces $p = 1$, which is a contradiction, since 1 isn't a prime.

Thus the only positive common divisor of $ab$ and $a^2+b^2$ is $1$, and hence they are coprime.

If $d$ divides $a+b$ and $d$ divides $ab$, then $d$ divides $a(a+b)-ab = a^2$. Similarly, $d$ divides $b^2$. Thus $d$ divides $(a^2,b^2$). But $(a^2,b^2) = (a,b)^2 = 1$, so $d=1$.

Yet another approach: it's straightforward to show that $(i, jk) | (i,j)\cdot(i, k)$. It's also a classic theorem of the GCD that $(m, n) = (m, m+n)$ (this principle underlies the Euclidean algorithm). Then we have $(a, a+b)=(a, b)=1$, and $(b, a+b) = (b, a) = 1$, so $(ab, a+b)|(a, a+b)\cdot(b, a+b) = 1\cdot 1$.

We know that the prime factors of $ab$ is either a factor of $a$ or $b$ but not the other due to $gcd(a,b) = 1$. However, $a+b$ is not divisible by a prime factor of $a$ nor $b$ because the division yields an integer plus a 'decimal number'. Hence, by the fundamental theorem of arithmetic, it is not divisible by any factors of $ab$.

Suppose $\text{gcd}(a,b) = 1$, but $\text{gcd}(ab,a^2+b^2) = d$, where $d > 1$. Let p be a prime factor of d. Then

$$d|ab \implies p|ab \implies p|a \text{ or } p|b$$

Without loss of generality, assume p|a. Then

$$d|(a^2 + b^2) \implies p|(a^2 + b^2) \implies p|b^2 \implies p|b$$

contrary to $\text{gcd}(a,b)=1$.

For variety here's a proof using Gaussian integers. They are UFD so enjoy GCDs, Euclid's Lemma, etc.

$(a,b) = 1\,\Rightarrow\, (a\pm bi,b) = (a,b) = 1.\,$ Similarly $\,(a\pm bi,a) = 1.\,$ So by Euclid $\,a,b$ are coprime to $\,(a-bi)(a+bi) = a^2+b^2\,$ hence so too is their product $\,ab.$