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$ 016 Answers
$\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$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 $\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$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$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$HINT: $a^2 + b^2 +2ab = (a+b)^2.$
$\endgroup$ $\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$ $\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$ $\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$ $\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$ $\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$ $\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$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$ $\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$ $\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$ $\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
