# Sum of THREE squares

• Mar 17th 2010, 10:46 PM
kingwinner
Sum of THREE squares
a) Prove that if $\displaystyle 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 $\displaystyle 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 $\displaystyle n = x^2 + y^2 + z^2$ (aim for a contradiction). Assuming the result of part a, since 4|$\displaystyle 4^m(8k+7)$, x,y, and z must be even, so x/2, y/2, z/2 are integers.
=> $\displaystyle 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]
• Mar 17th 2010, 11:53 PM
aman_cc
Quote:

Originally Posted by kingwinner
a) Prove that if $\displaystyle 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 $\displaystyle 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 $\displaystyle n = x^2 + y^2 + z^2$ (aim for a contradiction). Assuming the result of part a, since 4|$\displaystyle 4^m(8k+7)$, x,y, and z must be even, so x/2, y/2, z/2 are integers.
=> $\displaystyle 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?
• Mar 18th 2010, 08:44 AM
chiph588@
Quote:

Originally Posted by kingwinner
a) Prove that if $\displaystyle 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 $\displaystyle 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 $\displaystyle n = x^2 + y^2 + z^2$ (aim for a contradiction). Assuming the result of part a, since 4|$\displaystyle 4^m(8k+7)$, x,y, and z must be even, so x/2, y/2, z/2 are integers.
=> $\displaystyle 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 $\displaystyle a,b,c\in \{0,1,4\}$. This is impossible, so we're done.
• Mar 18th 2010, 10:44 AM
kingwinner
Quote:

Originally Posted by aman_cc
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!
• Mar 18th 2010, 10:59 AM
kingwinner
Quote:

Originally Posted by chiph588@
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 $\displaystyle 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!
• Mar 18th 2010, 11:16 AM
chiph588@
Quote:

Originally Posted by kingwinner
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!
• Mar 19th 2010, 01:12 AM
aman_cc
Quote:

Originally Posted by kingwinner
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.
• Mar 19th 2010, 09:40 PM
kingwinner
Quote:

Originally Posted by chiph588@
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!
• Mar 19th 2010, 09:54 PM
kingwinner
Quote:

Originally Posted by aman_cc
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.

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!
• Mar 19th 2010, 11:07 PM
CaptainBlack
Quote:

Originally Posted by kingwinner
a) Prove that if $\displaystyle n = x^2 + y^2 + z^2$ and 4|n, then x, y, and z are even.

Supose $\displaystyle n=x^2+y^2+z^2$ where $\displaystyle n,x,y,z \in \mathbb{N}$ and that $\displaystyle 4|n.$

Then $\displaystyle n$ is even which implies either $\displaystyle 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 $\displaystyle x$) and the others odd. As $\displaystyle 4|n$ and $\displaystyle 4|x^2$ we must have $\displaystyle 4|y^2+z^2$.

Now as $\displaystyle y$ and $\displaystyle z$ are odd we may write:

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

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

CB