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$
  • 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 '15 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 '15 at 1:55
  • 1
    $\begingroup$ If $a,b$ are both odd, then it's 2. Otherwise, it's 1. $\endgroup$ – vadim123 Feb 20 '15 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 '15 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 '15 at 2:25
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)$.

| cite | improve this answer | |
$\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)$$

| cite | improve this answer | |
$\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}$

| cite | improve this answer | |
$\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.