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

Printable View

- Sep 11th 2008, 06:47 AMprincess08GCD
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 - Sep 11th 2008, 01:34 PMLaurent
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 (Hi)

Laurent.