Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Hint: you can consider $d|2ab$. – Babak Miraftab Jun 3 '12 at 5:18
up vote 9 down vote accepted

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.

share|cite|improve this answer

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

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

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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