Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If $\gcd(a,b)=1$, how can I find the values that $\gcd(a+b,a^2+b^2)$ can possibly take? I can't find a way to use any of the elemental divisibility and gcd theorems to find them.

share|cite|improve this question
I added an answer which proves that $ \rm\: (a\!+\!b,\ a^2\!+\!b^2)\,=\,(a\!+\!b,\,2(a,b)^2\!)\:$ for any value of $\rm\:(a,b).\:$ Therefore $ \rm\: (a\!+\!b,\ a^2\!+\!b^2)\,=\,(a\!+\!b,\,2)\:$ in your special case when $\rm\:(a,b) = 1.\:$ – Math Gems Feb 21 '13 at 19:28
up vote 16 down vote accepted

We have $a^2 + b^2 - a(a+b) = b^2 - ab = -b (a-b)$ and $a^2 + b^2 - b(a+b) = a^2 - ba = a (a-b)$.

So if $d$ divides both $a+b$ and $a^2+b^2$, then $d$ divides $$\gcd(a (a-b), b (a-b)) = \gcd(a, b) (a-b) = a - b.$$

So $d$ divides $a+b + a - b = 2a$ and $a+b - (a - b) = 2b$.

So $d$ divides $2\gcd(a,b)=2$.

So the possibilities for the $\gcd$ appear to be $1$ and $2$, and both clearly occur.

share|cite|improve this answer
@StevenStadnicki, thanks for the fix. – Andreas Caranti Feb 18 '13 at 23:18
A well-earned +1, too - this is much cleaner than the approach I was taking. – Steven Stadnicki Feb 18 '13 at 23:26
@StevenStadnicki, thanks, I appreciate. – Andreas Caranti Feb 18 '13 at 23:38
@AndreasCaranti Thanks for your help – Richard Codwater Feb 18 '13 at 23:50
@RichardCodwater, you're welcome. – Andreas Caranti Feb 18 '13 at 23:52

Since $\gcd(a,b)=1$, Bezout's Identity says we have an $x$ and $y$ so that $$ ax+by=1\tag{1} $$ Note that $$ \begin{align} 2a^2&=(a^2+b^2)+(a+b)(a-b)\\ 2ab&=(a+b)^2-(a^2+b^2)\\ 2b^2&=(a^2+b^2)-(a+b)(a-b)\\ \end{align}\tag{2} $$ Therefore, incorporating $(1)$ and $(2)$, $$ \begin{align} 2 &=2(ax+by)^2\\ &=2a^2x^2+4abxy+2b^2y^2\\ &=\Big((a^2+b^2)+(a+b)(a-b)\Big)x^2\\ &+2\Big((a+b)^2-(a^2+b^2)\Big)xy\\ &+\Big((a^2+b^2)-(a+b)(a-b)\Big)y^2\\ &=\color{#00A000}{(x-y)^2}\color{#C00000}{(a^2+b^2)} +\color{#00A000}{((x^2-y^2)(a-b)+2xy(a+b))}\color{#C00000}{(a+b)}\tag{3} \end{align} $$ Equation $(3)$ says that $$ \gcd(a+b,a^2+b^2)\,|\,2\tag{4} $$ Note that $\gcd(1+2,1^2+2^2)=1$ and $\gcd(1+3,1^2+3^2)=2$, so both $1$ and $2$ are possible.

share|cite|improve this answer
Thank you very much. – Richard Codwater Feb 19 '13 at 2:24
One can also prove it more simply without Bezout, using only gcd laws and Euclid's lemma: $$\begin{array}{l}\rm d\,|\ \,\color{#C00}{a+b}\\ \rm d\,|\,a^2\!\!+b^2\\ \end{array}\ \Rightarrow\ \ \rm\begin{array}{l} d\,|\,2a^2\, = \, \color{#C00}{a^2\!\!-\!b^2}\, +a^2\!\!+b^2\\ \rm d\,|\,2b^2\, = \, \color{#C00}{b^2\!\!-\!a^2}\,+a^2\!\!+b^2\end{array}\ \Rightarrow\ \ \rm d\,|\,(2a^2,2b^2)=2(a^2,b^2) = 2$$ – Math Gems Feb 21 '13 at 19:12
@MathGems: Indeed, $(2)$ above is the first $\Rightarrow$, and $(3)$ essentially reproves Euclid's Lemma. I figured there would be other non-Bezout proofs, and so the challenge was to find the linear combination of $a+b$ and $a^2+b^2$ that equals $2$. :-) – robjohn Feb 21 '13 at 20:27
@Rob Your Bezout skills are legends in my circles! – Math Gems Feb 21 '13 at 20:54

$$\begin{align} \gcd(a+b, a^2 + b^2) &= \gcd(a+b, a^2 + b^2 - a(a+b)) \\&= \gcd(a+b, b^2 - ab) \\&= \gcd(a+b, b^2 - ab + b(a+b)) \\&= \gcd(a+b, 2b^2) \end{align} $$

Now, $\gcd(a+b,b) = \gcd(a,b) = 1$, so we can get rid of the factors of $b$ and have

$$ \gcd(a+b, a^2 + b^2) = \gcd(a+b, 2) $$

The strategy I used was still the basic idea of the Euclidean algorithm; since I couldn't compare numeric values, I instead simplified by working to eliminate the variable $a$, starting with the largest power of $a$.

share|cite|improve this answer
Nice answer. I like that you get a formula for the exact gcd (+1) – robjohn Feb 19 '13 at 1:11
Which property or theorem do you use to get rid of the factors of b? – Richard Codwater Feb 19 '13 at 2:23
There are a few things you can do with products. In this case, I invoked: $$\gcd(x,y)=1 \implies \gcd(x,yz) = \gcd(x,z)$$ – Hurkyl Feb 19 '13 at 3:16
@Rob In fact one can give an exact formula $\rm\: (a\!+\!b,\ a^2\!+\!b^2)\,=\,(a\!+\!b,\,2(a,b)^2\!)\:$ even for the case $\rm\:(a,b)\ne 1,\: $ see my answer. – Math Gems Feb 21 '13 at 19:14
@MathGems: neat. unfortunately, I can only upvote once :-) – robjohn Feb 21 '13 at 20:40

By below: $\rm\ \ \ (a\!+\!b,\ a^2\!+\!b^2)\, =\, (2,a\!+\!b)\ $ when $\rm (a,b)=1,\ $ yields the sought gcd.

Theorem $\rm\ \ (a\!+\!b,\ a^2\!+\!b^2)\, =\, (2a^2,\ \ 2ab,\ \ 2b^2,\ a\!+\!b)\, =\, (2(a,b)^2\!,\ a\!+\!b)$

Proof $\rm\,\ mod\ a\!+\!b\!:\ a^2\!+\!b^2 \equiv 2a^2\! \equiv -2ab \equiv 2b^2\ \, $ by $\rm\,a\!+\!b\,$ divides $\rm\color{#0A0}{green}$ terms below

$$\rm a^2\!+\!b^2 = (\color{#0A0}{b^2\!-\!a^2})+2a^2 = (\color{#0A0}{a\!+\!b})^2\!-2ab = (\color{#0A0}{a^2\!-\!b^2})+2b^2 $$

Remark $\ $ We used $\rm\: (c,d_i) = (c,d)\ $ if $\rm\ d_i\equiv d\ (mod\ c);\:$ for example $\rm\: (c,d) = (c,\ d\ mod\ c),\:$ the recursive step (descent) at the heart of the Euclidean algorithm (essentially, what we used).

The final equality $\rm\ 2(a,b)^2 =\, 2(a^2,ab,b^2)\:$ is by gcd laws (associative,distributive, etc), i.e.

$$\rm\ (a,b)(a,b) = ((a,b)a,(a,b)b) = (a^2,ba,ab,b^2) = (a^2,ab,b^2)$$

share|cite|improve this answer

Note that $a^2+b^2=(a+b)^2-2ab$. Thus $a^2+b^2\equiv -2ab\mod a+b$ and you need to find $(a+b,-2ab)=(a+b,2ab)$. Can you move on?

ADD Note that $a,b$ cannot be both even. If one is odd and the other is even, then $2\not\mid a+b$, so $(a+b,2ab)=(a+b,ab)$. But if $p>2$ is a prime with $p\mid a+b,ab$ then $p\mid a$ or $p\mid b$, since $p\mid ab$. But in any case, since $p\mid a+b$, this would give $p \mid b$ (if $p\mid a$) or $p \mid a$ (if $p\mid b)$, contrary to $(a,b)=1$. Thus $(a+b,ab)=1$.

If $a,b$ are both odd, then $a+b$ is even and $2\mid (a+b,2ab)$. And again, if $p$ is an odd prime factor $p\mid 2ab\implies p\mid ab$ and the same argument above goes through. Thus whenever $(a,b)=1$, $$(a+b,a^2+b^2)=\begin{cases} 1 &\text{if one of } a,b \text{ is odd}\\2&\text{if both} a,b\text{ are odd}\end{cases}$$

share|cite|improve this answer
I reduced it upto d divides 2ab. I'm stuck again please help? – ngub05 Oct 24 '13 at 20:05
What is $d$, @BOF? – Pedro Tamaroff Oct 24 '13 at 21:49

$$ gcd(a+b,a^2+b^2) | gcd((a+b)(a-b), a^2+b^2) = gcd(a^2-b^2, a^2+b^2) | gcd [ ( a^2+b^2)+ (a^2-b^2) , ( a^2+b^2)+ (a^2-b^2) ]=2 gcd(a^2,b^2)=2$$

Now it is easy to check that both 1 and 2 are possible...

share|cite|improve this answer
That's essentially the same method as in my un-Bezouted comment to Rob's answer. – Math Gems Feb 21 '13 at 19:30

There are two possible values ​​for $(a+b,a^{2}+b^{2})$ Let's call it $d$ the $gcd(a+b,a^{2}+b^{2})$$$$$ $$(a+b,a^{2}+b^{2})=d\Longrightarrow d\mid a+b\;\text{and}\;d\mid a^{2}+b^{2}$$$$$$$$a^{2}+b^{2}=a^{2}+b^{2}-2ab+2ab=(a+b)^{2}-2ab$$Above we found that the definition of gcd $d\mid a+b\Longrightarrow d\mid (a+b)^{2}$$$$$Since we know that $d\mid (a+b)^2$ and $d\mid (a+b)^2-2ab$ then $d\mid 2ab$$$$$If $d\mid 2ab\Longrightarrow d\mid 2\;\;\text{or}\;\;d\mid ab$$$$$If $d\mid 2\Longrightarrow d=1\;\;\text{or}\;\;d=2$$$$$If $d\mid ab\Longrightarrow d\mid a\;\;\text{or}\;\;d\mid b$$$$$If $d\mid a$ We know by definition that gcd $d\mid a+b$ Starting this, we conclude that $d\mid b$ soon $$d\mid (a,b)\Longrightarrow d\mid 1 \Longrightarrow d=1$$$$$$Similarly, when we use the fact that $d\mid b$ we have that $d=1$$$$$*We conclude then that $(a+b,a^{2}+b^{2})$ is $1$ or $2$*.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.