# Prove $\gcd(a+b,a^2+b^2)$ is $1$ or $2$ if $\gcd(a,b) = 1$

Assuming that $\gcd(a,b) = 1$, prove that $\gcd(a+b,a^2+b^2) = 1$ or $2$.

I tried this problem and ended up with
$$d\mid 2a^2,\quad d\mid 2b^2$$ where $d = \gcd(a+b,a^2+b^2)$, but then I am stuck; by these two conclusions how can I conclude $d=1$ or $2$? And also is there any other way of proving this result?

-
Hint: you can consider $d|2ab$. – Babak Miraftab Jun 3 '12 at 5:18

From what you have found, you can conclude easily.

If $d$ divides two numbers, it also divides their gcd, so

$$d| \gcd (2a^2,2b^2) = 2 \gcd (a,b) ^2 =2.$$

So, $d$ is a divisor of 2 and thus either 1 or 2.

-

Suppose that the $\operatorname{gcd}\:(a+b,a^{2}+b^{2})= d$. Then we have the following:

• $d\mid (a+b)$ and $d \mid (a^{2}+b^{2})$

• Now $a^{2}+b^{2} = (a+b)^{2} - 2ab \Rightarrow d \mid 2\cdot a \cdot b$.

• Now since $d\mid (2 \cdot a \cdot b)$ either $d =1,2$ or $d\mid a$ or $d \mid b$.

• Now if $d\mid a \Rightarrow$ $d \mid b$ since $d \mid (a+b)$. So $d\nmid a$ and $d \nmid b$.

-
I didn't understood the last point if d|a it implies d|b that correct but then how you had concluded d doesn't divide a and b. – Saurabh Jun 3 '12 at 6:30
@SaurabhHota: if $d \mid a$ along with $d \mid (a+b)$ gives $d \mid b$ which contradicts $(a,b)=1$. Apply same argument of what will happen if $d \mid b$ – user9413 Jun 3 '12 at 6:57

Since $\text{gcd}(a,b) = 1$, we have that there exists $x,y \in \mathbb{Z}$ such that $$ax+by = 1$$ Hence, we have that $$(a+b)x + b(y-x) = 1$$ and $$a(x-y) + (a+b)y = 1$$ Squaring and adding the two equations, we get that $$(a+b)^2 x^2 + b^2(y-x)^2 + 2b(a+b)x(y-x) + (a+b)^2 y^2 + a^2(x-y)^2 + 2a(a+b)y(x-y) = 2$$ Rearranging the above equation, we get that $$(a+b) \left( (a+b) (x^2+y^2) + 2 (x-y) (ay-bx) \right) + (a^2 + b^2)(x-y)^2 = 2$$ Hence, we have that $$(a+b) X + (a^2 + b^2) Y =2$$ where $X = \left( (a+b) (x^2+y^2) + 2 (x-y) (ay-bx) \right)$ and $Y = (x-y)^2$. This implies that $\text{gcd}(a,b) \vert 2$.

Hence, $$\text{gcd}(a,b) = 1 \text{ or } 2$$

-

If $d$ divides $a+b$ then it divides $a(a+b)=a^2+ab$ so if it also divides $a^2+b^2$ then it divides $a^2+ab-(a^2+b^2)=ab-b^2=b(a-b)$. A similar calculation shows it divides $a(a-b)$. Then from $\gcd(a,b)=1$ we get $d$ divides $a-b$. But then it divides $(a+b)+(a-b)=2a$ and $(a+b)-(a-b)=2b$, so it's 1 or 2.

-