# 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
• This method can be motivated intuitively as a generalization of Euclid's method for generating (co)primes - see this answer here. – Bill Dubuque Dec 16 '19 at 18:55

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
• 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. – Bill Dubuque Dec 16 '19 at 19:02

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}

• 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. – Bill Dubuque Dec 16 '19 at 21:09

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

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

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

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.

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

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

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

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

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.

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

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

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