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

Using long division, we see that

$a^2+b^2=(a+b)(a-b)+2b^2$

and thus, the Euclidean algorithm states that

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

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

$\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 $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.