Results 1 to 4 of 4

Math Help - Sum of squares

  1. #1
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163

    Sum of squares

    Can someone give me a hint for how to show if  p \equiv 1 \mod{4} then  p = a^2+b^2 ?

    Thanks a lot!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by chiph588@ View Post
    Can someone give me a hint for how to show if  p \equiv 1 \mod{4} then  p = a^2+b^2 ?

    Thanks a lot!
    Consider, \mathbb{Z}[i]. This is a principal ideal domain. Now the equation x^2 \equiv -1(\bmod p) is solvable if p\equiv 1(\bmod 4). Therefore, p|(x^2+1) for some x\in \mathbb{Z}. If p was irreducible then p would also be prime (since the integral domain is a PID and so "irreducible" is equivalent to "prime") and so p|(x+i)(x-i)\implies p|(x+i) \text{ or }p|(x-i). But this is impossible. Therefore, p is reducible and p=\alpha \beta where \alpha,\beta \in \mathbb{Z}[i] and \alpha,\beta are non-units. This means p^2 = Np = (N\alpha)(N\beta) (norm). However, N\alpha, N\beta \not = 1 since they are not units and so N\alpha = N\beta = p. Therefore, if \alpha = a+bi then it means N\alpha = p \implies a^2 + b^2 = p.

    Additional problem: Prove that if p=a^2+b^2 and p=c^2+d^2 where a,c are odd and b,d are even and a,b,c,d>0 then a=c\text{ and }b=d. In other words, we have a certain level of uniqueness in the decomposition of p into sum of squares.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Ah yes, I was having trouble seeing why p is reducible.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Here is a very elementary way of proving this result. Remember if p\equiv 1(\bmod 4) then there is a so that a^2 \equiv -1(\bmod p). There is an elementary way of showing this too, just let a = \left( \tfrac{p-1}{2} \right)! and use Wilson's theorem. But whatever, we will accept this result.

    We need a Lemma first: let (b,p)=1 then there exists x,y with 0 < |x|,|y| < \sqrt{p} so that bx\equiv y(\bmod p).

    To prove this let n = [\sqrt{p}]+1. And define S = \{bx - y | 0\leq x,y \leq n-1\}. The set S has at most n^2 different values. Since n^2 > p and there are only two p residue classes of mod p it means there are bx_1 - y_1\text{ and }bx_2 - y_2 so that bx_1 - y_1 \equiv bx_2 - y_2(\bmod p) and x_1\not = x_2 or y_1\not = y_2 (by pigeonhole principle). If x_1 = x_2 then by considering this congruence it would mean y_1 = y_2, which is a contradiction. Similarly if y_1 = y_2 then it would force x_1=x_2, which is a contradiction. Therefore, x_1\not =x_2 , ~ y_1\not = y_2. Thus, we have b(x_1 - x_2) \equiv (y_1 - y_2)(\bmod p). Set x=x_1-x_2, ~ y=y_1-y_2 and we see that 0 < |x|,|y| \leq n-1 < \sqrt{p}. Remember that x^2,y^2 < p \implies x^2+y^2 < 2p, thus k must be equal to 1.

    Now we can prove that p is a sum of two squares. Let a be a square root of -1 mod p i.e. in less fancy language a^2\equiv -1(\bmod p). Pick integers x,y so that ax\equiv y(\bmod p) and 0 < |x|,|y| < \sqrt{p}. Therefore, -x^2 \equiv a^2x^2 = (ax)^2 \equiv y^2(\bmod p). Thus, p|(x^2+y^2) \implies x^2+y^2 = pk for some k\in \mathbb{Z}^+. We will complete the proof if we can show k=1.
    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