# Math Help - How many elements of S can be written as the sum of three integer squares?

1. ## How many elements of S can be written as the sum of three integer squares?

Let $S$ be the set of all positive integers $n$ not exceeding $1 000 000$ such that $n \equiv 4 \pmod{8}$, that is, $S = \{4,12,20,28,\ldots,999996\}$.

How many of the elements of $S$ can be written as the sum of the three integer squares?

A theorem says that $n$ can be written as sum of three integer squares iff $n \ne 4^k (8m + 7)$ for non-negative integers $k,m$.

So $n = 8x - 4$ can be written as sum of three integer squares iff $n = 8x - 4 \ne 4^k (8m + 7)$, or in another word when $8x - 4 = 4^k (8m + 7)$ with variable $x$ has no integer solution.

$x = 4^km + \frac{4^k \timex 7}{8} - \frac{1}{2}$ is not an integer when $k > 1$, and is an integer when $k = 0,1$.

Work out how many $n$ CANNOT be written as sum of three integer squares.

When $k = 0$, $n = 8m + 7 \equiv 7 \pmod{8}$ are not in $S$.
When $k = 1$, $n = 4(8m + 7) = 32m + 28 \equiv 4 \pmod{8}$ are in $S$.

We require $n = 4(8m + 7) \leq 1000000$ or $m \leq 31249$, hence there are $31250$ elements in $S$ that cannot be written as sum of three integer squares.

There are $124999$ elements in $S$, hence $124999-31250 = 93749$ elements can be written as sum of three integer squares.

2. ## Re: How many elements of S can be written as the sum of three integer squares?

Your solution seems correct. However, $S$ contains 125,000 elements, not 124,999 (you have to add 1 b/c you have an inclusive set). So the answer should be 93,750.

3. ## Re: How many elements of S can be written as the sum of three integer squares?

Thank you. You are right. $S$ does contain 125000 elements.

4. ## Re: How many elements of S can be written as the sum of three integer squares?

it appears that i agree with your answer, although i do not know how you can conclude that x is an integer when k = 0. for then:

x = m + 7/8 - 1/2 = m + 3/8, which is *not* an integer.

5. ## Re: How many elements of S can be written as the sum of three integer squares?

$k$ cannot be zero (because every integer in $S$ is congruent to 4 mod 8).

6. ## Re: How many elements of S can be written as the sum of three integer squares?

i am saying that when k = 0, x is not even an integer.

look, when k = 0, 8x - 4 = 8m + 7

8(x - m) = 11 ---> x - m is not an integer ---> x is not an integer.

7. ## Re: How many elements of S can be written as the sum of three integer squares?

You guys are right. I have got the details wrong about $k = 0$. Thank you guys for pointing it out and explaining.