1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Greatest common divisor

  1. Aug 4, 2009 #1
    1. The problem statement, all variables and given/known data
    Given gcd(a,b)=1, what is the gcd(a^2+b^2, a+b) where ^=square.


    2. Relevant equations



    3. The attempt at a solution
    gcd(a^2+b^2, a+b) = gcd ( (a+b)^2 -2ab, a+b) which i think, we can reduce to gcd(2ab, a+b). Here is where I stucked. I am not sure how to proceed. Please could anyone help me?
     
  2. jcsd
  3. Aug 4, 2009 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Welcome to PF!

    Hi mafendee! Welcome to PF! :smile:

    Hint: if p divides 2ab, then either … :wink:
     
  4. Aug 4, 2009 #3
    thank you tiny-tim,

    "if p divides 2ab, then either", p|2 and/or p|a (p not divide b)
    or p|2 and/or p|b. (p not divide a)
    p>1 cannot divide both a,b since (a,b)=1.

    so gcd(2ab, a+b)=1. is this correct?
     
  5. Aug 5, 2009 #4

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    hmm :frown:

    you're not being logical …

    why can't it be 2?
     
  6. Aug 5, 2009 #5
    you're right. I had a thinking that a and b should be even and odd which is not divisible by 2. But then it could also be the case where both of them are odds, hence a+b=even which is divisible by 2.

    so, the gcd = 2.

    is it correct to say that gcd(a^n+b^n, a+b) = n? (i haven't tried to prove this).
     
  7. Aug 5, 2009 #6

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Yes, gcd = 2 if they're both odd, and 1 if one is even …

    but can you prove that properly? :wink:
    (try using the X2 tag just above the Reply box :wink:)

    Well, if n is odd, then a+b divides an + bn anyway.

    For n = 4, for example, you would start with gcd(2ab(2a2 + 3ab + 2b2),a+b) …

    what happens next? :smile:
     
  8. Aug 5, 2009 #7
    And what if a=7 and b=2 ?

    gcd(7,2)=1

    gcd(72+22,7+2)=gcd(53,9)=1

    Where 2 came from?
     
  9. Aug 5, 2009 #8

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    ah … 2 is even! :wink:
     
  10. Aug 5, 2009 #9
    Ohh... I missed this one... Sorry...

    Regards.

    EDIT:

    Here is my proof.

    Let's say that p and k are integers.

    If a is even and b is odd then a=2p and b=2k-1 so that a2+b2= 4p2 + 4k2-4k+1 and a+b = 2p+2k-1. As we can see there isn't number which is divisible by both of the terms.

    If a and b are odd then a2+b2=(2k-1)2+(2p-1)2=4k2+4p2-4k-4p+2 and a+b=2p-2k-2, so that both terms are divisible by 2 so that gcd(a2+b2, a+b) = 2 :smile:
     
    Last edited: Aug 5, 2009
  11. Aug 6, 2009 #10
    thank you to both of you. i think Дьявол has proved the cases of +a,-b and -a,-b.

    "For n = 4, for example, you would start with gcd(2ab(2a2 + 3ab + 2b2),a+b) "

    Here is what I have:

    Let say p|2ab(2a2 + 3ab + 2b2), this could be the cases where

    case1: p|2 or p|a but not b, and p does not divide (2a2 + 3ab + 2b2)
    OR
    case2: p|2 or p|b but not a, and p does not divide (2a2 + 3ab + 2b2)

    clearly in both cases if p|(a+b), this is the cases when p|2. so p=1,2.

    If both a,b are odds. let a=2k+1, b=2p+1, then a2=4k2+4k+1, b2=4p2+4p+1, ab=4kp+2(k+p) +1.

    2(4kp+2(k+p)+1)(8k2+8p2+14(k+p)+12kp+7) which is divisible by 2, so does a+b, so gcd=2.

    If only one is odd, let a=2k+1, b=2p, then a2=4k2+4k+1, b2=4p2, ab=2p(2k+1).

    2(2p)(2k+1)(8k2+4p2+2(4k+p)+2kp+2)=8(p)(2k+1)(4k2+2p2+(4k+p)+kp+1) which is divisible by 8, but a+b=2(k+p) +1 is only divisible by 1, so gcd=1.

    Am i doing this correctly?
     
  12. Aug 6, 2009 #11

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    mafendee, this a = 2k or 2k+1 stuff is really longwinded.

    For the original case, if p is prime and p | 2ab, then p = 2 or p| a or p | b, and p can't divide both a and b, so if it divides one of them it can't divide a+b, so gcd = gcd(2,a+b) = 1 or 2.

    For the (a+b)4 case, I was expecting you to carry on from gcd(2ab(2a2 + 3ab + 2b2),a+b), and reduce the 2a2 + 3ab + 2b2 even further, until you get something like gcd(2ab,a+b) again.
     
  13. Aug 8, 2009 #12
    tiny-tim, you are right.

    from gcd(2ab(2a2 + 3ab + 2b2),a+b), we have
    = gcd(2ab(2a+2b)(a+b) -4ab + 3ab),a+b) = gcd(2ab(ab), a+b))

    if p|2a2b2 then p|2 or p|a2 (p|a) or p|b2 (p|b) but p does not divide both a and b at the same time so p does not divide a+b. So we have gcd(2, a+b) = 1 or 2.

    For odd n, say n=3 we have gcd(a3+b3, a+b) =
    gcd ((a+b)(a2+b2-ab), a+b) = a+b. So if n is odd, the gcd = a+b.

    What happen if n is even, will the gcd always be 1 or 2? How to prove this, by induction or???
     
  14. Aug 9, 2009 #13

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Yes. :smile:
    Try expanding (a + b)2n using the binomial coefficents …

    so 1 4 6 4 1 for n = 2

    1 6 15 20 15 6 1 for n = 3 etc :wink:
     
  15. Aug 10, 2009 #14
    tiny-tim,

    for even power, (a + b)2n,

    let n=1,
    1 2 1
    we have gcd(2ab, a+b)
    here gcd=1/2

    let n=2,
    1 4 6 4 1
    we have gcd(2ab(2a2+3ab+2b2), a+b)
    here gcd=1/2

    let n=3,
    1 6 15 20 15 6 1
    we have gcd(ab(6a4+15a3b+20a2b2+15ab3+6b4), a+b)
    here gcd=1

    let n=4,
    1 8 28 56 70 56 28 8 1
    after taking 1 out after reduction, we can factorise 2 out. So i assume the gcd here is 1/2.

    But then how to proof that when is the gcd=1 and when the gcd=1/2?
     
  16. Aug 11, 2009 #15

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    (just got up :zzz:)
    No, 6a4+15a3b+20a2b2+15ab3+6b4

    = 6a4+(6+9)a3b+(9+2+9)a2b2+(6+9)ab3+6b4

    = 2a2b2 + multiple of (a+b) …

    and you should be able to prove that it will always be 2an-1bn-1 :smile:

    (i expect there's a better way of proving it, but this is the most immediately obvious one :redface:)

    EDIT: ah, I see the pattern now …

    it's 6 - 15 + 20 - 15 + 6

    (and n = 2 was -4 + 6 - 4) …

    can you see what the general pattern is, and why it must always add to 2? :wink:

    (hint: consider (a - b)2n)​
     
    Last edited: Aug 11, 2009
  17. Aug 12, 2009 #16
    here we go again,

    for even power, (a + b)2n,

    let n=1, we have (a + b)2
    1 2 1
    we have gcd(2ab, a+b)
    here gcd=1/2

    let n=2,
    1 4 6 4 1
    we have gcd(2ab(2a2+3ab+2b2), a+b) = gcd (2ab((2a+2b)(a+b) -ab), a+b) = gcd (2a2b2, a+b)
    here gcd=1/2

    let n=3,
    1 6 15 20 15 6 1
    we have
    =gcd(ab(6a4+15a3b+20a2b2+15ab3+6b4), a+b)
    =gcd(ab((6a2+6b2)(a2+b2)-12a2b2+15a3b+20a2b2+15ab3), a+b)
    =gcd(ab(((6a+6b)(a+b)-12ab)((a+b)(a+b)-2ab)+15a3b+8a2b2+15ab3), a+b)
    =gcd(ab(24a2b2+15a3b+8a2b2+15ab3)), a+b)
    = gcd(a2b2(15a2+32ab+15b2), a+b)
    = gcd(a2b2((15a+15b)(a+b)-30ab+32ab), a+b)
    = gcd(a2b2(2ab), a+b)
    = gcd(2a3b3, a+b)

    here gcd=1/2

    but what i've got here is the gcd is of the form (2anbn, a+b) different from what you pointed out (2an-1bn-1, a+b). am i missing something here?

    The '2' that we managed to factor out after lengthy algebra there goes parallel to what you wrote on your 'edit' part. When we "sum" up the term, it will end up with 2. (6 - 15 + 20 - 15 + 6 = 2, -4 + 6 - 4 = 2 and so on).
     
    Last edited: Aug 12, 2009
  18. Aug 13, 2009 #17
    tiny-tim,

    was my answer in previous post correct?
     
  19. Aug 14, 2009 #18

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi mafendee! :smile:
    Sorry … I somehow missed replying to this thread. :redface:

    Yes, it's correct, but a little long-winded …

    you get more marks in the exam if you can make the proofs shorter, and so that they clearly work for any n. :wink:
    No, I just forgot what "n" was. :smile:
    Yup … and can you do a simple proof why that works for any n?
     
  20. Aug 14, 2009 #19
    tiny-tim,

    i will try to work on that simple proof you said. thank you.
     
  21. Aug 23, 2009 #20

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi mafendee! :smile:

    In case you haven't got it yet, here's a hint:

    expand (1 - 1)n :wink:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Greatest common divisor
  1. Greatest common divisor (Replies: 24)

Loading...