Results 1 to 10 of 10

Math Help - Sum of THREE squares

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    Lightbulb Sum of THREE squares

    a) Prove that if n = x^2 + y^2 + z^2 and 4|n, then x, y, and z are even.
    b) Prove that if n is of the form 4^m(8k+7), then n is NOT the sum of three squares.
    ===================================

    How can we prove part a?

    For part b, this is what I've got so far.
    Suppose n is a sum of three squares n = x^2 + y^2 + z^2 (aim for a contradiction). Assuming the result of part a, since 4| 4^m(8k+7), x,y, and z must be even, so x/2, y/2, z/2 are integers.
    => n/4 = (x/2)^2 + (y/2)^2 + (z/2)^2, so n/4 is also a sum of three squares
    How to finish the proof from here?

    Any help is appreciated!

    [note: also under discussion in math links forum]
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by kingwinner View Post
    a) Prove that if n = x^2 + y^2 + z^2 and 4|n, then x, y, and z are even.
    b) Prove that if n is of the form 4^m(8k+7), then n is NOT the sum of three squares.
    ===================================

    How can we prove part a?

    For part b, this is what I've got so far.
    Suppose n is a sum of three squares n = x^2 + y^2 + z^2 (aim for a contradiction). Assuming the result of part a, since 4| 4^m(8k+7), x,y, and z must be even, so x/2, y/2, z/2 are integers.
    => n/4 = (x/2)^2 + (y/2)^2 + (z/2)^2, so n/4 is also a sum of three squares
    How to finish the proof from here?

    Any help is appreciated!

    [note: also under discussion in math links forum]

    Hint - Note all x,y,z cant be odd. So without loss of generality I can assume x is even. Then y^2 + z^2 is divisible by 4. Can you continue this argument?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by kingwinner View Post
    a) Prove that if n = x^2 + y^2 + z^2 and 4|n, then x, y, and z are even.
    b) Prove that if n is of the form 4^m(8k+7), then n is NOT the sum of three squares.
    ===================================

    How can we prove part a?

    For part b, this is what I've got so far.
    Suppose n is a sum of three squares n = x^2 + y^2 + z^2 (aim for a contradiction). Assuming the result of part a, since 4| 4^m(8k+7), x,y, and z must be even, so x/2, y/2, z/2 are integers.
    => n/4 = (x/2)^2 + (y/2)^2 + (z/2)^2, so n/4 is also a sum of three squares
    How to finish the proof from here?

    Any help is appreciated!

    [note: also under discussion in math links forum]
    part b.

    You can use your n/4 argument to recurse down to the case n=8k+7.

    So if 8k+7=x^2+y^2+z^2, we can reduce modulo 8.

    So 7=a+b+c, where  a,b,c\in \{0,1,4\} . This is impossible, so we're done.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by aman_cc View Post
    Hint - Note all x,y,z cant be odd. So without loss of generality I can assume x is even. Then y^2 + z^2 is divisible by 4. Can you continue this argument?
    So I think you're suggesting a proof by contradiction.
    Suppose x,y,z are not all even.
    To continue, 4|(y^2 + z^2) => y^2 + z^2 is even, so it must be that both of y,z are odd OR both are even. But we assumed that not all x,y,z are even, so it must be thiat y,z are odd.
    So x is even, y odd, z odd, is this the ONLY case possible?
    x=0(mod 2)
    y=1(mod 2)
    z=1(mod 2)
    How to continue from here?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by chiph588@ View Post
    part b.

    You can use your n/4 argument to recurse down to the case n=8k+7.

    So if 8k+7=x^2+y^2+z^2, we can reduce modulo 8.

    So 7=a+b+c, where  a,b,c\in \{0,1,4\} . This is impossible, so we're done.
    1) About the recursing, to be really formal, we would need something like induction, right? But in this case, it looks like we are working backwards; the m's are getting smaller rather than bigger and also there is only a finite (rather than infinite) number of steps. How can we set up the induction in this case?


    2) At the end, we get that 8k+7=7(mod8), and on the other hand, since 8k+7 is a sum of three squares, we get that 8k+7=/=7(mod8). This is where the contradiction comes, am I right?

    Thank you!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by kingwinner View Post
    1) About the recursing, to be really formal, we would need something like induction, right? But in this case, it looks like we are working backwards; the m's are getting smaller rather than bigger and also there is only a finite (rather than infinite) number of steps. How can we set up the induction in this case?


    2) At the end, we get that 8k+7=7(mod8), and on the other hand, since 8k+7 is a sum of three squares, we get that 8k+7=/=7(mod8). This is where the contradiction comes, am I right?

    Thank you!
    1.) Since we're only recursing a finite number of times, I'd say induction isn't necessary.

    2.) correct!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by kingwinner View Post
    So I think you're suggesting a proof by contradiction.
    Suppose x,y,z are not all even.
    To continue, 4|(y^2 + z^2) => y^2 + z^2 is even, so it must be that both of y,z are odd OR both are even. But we assumed that not all x,y,z are even, so it must be thiat y,z are odd.
    So x is even, y odd, z odd, is this the ONLY case possible?
    x=0(mod 2)
    y=1(mod 2)
    z=1(mod 2)
    How to continue from here?

    Thanks!
    You are confusing yourself.
    4|(y^2 + z^2). Take cases now
    Both y,z are even - we are done. Nothing more to be proved.
    One of y,z is odd - sum is odd => above won't be true.
    Both y,z are odd - sum is even but convince yourself that it won't be divisible by 4. Hence this possibility is also ruled out.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by chiph588@ View Post
    1.) Since we're only recursing a finite number of times, I'd say induction isn't necessary.

    2.) correct!
    1) But to be really really rigorous, I think we have to formally justify EVERY step of reduction of powers of 4. And to verify every step, we need something similar to induction, right? How can we set up the inductive step here? I've seen textbooks justifying things like this by "induction". (I know the fact that we can keep on reducing powers of 4 should be obvious, but I'm just wondering how to justify this really formally)

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by aman_cc View Post
    You are confusing yourself.
    4|(y^2 + z^2). Take cases now
    Both y,z are even - we are done. Nothing more to be proved.
    One of y,z is odd - sum is odd => above won't be true.
    Both y,z are odd - sum is even but convince yourself that it won't be divisible by 4. Hence this possibility is also ruled out.
    About the last case...
    The case x even, y odd, z odd means that
    x=0(mod 2), y=1(mod 2), z=1(mod 2)

    But to look at divisibility by 4, we need to use mod 4. How to go from mod 2 to mod 4? (In general, I'm pretty confused about problems relating to a change of modulus)

    I hope someone can explain this process of changing modulus.
    Thank you!
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by kingwinner View Post
    a) Prove that if n = x^2 + y^2 + z^2 and 4|n, then x, y, and z are even.
    Supose n=x^2+y^2+z^2 where n,x,y,z \in \mathbb{N} and that 4|n.

    Then n is even which implies either x,y,z are all even or one is even and two odd.

    If all are even then all is done, so suppose one even (and without loss of generality let it be x) and the others odd. As 4|n and 4|x^2 we must have 4|y^2+z^2.

    Now as y and z are odd we may write:

    y^2+z^2=(2m+1)^2+(2n+1)^2=4n^2+4n+1+4m^2+4m+1

    for some n,m \in \mathbb{N}. This is not divisible by 4, a contradiction ...

    CB
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. sum of squares
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 16th 2010, 07:25 PM
  2. Magic squares of Squares
    Posted in the Math Puzzles Forum
    Replies: 5
    Last Post: September 22nd 2010, 10:58 AM
  3. Squares
    Posted in the Math Puzzles Forum
    Replies: 6
    Last Post: December 2nd 2009, 07:55 PM
  4. Replies: 4
    Last Post: November 13th 2009, 06:12 PM
  5. sum of squares
    Posted in the Algebra Forum
    Replies: 1
    Last Post: September 7th 2007, 08:19 AM

Search Tags


/mathhelpforum @mathhelpforum