# How can I find the possible values that $\gcd(a+b,a^2+b^2)$ can take, if $\gcd(a,b)=1$

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.

-
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

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.

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

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

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

-

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

-
I reduced it upto d divides 2ab. I'm stuck again please help? –  BOF 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...

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

-