14
$\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$
0

16 Answers 16

24
$\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$
2
  • $\begingroup$ I like this proof. Short and sweet. $\endgroup$ – ireallydonknow Dec 20 '13 at 18:59
  • $\begingroup$ This method can be motivated intuitively as a generalization of Euclid's method for generating (co)primes - see this answer here. $\endgroup$ – Bill Dubuque Dec 16 '19 at 18:55
9
$\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$
2
  • 1
    $\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
  • $\begingroup$ Worth emphasis - at the heart of this method is a classical (bi-)quadratic composition identity (a generalization of the classical Brahmagupta–Fibonacci identity for composition of squares). See this answer here for that viewpoint. $\endgroup$ – Bill Dubuque Dec 16 '19 at 19:02
5
$\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$
1
  • $\begingroup$ Generally $\,(a,c)(b,c) = (ab,c)$ when $\,(a,b,c)=1\,$ as proved in this answer here. The proof in Rob's answer is essentially a Bezout based proof of this in the special case $\,c=a\!+\!b,\,(a,b)=1.\,$ In Rob's $(5)$ if we use his equivalent expression $\,m^2a+n^2b\,$ and replace $1$ on the LHS by $\,(ma+nb)^2\,$ it becomes the first identity in the linked answer, which is a classical composition of squares identity. $\endgroup$ – Bill Dubuque Dec 16 '19 at 21:09
5
$\begingroup$

[This answer was merged from a question concerning $\rm\color{#0a0}{Bezout}$-based proofs]

Note $\ (\color{#c00}{a\!+\!b}) (ai^2\!+\!bj^2)= \color{#0a0}{(ai\!+\!bj)^2}\ \!\!+ \color{#c00}{ab}(i\!-\!j)^2\, $ by calculation (or by composition - see below)
thus $\ \ n^{\phantom{|^|}}\!\!\!\mid\color{#c00}{a\!+\!b,ab}\,\Rightarrow\, n\mid\color{#0a0}{(ai\!+\!bj)^2}\!=1^2\ $ by choosing $\,\color{#0a0}{ai\!+\!bj}=1\,$ by $\,(a,b)=1\,$ & Bezout.

Or: $\,\ \ (\color{#c00}{a\!+\!b}) (ai\!+\!bj)\,=\, \color{#0a0}{a^2i\!+\!b^2j}\,+\, \color{#c00}{ab}(i\!+\!j)\ $
thus $\,n^{\phantom{|^|}}\!\!\!\mid\color{#c00}{a\!+\!b,ab}\,\Rightarrow\, n\mid\color{#0a0}{a^2i\!+\!b^2j}\!=1\ $ by choosing $\,i,j\,$ to get Bezout for $\,(a^2,b^2)=1\,$

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 $\, (a\!+\!b,\,{\rm 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 needn't exist). In fact OP is case $\, c=a\!+\!b,\,(a,b)\!=\! 1\,$ of

$$(a,b,c)=1\,\Rightarrow\, (a,c)(b,c) = (ab,c(a,b,c)) = (ab,c)\qquad$$

More classically, the first identity may be viewed conceptually as the special case $\,x=1=y\,$ in the biquadratic composition of quadratic forms in the Lemma below (used by Euler) whose proof by norm multiplicativity is an obvious generalization of the classical proof when $\,a=1=b.$

Lemma $\ \ (ax^2+by^2) (ai^2+bj^2)= (aix\!+\!bjy)^2\ \!\!+ ab(iy\!-\!jx)^2$

$\!\begin{array}{rll}{\bf Proof}\qquad\qquad\ \ (ax^2+by^2)&\!\!\!\!\!\!(ai^2+bj^2)&\!\! =\ N(\alpha)N(\beta)\\[.2em] \!\!\!\!\!(x\sqrt a\!+\!y\sqrt{-b})(x\sqrt a\!-\!y\sqrt{-b})&\!\!\!\!\!\!(i\sqrt a\!-\!j\sqrt{-b})\ (i\sqrt a\!+\!j\sqrt{-b})&\!\!=\ \ \ \alpha\,\bar\alpha\,\beta\,\bar\beta\\[.2em] (x\sqrt a\!+\!y\sqrt{-b})\ (i\sqrt a\!-\!j\sqrt{-b})&\!\!\!\!\!\!(x\sqrt a\!-\!y\sqrt{-b})(i\sqrt a\!+\!j\sqrt{-b})&\!\!=\ \ \ \alpha\,\beta\,\bar\alpha\,\bar\beta\\[.2em] (aix\!+\!bjy\! +\! (iy\!-\!jx)\sqrt{-ab})&\!\!\!\!\!\!(aix\!+\!bjy\! -\! (iy\!-\!jx)\sqrt{-ab} )&\!\!= \ \ \ \alpha\beta\:\smash[t]{\overline{\alpha\beta}}\\[.2em] (aix\!+\!bjy)^2\ &\!\!\!\!\!\!\!+ ab(iy\!-\!jx)^2 &\!\!= \ \ N(\alpha\beta)\end{array}$

$\endgroup$
4
  • $\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
  • $\begingroup$ @robjohn I found some time to elaborate to explain the classical view in terms of composition of quadratic forms. $\endgroup$ – Bill Dubuque Dec 16 '19 at 6:13
4
$\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$
3
  • $\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$
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$
2
$\begingroup$

This can be solved intuitively by using a slight twist on Euclid's idea for generating new primes. Euclid employed $\,1 + p_1\cdots p_n$ is coprime to $\,c = p_1\cdots p_n.\,$ Stieltjes noted the generalization that, furthermore, $\ \color{#c00}{p_1\cdots p_k} +\, \color{#0a0}{p_{k+1}\cdots p_n}\,$ is coprime to $\,c\,$ too, which motivates the following

Key Idea $\, $ Coprimes to $\,c\,$ arise by partitioning into $\rm\color{#c00}{two}\ \color{#0a0}{summands}$ all prime factors of $\,c,\,$ i.e.

Theorem $\ \ \color{#c00}a+\color{#0a0}b\ $ is coprime to $\ c\:$ if every prime factor of $\,c\,$ divides $\,a\,$ or $\,b,\,$ but not both.

Proof $\ $ If it fails then $\,a+b\,$ and $\,c\,$ have a common prime factor $\,p.\,$ By hypothesis $\,p\mid a\,$ or $\,p\mid b,\,$ w.l.o.g. say $\,p\mid b.\,$ Then $\,p\mid (a+b)-b = a,\,$ so $\,p\,$ divides both $\,a,b,\,$ contra hypothesis.

Corollary $\ \ (a,b)=1\,\Rightarrow\, (a+b,ab) = 1$

Remark $\ $ Note how the solution becomes quite obvious after employing Stieltjes idea. More generally it yields a "coprime" version of Dirichlet's result on primes in arithmetic progression

$$(a,b,c)=1\,\Rightarrow\,(an+b,c) = 1\ \ \ {\rm for\ some}\ n\qquad$$

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

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$
1
  • $\begingroup$ I quite like this one; +1. $\endgroup$ – Brian M. Scott Jan 10 '17 at 5:59
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$

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$
0
$\begingroup$

A proof in Gaussian integers $\Bbb Z[i].\,$ They are Euclidean $\Rightarrow$ 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\,$ thus so too is their product $\,ab.$

$\endgroup$
0
$\begingroup$

Suppose that gcd(a,b)=1.

Let d=gcd(a+b,ab).

Now d|(a+b) and d|ab.

Suppose that d|a.

Then a=dqa.

Now examining a+b=dq1 we have dqa+b=dq1 b=d(q1−qa).

So then d|b and d=1.

A similar argument shows d|b implies d|a.

So we know that d|a or d|b implies d=1.

Suppose that d∤b and d∤a.

We have a+b=dq1 a=dq1−b.

Here we have that gcd(a,−b)=1=gcd(a,d) (this is from a Lemma used in the proof of the Euclidean Algorithm).

We can also derive that gcd(b,−a)=1=gcd(b,d).

So we know that a and d and b and d are both relatively prime.

Considering d|ab we know by Euclid's Lemma that since a and d are relatively prime implies that d|b.

This contradicts our assumption, so this case is not possible.

Therefore, we may conclude that d=1. □

$\endgroup$
1
  • $\begingroup$ I found this question in Elementary Number Theory 7th edition, by Bartle. Section 2.4, Question 6. $\endgroup$ – fantasticasm89 Jan 22 at 19:24

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.