Natural numbers a and b are relatively prime. Prove that the greatest common divisor of (a+b) and (a^2+b^2) is?

When gcd(a, b) = 1, gcd(a + b, a^2 + b^2) is either 2 or 1. It is 2 if a and b are both odd, and 1 otherwise.

It helps to recall a general fact: for any x, y, and z, one has

gcd(x,y) = gcd(x, y - xz).

Putting in x = a + b, y = a^2 + b^2, and z = a - b we have y - xz = a^2 + b^2 - (a + b)(a - b) = a^2 + b^2 - (a^2 - b^2) = 2b^2 and so we learn that

gcd(a + b, a^2 + b^2) = gcd(a + b, 2b^2).

If a and b are both odd, then a + b and 2b^2 are both even, so 2 is a common divisor of a + b and 2b^2. Note that if q is an odd prime and q divides 2b^2, then q divides b^2, and hence q divides b; it cannot be that q divides a + b, because then q would also divide the difference (a + b) - b = a, so that q would be a common divisor of a and b, contradicting gcd(a,b) = 1. So no odd prime divides both a + b and 2b^2. This implies that gcd(a + b, 2b^2) is a power of 2. But 2b^2 cannot be a multiple of 4, because then b^2 would be a multiple of 2 and hence even, and then b would be even, contrary to hypothesis. So gcd(a + b, a^2 + b^2) = 2 in this case.

If at least one of a, b is even, we can (by interchanging the roles of a and b, if necessary) assume that a is even. I claim that no odd prime number divides both a + b and a^2 + b^2. To see this, fix any odd prime q. If q divides both a^2 + b^2 and a + b, then q divides (a^2 + b^2) - (a + b)(a - b) = a^2 + b^2 - (a^2 - b^2) = 2b^2, and since q is an odd prime, we deduce from this that q divides b^2, and hence that q divides b. Since q divides both a + b and b we deduce that q divides (a + b) - b = a, and hence q is a common divisor of a and b, contradicting gcd(a,b) = 1. It follows that gcd(a + b, a^2 + b^2) must be a power of 2 (allowing for the possibility of 2^0 = 1 here). But 2 cannot divide both a + b and a^2 + b^2, because if it does, then a + b is even, so, as we already know that a is even, we would deduce that (a + b) - a = b is even, implying that 2 was a common divisor of a and b, contradicting the fact that gcd(a,b) = 1. It follows that gcd(a + b, a^2 + b^2) = 1 in this case.

I'm pretty sure the GCD is also 1, but I can't prove it.