1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Prove 2/5 perfect squares must be even to have their sum equal odd

  1. Nov 9, 2009 #1
    1. The problem statement, all variables and given/known data
    given the equality a2+b2+c2+d2+e2=f2

    prove 2 out of the the 6 variables must be even.

    2. Relevant equations
    can use quadratic residues and primitive roots if it helps but don't think i need them.

    3. The attempt at a solution
    assume f is even. then f2 is even. and not all 5 numbers on the left can be odd or else we would have odd=even. so at least one even on the LHS completes this case.

    assume f is odd. then f2 is odd. so the LHS must have a odd number of odd numbers. 1,3,5 of these numbers must be odd. if it's 1,3 then we have at least 2 even and are done.

    so now i need to prove by contradiction that not all 5 can be odd. this is where i am stuck and am thinking maybe the whole method is wrong.

    a hint would be nice, thanks.
    Last edited: Nov 9, 2009
  2. jcsd
  3. Nov 9, 2009 #2
    Your method is perfectly workable. To obtain your contradiction in the last case try to consider the equality modulo 8 (HINT: If a is odd, then you know a^2 mod 8).
  4. Nov 9, 2009 #3
    ok so RHS is 1 mod 8 and LHS is 5 mod 8. easy, but how did you know to use mod 8? i have noticed that mod 8,6,4 are particularly important. but i never know which one to use. i have actually considered mod 4 here but that didn't give me any results.
  5. Nov 9, 2009 #4
    Mostly experience I guess. I knew that mod 8 have very few quadratic residues, and that 1 is the only odd one so it seemed like a natural choice. I also considered mod 4 briefly first, but saw that due to the fact that the left hand side wrapped around too early no contradiction could be obtained, but as mod 8 has very similar behavior for odd numbers I just thought of it. There are some quadratic residues that are often helpful. For instance working mod 2^n often gives good results, especially when dealing with powers of numbers whose parity you know.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook