Results 1 to 5 of 5

Math Help - Modulus Proof

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Modulus Proof

    Show that if n is the sum of two squares, then it CAN"T be congruent to 3 mod 4.

    Proof:

    Let n = x^2 + y^2
    Assume, aiming for a contradiction, that n is congruent to 3 mod 4.
    So, x^2 + y^2 is congruent to 3 mod 4
    This implies that 4 | x^2 + y^2 -3

    I'm trying to get a contradiction, but I'm stuck here...
    Any advice... Thanks..
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by jzellt View Post
    Show that if n is the sum of two squares, then it CAN"T be congruent to 3 mod 4.

    Proof:

    Let n = x^2 + y^2
    Assume, aiming for a contradiction, that n is congruent to 3 mod 4.
    So, x^2 + y^2 is congruent to 3 mod 4
    This implies that 4 | x^2 + y^2 -3

    I'm trying to get a contradiction, but I'm stuck here...
    Any advice... Thanks..

    Check what are the squares modulo 4 and show that the sum of any two of them cannot be 3 (mod 4)

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Feb 2008
    Posts
    535
    I still don't know how to show this. Can someone please post the proof of this. I need to know how to show this for my exam
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member Tinyboss's Avatar
    Joined
    Jul 2008
    Posts
    433
    So you know that if a=n (mod 4), that a^2=n^2 (mod 4), right? So, if you want to know what the square is, mod 4, all you need to know is what the original number is, mod 4. So do that--check all four possibilities. Then, see what you can get by adding any two squares.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2009
    From
    New York, NY
    Posts
    6
    Quote Originally Posted by jzellt View Post
    Show that if n is the sum of two squares, then it CAN"T be congruent to 3 mod 4.

    Proof:

    Let n = x^2 + y^2
    Assume, aiming for a contradiction, that n is congruent to 3 mod 4.
    So, x^2 + y^2 is congruent to 3 mod 4
    This implies that 4 | x^2 + y^2 -3

    I'm trying to get a contradiction, but I'm stuck here...
    Any advice... Thanks..
    Tinyboss gives a good answer, but here is a more specific one if you were still struggling.

    In order for n = x^2 + y^2 = 3 (mod 4) it must be that x^2 is even and y^2 is odd, or vice versa (since any number congruent to 3 mod 4 is necessarily odd). Say x^2 is even, so y^2 has to be odd. Then x must be even and y must be odd. So, x = 0 or 2 (mod 4) and y = 1 or 3 (mod 4). Then either way x^2 = 0 (mod 4) and y^2 = 1 (mod 4), so x^2 + y^2 = 1 (mod 4), contradicting the initial hypothesis.

    this is basically what Tinyboss said, just thought I'd help spell it out a bit more.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modulus
    Posted in the Algebra Forum
    Replies: 2
    Last Post: November 5th 2009, 03:46 AM
  2. Use of modulus..
    Posted in the Algebra Forum
    Replies: 3
    Last Post: June 30th 2009, 10:27 AM
  3. Proof of the modulus and Amplitude
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: April 5th 2009, 09:57 PM
  4. Inverse Modulus Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 18th 2008, 11:54 PM
  5. Formal Modulus Proof: How close am I?
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: October 14th 2008, 05:07 PM

Search Tags


/mathhelpforum @mathhelpforum