Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

GCD question`

  1. Nov 25, 2007 #1
    Can anyone help me with this?

    If gcd(r,s)=1 then prove that gcd(r^2-s^2, r^2+s^2)=1 or 2.

    i'm so confused.
  2. jcsd
  3. Nov 25, 2007 #2


    User Avatar
    Science Advisor
    Homework Helper

    Suppose [itex]n|(r^2-s^2)[/itex] and [itex]n|(r^2+s^2)[/itex]. (This would be the case for the gcd of the two expressions.) Then there are some integers a, b with
    [tex]an=r^2-s^2[/tex] and [tex]bn=r^2+s^2[/tex].
    Then [itex](a+b)n=2r^2[/itex] and so n divides [itex]2r^2[/itex]. Does this help?
  4. Nov 25, 2007 #3
    I understand, but how does that give us that gcd (r^2-s^2, r^2+s^2) = 1 or 2?
  5. Nov 25, 2007 #4
    nevermind, I think i see it! Thanks!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook