Results 1 to 4 of 4

Thread: Greatest Common Divisor Problen: If gcd(a, b) = 1, solve gcd(a^2 + b^2, a + b)

  1. #1
    Junior Member
    Joined
    Jun 2010
    Posts
    59

    Greatest Common Divisor Problen: If gcd(a, b) = 1, solve gcd(a^2 + b^2, a + b)

    How do I solve the problem in the subject line? The back of the book lists an answer "1 or 2", but I'd like to see the steps used to arrive at that solution. Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Note that: $\displaystyle \text{gcd} ( a^2+b^2,a+b) = \text{gcd}((a+b)^2 - (a^2+b^2),a+b)$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    Quote Originally Posted by VinceW View Post
    How do I solve the problem in the subject line? The back of the book lists an answer "1 or 2", but I'd like to see the steps used to arrive at that solution. Thanks!
    Hint:
    d=gcd(a^2 + b^2, a + b)=gcd(a+b,a^2+b^2 +(a+b)(a-b))=gcd(a+b,2a^2), hence d|2a^2.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jun 2011
    Posts
    6

    Re: Greatest Common Divisor Problen: If gcd(a, b) = 1, solve gcd(a^2 + b^2, a + b)

    Quote Originally Posted by PaulRS View Post
    Note that: $\displaystyle \text{gcd} ( a^2+b^2,a+b) = \text{gcd}((a+b)^2 - (a^2+b^2),a+b)$
    So starting from this point we can prove it as follows:

    If $\displaystyle x|(a+b)$, then since $\displaystyle (a+b)|(a+b)^2$ we have $\displaystyle x|(a+b)^2$.

    In particular, any common divisor $\displaystyle x_1$ of $\displaystyle (a^2+b^2)$ and $\displaystyle (a+b)$ is also a divisor of $\displaystyle (a+b)^2$, hence $\displaystyle (a+b)^2 - (a^2+b^2) \equiv 0 - 0 \equiv 0$ $\displaystyle ($mod $\displaystyle x_1) $, so $\displaystyle x_1|((a+b)^2 - (a^2+b^2))$. $\displaystyle (a+b)^2 - (a^2+b^2) = 2 \cdot a \cdot b \Rightarrow x_1|(2 \cdot a \cdot b)$.

    Conversely, let $\displaystyle y_1$ be any common divisor of $\displaystyle (2 \cdot a \cdot b)$ and $\displaystyle (a + b)$. Then $\displaystyle a^2 + b^2 = (a + b)^2 - 2 \cdot a \cdot b \equiv 0^2 - 0 \equiv 0$ $\displaystyle ($mod $\displaystyle y_1)$, therefore $\displaystyle y_1$ is a common divisor of $\displaystyle (a+b)$ and $\displaystyle a^2 + b^2$ as well.

    Thus, since we showed the above two pairs have the same set of common divisors, it follows they have the same greatest commond divisor, i.e. $\displaystyle GCD(a^2+b^2,a+b) = GCD(2 \cdot a \cdot b, a+b)$.

    Let $\displaystyle y_2$ be any common divisor of $\displaystyle (a \cdot b)$ and $\displaystyle (a+b)$. Let $\displaystyle p_y$ be any odd prime factor of $\displaystyle y_2$. Then $\displaystyle p_y$, being prime, divides at least one of $\displaystyle a,b$. WLOG let us assume $\displaystyle p_y|a$. Then $\displaystyle a + b \equiv 0 + b \equiv b$ $\displaystyle ($mod $\displaystyle p_y)$. Recall that $\displaystyle p_y|(a+b)$, therefore $\displaystyle 0 \equiv a + b \equiv b$ $\displaystyle ($mod $\displaystyle p_y)$. But this means $\displaystyle p_y$ is a common nontrivial divisor of $\displaystyle a$ and $\displaystyle b$, contradicting that $\displaystyle GCD(a,b)=1$.
    Thus, our assumption that $\displaystyle p_y$ exists must have been wrong. Then this implies that $\displaystyle GCD(a \cdot b, a + b) = 1$.

    Now, let $\displaystyle p_3$ be any common PRIME divisor of $\displaystyle (2 \cdot a \cdot b)$ and $\displaystyle (a+b)$. We already showed $\displaystyle p_3$ does not divide $\displaystyle a \cdot b$, therefore $\displaystyle p_3$ divides the only remaining factor of $\displaystyle 2 \cdot a \cdot b$, which is $\displaystyle 2$. Thus, $\displaystyle p_3 = 2$ (since $\displaystyle 2$ is prime). This implies that any common divisor is a power of $\displaystyle 2$. Notice that this also implies that both $\displaystyle a$ and $\displaystyle b$ are odd (whenever the GCD we are looking for is greater than 1). Thus, $\displaystyle 4$ does not divide $\displaystyle (2 \cdot a \cdot b)$ so the only possible nontrivial common divisor is $\displaystyle 2$. (IOW, other than $\displaystyle 2$, the only possible divisor is $\displaystyle 1$).


    We show by example that the GCD of $\displaystyle 2$ is not only possible, but realized. Set $\displaystyle a=3, b=5$. Then the problem's hypthoses are satisfied and $\displaystyle a+b = 8$, $\displaystyle a^2+b^2 = 34$, which indeed have a GCD of $\displaystyle 2$.

    The other possibility admitted by our proof is the case of the trivial GCD (i.e. GCD = 1). To see that this is realized, set $\displaystyle a=2, b=3$. Then $\displaystyle a+b=5$, $\displaystyle a^2 + b^2 = 13$, which indeed have a GCD of $\displaystyle 1$.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Greatest Common Divisor of (9m+8, 6m+5)
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jan 15th 2011, 05:43 AM
  2. [SOLVED] Least common multiple - Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: Oct 25th 2010, 05:45 AM
  3. greatest common divisor
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 14th 2008, 03:24 AM
  4. Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Dec 4th 2008, 01:08 AM
  5. greatest common divisor
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Oct 16th 2006, 02:56 PM

/mathhelpforum @mathhelpforum