Results 1 to 2 of 2

Thread: GCD

  1. #1
    Newbie
    Joined
    Sep 2008
    Posts
    4

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    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
    Laurent.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum