13
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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.\:$ $\endgroup$ – Math Gems Feb 21 '13 at 19:28
17
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ 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$$ $\endgroup$ – Math Gems Feb 21 '13 at 19:12
  • $\begingroup$ @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$. :-) $\endgroup$ – robjohn Feb 21 '13 at 20:27
  • $\begingroup$ @Rob Your Bezout skills are legends in my circles! $\endgroup$ – Math Gems Feb 21 '13 at 20:54
9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Nice answer. I like that you get a formula for the exact gcd (+1) $\endgroup$ – robjohn Feb 19 '13 at 1:11
  • $\begingroup$ Which property or theorem do you use to get rid of the factors of b? $\endgroup$ – Richard Codwater Feb 19 '13 at 2:23
  • $\begingroup$ 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)$$ $\endgroup$ – Hurkyl Feb 19 '13 at 3:16
  • 1
    $\begingroup$ @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. $\endgroup$ – Math Gems Feb 21 '13 at 19:14
  • $\begingroup$ @MathGems: neat. unfortunately, I can only upvote once :-) $\endgroup$ – robjohn Feb 21 '13 at 20:40
5
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ That's essentially the same method as in my un-Bezouted comment to Rob's answer. $\endgroup$ – Math Gems Feb 21 '13 at 19:30
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I reduced it upto d divides 2ab. I'm stuck again please help? $\endgroup$ – ngub05 Oct 24 '13 at 20:05
  • $\begingroup$ What is $d$, @BOF? $\endgroup$ – Pedro Tamaroff Oct 24 '13 at 21:49
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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