Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
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

7 Answers 7

up vote 13 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|improve this answer
    
@StevenStadnicki, thanks for the fix. –  Andreas Caranti Feb 18 '13 at 23:18
2  
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

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|improve this answer
    
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

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|improve this answer

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|improve this answer

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

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

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

Your Answer

 
discard

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.