Problem
NT-B2-M01-P008 Sum and Sum of Squares
#8
★★★☆☆ Level 3 of 5
Let \( \gcd(a,b)=1 \). Prove that \( \gcd(a+b,a^2+b^2) \) is \(1\) or \(2\). State when it equals \(2\).
Consider an odd prime divisor of the common gcd.
Let an odd prime \(p\) divide both numbers. From \(a+b\equiv0\pmod p\), we get \(b\equiv-a\). Then \(a^2+b^2\equiv2a^2\pmod p\). Since \(p\ne2\), this gives \(p\mid a\), hence \(p\mid b\), contradicting \( \gcd(a,b)=1 \). Thus only the divisor \(2\) is possible. It occurs exactly when both \(a+b\) and \(a^2+b^2\) are even, that is, when \(a,b\) are both odd. Then \(a^2+b^2\equiv2\pmod4\), so the gcd is exactly \(2\).
Explicitly discuss why no higher power of two can occur.