Hi, I am a little confused on this problem. Please help!!

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

So far I know a^2 + b^2= (a+b)(a-b)+2b^2

Results 1 to 2 of 2

- Sep 11th 2008, 05:47 AM #1

- Joined
- Sep 2008
- Posts
- 4

- Sep 11th 2008, 12:34 PM #2

- Joined
- Aug 2008
- From
- Paris, France
- Posts
- 1,174

Let be a (positive) common divider of and of . You wrote , so divides both the left-hand side and the first term on the right side, which implies that as well.

Suppose does not divide . Then and are relatively prime (using the fact that is prime), so that . Remembering that , we deduce . So and . However, and are relatively prime, so that and are relatively prime as well, and their only positive common divider is 1. So .

Suppose now that divides . Then, letting , we have and , so . Again, because , we get , so that .

We have shown that the only common dividers of and are either or . This implies that is either 1 or 2.

This was a nice problem, thank you

Laurent.