# GCD

Printable View

• Sep 11th 2008, 05:47 AM
princess08
GCD
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, 12:34 PM
Laurent
Let \$\displaystyle d\$ be a (positive) common divider of \$\displaystyle a^2+b^2\$ and of \$\displaystyle a+b\$. You wrote \$\displaystyle a^2+b^2=(a+b)(a-b)+2b^2\$, so \$\displaystyle d\$ divides both the left-hand side and the first term on the right side, which implies that \$\displaystyle d|2b^2\$ as well.

Suppose \$\displaystyle 2\$ does not divide \$\displaystyle d\$. Then \$\displaystyle 2\$ and \$\displaystyle d\$ are relatively prime (using the fact that \$\displaystyle 2\$ is prime), so that \$\displaystyle d|b^2\$. Remembering that \$\displaystyle d|a^2+b^2\$, we deduce \$\displaystyle d|a^2\$. So \$\displaystyle d|b^2\$ and \$\displaystyle d|a^2\$. However, \$\displaystyle a\$ and \$\displaystyle b\$ are relatively prime, so that \$\displaystyle a^2\$ and \$\displaystyle b^2\$ are relatively prime as well, and their only positive common divider is 1. So \$\displaystyle d=1\$.

Suppose now that \$\displaystyle 2\$ divides \$\displaystyle d\$. Then, letting \$\displaystyle d=2 d'\$, we have \$\displaystyle d'|b^2\$ and \$\displaystyle d'|d|a^2+b^2\$, so \$\displaystyle d'|a^2\$. Again, because \$\displaystyle \gcd(a^2,b^2)=1\$, we get \$\displaystyle d'=1\$, so that \$\displaystyle d=2\$.

We have shown that the only common dividers \$\displaystyle d\$ of \$\displaystyle a^2+b^2\$ and \$\displaystyle a+b\$ are either \$\displaystyle 1\$ or \$\displaystyle 2\$. This implies that \$\displaystyle \gcd(a^2+b^2,a+b)\$ is either 1 or 2.

This was a nice problem, thank you (Hi)
Laurent.