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

Solution 1:

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.

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

Solution 3:

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