Results 1 to 4 of 4

Math Help - sum of squares and congruence problem

  1. #1
    Junior Member
    Joined
    Jan 2009
    Posts
    27

    sum of squares and congruence problem

    I searched around and couldn't find anything like this, so here's my questions:

    Show that if an integer x is the sum of two squares, then x \not\equiv 3 mod 4

    proof:
     x = a^2 + b^2 for a,b integers

    Assume x \equiv 3 mod 4. (going for a contradiction here)
    a^2+b^2 \equiv 3 mod 4            -subsitution
    4 | (a^2+b^2-3) -def. of congruence
    a^2+b^2-3 = 4k for some k int - def. of divides

    So, I have to some how show that this ISN'T true. I'm not sure if I am even going about this correctly by contradiction, but it just seems like what I would need to do.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor red_dog's Avatar
    Joined
    Jun 2007
    From
    Medgidia, Romania
    Posts
    1,252
    Thanks
    5
    a=2m, \ b=2n\Rightarrow a^2+b^2=4(m^2+n^2)

    a=2m, \ b=2n+1\Rightarrow a^2+b^2=4(m^2+n^2+n)+1

    a=2m+1, \ b=2n\Rightarrow a^2+b^2=4(m^2+n^2+m)+1

    a=2m+1, \ b=2n+1\Rightarrow a^2+b^2=4(m^2+n^2+m+n)+2
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Th3sandm4n View Post
    I searched around and couldn't find anything like this, so here's my questions:

    Show that if an integer x is the sum of two squares, then x \not\equiv 3 mod 4

    proof:
     x = a^2 + b^2 for a,b integers

    Assume x \equiv 3 mod 4. (going for a contradiction here)
    a^2+b^2 \equiv 3 mod 4            -subsitution
    4 | (a^2+b^2-3) -def. of congruence
    a^2+b^2-3 = 4k for some k int - def. of divides

    So, I have to some how show that this ISN'T true. I'm not sure if I am even going about this correctly by contradiction, but it just seems like what I would need to do.

    Thanks
    Depending on whether a is even or odd we get a^2\equiv 0,1(\bmod 4).
    Thus, b^2\equiv 0,1(\bmod 4) which means x = a^2+b^2 \equiv 0,1,2(\bmod 4). Thus, x\not \equiv 3(\bmod 4).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jan 2009
    Posts
    27
    Thanks, I was just thinking about that on the bus ride back home
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Congruence Problem
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: June 29th 2011, 08:41 AM
  2. congruence problem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 14th 2009, 08:53 PM
  3. Congruence problem with gcd
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 9th 2009, 01:18 AM
  4. Congruence Problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 14th 2007, 11:25 AM
  5. Congruence problem with LCM
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: February 19th 2007, 01:55 PM

Search Tags


/mathhelpforum @mathhelpforum