Results 1 to 7 of 7
Like Tree1Thanks
  • 1 Post By richard1234

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

  1. #1
    Junior Member
    Joined
    Mar 2011
    Posts
    72

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

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

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


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

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

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

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

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

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

    There are $\displaystyle 124999$ elements in $\displaystyle S$, hence $\displaystyle 124999-31250 = 93749$ elements can be written as sum of three integer squares.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jun 2012
    From
    AZ
    Posts
    616
    Thanks
    97

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

    Your solution seems correct. However, $\displaystyle 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.
    Thanks from math2011
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2011
    Posts
    72

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

    Thank you. You are right. $\displaystyle S$ does contain 125000 elements.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,546
    Thanks
    842

    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Jun 2012
    From
    AZ
    Posts
    616
    Thanks
    97

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

    $\displaystyle k$ cannot be zero (because every integer in $\displaystyle S$ is congruent to 4 mod 8).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,546
    Thanks
    842

    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Mar 2011
    Posts
    72

    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 $\displaystyle k = 0$. Thank you guys for pointing it out and explaining.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: May 28th 2012, 05:55 PM
  2. Replies: 8
    Last Post: Nov 27th 2011, 10:18 PM
  3. Replies: 1
    Last Post: Jul 13th 2010, 07:54 AM
  4. integer squares problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 1st 2010, 03:41 AM
  5. Replies: 2
    Last Post: Jan 9th 2010, 10:06 PM

Search Tags


/mathhelpforum @mathhelpforum