2
$\begingroup$

I was solving some basic number theory problems when I came across :

What is $\gcd(a^2 + b^2, a+b)$, where $a$ and $b$ are relatively prime integers that are not both $0$?

Can someone help me out ? Even a hint , upon which I can build , would suffice ...

$\endgroup$
7
  • 1
    $\begingroup$ A start: Any common divisor of $a^2+b^2$ and $a+b$ is a common divisor of $a+b$ and $(a+b)^2-(a^2+b^2)$, which is $2ab$. $\endgroup$
    – André Nicolas
    Feb 20, 2015 at 1:51
  • $\begingroup$ Hi , @AndréNicolas -- I got upto this point that a prime divisor of $(a^{2} + b^{2} , a+b)$ , will also divide $2ab$ $\Rightarrow$ it also divides $2$ $\Rightarrow$ it is $=$ $1$ or $2$ . How can I proceed after that ? $\endgroup$
    – pranav
    Feb 20, 2015 at 1:55
  • 1
    $\begingroup$ If $a,b$ are both odd, then it's 2. Otherwise, it's 1. $\endgroup$
    – vadim123
    Feb 20, 2015 at 2:00
  • 1
    $\begingroup$ You are finished, once you show (using a couple of examples) that $1$ and $2$ are both possible. But you need to show that any common divisor is $1$ or $2$, not, as you put it, that a prime divisor of the gcd is $1$ or $2$. $\endgroup$
    – André Nicolas
    Feb 20, 2015 at 2:02
  • 1
    $\begingroup$ @pranav The answer is $\,(a\!+\!b,2).\,$ More generally, when $\,d = (a,b) > 1\,$ it is $\,(a\!+\!b,2d^2),\,$ as I show in my answer. $\endgroup$
    – Bill Dubuque
    Feb 20, 2015 at 2:25

3 Answers 3

Reset to default
2
$\begingroup$

Hint Modulo $a+b$, $(a+b)^2\equiv 0$ so $a^2+b^2\equiv -2ab$. Hence you want to compute $(2ab,a+b)$.

$\endgroup$
2
$\begingroup$

Hint If $d= \gcd(a+b,a^2+b^2)$, then $d\mid(a-b)(ab)$ hence

$$d \mid (a^2+b^2) \pm (a^2-b^2)$$

$\endgroup$
1
$\begingroup$

Hint $\ \ (a\!+\!b,\ a^2\!+\!b^2)\, =\, (a\!+\!b,\,\color{#c0f}{2a^2}, \ \color{blue}{2ab}, \ \color{#c00}{2b^2})\, =\, (a\!+\!b,\,2(a,b)^2\!)\,$ [$=\, (a\!+\!b,2)\ $ if $\ (a,b)=1$]

by $\ a^2\!+\!b^2 = (\color{#0A0}{b^2\!-\!a^2})+\color{#c0f}{2a^2} = (\color{#0A0}{a\!+\!b})^2\!-\color{blue}{2ab} = (\color{#0A0}{a^2\!-\!b^2})+\color{#c00}{2b^2}\, $ and $\,\color{#0a0}{\rm greens}\equiv 0\pmod{a\!+\!b}$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .