Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
Hint: you can consider $d|2ab$. –  Babak Miraftab Jun 3 '12 at 5:18
add comment

4 Answers

up vote 7 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|improve this answer
add comment

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|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
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.