Science:Math Exam Resources/Courses/MATH312/December 2009/Question 01 (b)/Solution 1

Using long division, we see that

$\displaystyle a^{2}+b^{2}=(a+b)(a-b)+2b^{2}$

and thus, the Euclidean algorithm states that

$\displaystyle \gcd(a^{2}+b^{2},a+b)=(a+b,2b^{2})$.

Now, as a and b are coprime, we see that

$\displaystyle \gcd(a^{2}+b^{2},a+b)=(a+b,2b^{2})=(a+b,2)$. If this were not true then some factor of b would divide $\displaystyle a+b$ and that means that this factor would also divide a which means that the factor must have been 1 since a and b were coprime. Finally, it's clear that $(a+b,2)$ is 1 or 2. This completes the proof.