10
$\begingroup$

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?

$\endgroup$

14 Answers 14

20
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I like this proof. Short and sweet. $\endgroup$ – ireallydonknow Dec 20 '13 at 18:59
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – robjohn Dec 20 '13 at 20:17
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Miles Johnson Jan 10 '17 at 5:29
  • $\begingroup$ 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. $\endgroup$ – Miles Johnson Jan 10 '17 at 5:36
  • $\begingroup$ Just in case anyone was wondering how to finish the proof. $\endgroup$ – Miles Johnson Jan 10 '17 at 5:37
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Everything looks good. It takes a bit of work to verify that your $c$ and $d$ work, but they do. +1 $\endgroup$ – robjohn Dec 20 '13 at 19:22
  • $\begingroup$ I just noticed that your solution looks pretty close to Henning's with $p=i$ and $q=j$. $\endgroup$ – robjohn Dec 20 '13 at 20:14
  • $\begingroup$ @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.$ $\endgroup$ – Bill Dubuque Dec 20 '13 at 20:24
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

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

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.