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

Printable View

- Sep 11th 2008, 05:47 AMprincess08GCD
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 PMLaurent
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.