Results 1 to 4 of 4

Math Help - 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: \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: \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 x|(a+b), then since (a+b)|(a+b)^2 we have x|(a+b)^2.

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

    Conversely, let y_1 be any common divisor of (2 \cdot a \cdot b) and (a + b). Then a^2 + b^2 = (a + b)^2 - 2 \cdot a \cdot b \equiv 0^2 - 0 \equiv 0 (mod y_1), therefore y_1 is a common divisor of (a+b) and 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. GCD(a^2+b^2,a+b) = GCD(2 \cdot a \cdot b, a+b).

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

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


    We show by example that the GCD of 2 is not only possible, but realized. Set a=3, b=5. Then the problem's hypthoses are satisfied and a+b = 8, a^2+b^2 = 34, which indeed have a GCD of 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 a=2, b=3. Then a+b=5, a^2 + b^2 = 13, which indeed have a GCD of 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: January 15th 2011, 06:43 AM
  2. [SOLVED] Least common multiple - Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 25th 2010, 06:45 AM
  3. greatest common divisor
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 14th 2008, 04:24 AM
  4. Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 4th 2008, 02:08 AM
  5. greatest common divisor
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 16th 2006, 03:56 PM

/mathhelpforum @mathhelpforum