Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

N congruent 3 mod 4

  1. Apr 15, 2009 #1
    Prove that if n[tex]\equiv3[/tex] (mod 4), then n cannot be represented as a sum of two squares.
     
  2. jcsd
  3. Apr 15, 2009 #2
    Well, assume a^2 + b^2 = 3 (mod 4).

    Then a^2 + b^2 is odd, which means exactly one of a, b is odd. We can call a odd, without loss of generality. b is therefore even.

    Clearly, b^2 = 0 (mod 4). The square of any even number is 0 mod 4.

    Therefore, a^2 must be 3 mod 4. Ergo

    a^2 = 3 (mod 4)
    <=>
    a^2 = 4n + 3

    Any odd number can be written as either 4m+1 or 4m-1. So

    (4m+1)^2 = 16m^2 + 8m + 1 = 4n + 3
    <=>
    16m^2 + 8m = 4n + 2
    <=>
    8m^2 + 4m = 2n + 1
    <=>
    4(2m^2 + m) = 2n + 1

    A clear contradiction. Checking the other case,

    (4m-1)^2 = 16m^2 - 8m + 1 = 4n + 3
    <=>
    16m^2 - 8m = 4n + 2
    <=>
    8m^2 - 4m = 2n + 1
    <=>
    4(2m^2 - m) = 2n + 1

    Also a clear contradiction. Therefore, it cannot possible be true that

    a^2 = 4n + 3

    So it follows that it is not the case that

    a^2 = 3 (mod 4)

    From which one can deduce that, since b^2 = 0 (mod 4),

    a^2 + b^2 = 3 (mod 4)

    Cannot happen.

    It may not be the prettiest proof, but I'm sure the other regulars will swoop in with a two-liner and make me look like a muppet. ;D
     
  4. Apr 15, 2009 #3

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Squares are zero or one mod 4.
    Thus the sum of two squares cannot be 3 mod 4.
     
  5. Apr 15, 2009 #4
    "Squares are zero or one mod 4."

    I think that taking this statement for granted is sort of presupposing the conclusion. Although a simple proof of this would certainly prove the guy's thing.

    I think one should be careful when proving theorems as an exercise... although there may be a theorem which makes your exercise trivial, you're not always allowed to use it per se. For instance, I could ask you to prove that there are infinitely many primes, and you could say "It has been proven that there are infinitely many primes already. Therefore, there are infinitely many primes. QED". Yes, alright. But that's sort of defeating the purpose.
     
  6. Apr 15, 2009 #5
    Can you show that n cannot be congruent to 3 (mod 4) by showing that it must be congruent to 0, 1 or 2 (mod 4)? Because you can do this by breaking it down into 3 cases. If n = x^2 + y^2 then either x and y are (1) both even, (2) both odd, or (3) one odd, one even.
    For (1) x^2 and y^2 are both congruent to 0 (mod 4) (because they are even), so x^2 + y^2 is congruent to 0 (mod 4).
    For (2) x^2 and y^2 are both congruent to 1 (mod 4) (because they are both odd), so x^2 + y^2 is congruent to 2 (mod 4).
    Finally, (3) one is odd, the other even. You find that this is congruent to 1 (mod 4).

    So then n cannot be congruent to 3 (mod 4) because by our 3 cases it must be either 0,1 or 2 (mod 4).

    Sorry in advance if I was unclear or made any other mistakes.
     
  7. Apr 15, 2009 #6

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    If you prefer the 'long' two-line version:
    0^2 = 0, 1^2 = 1, 2^2 = 0, 3^4 = 1 (mod 4). Thus squares are 0 or 1 mod 4.
    0+0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 2. Thus sums of squares are never 3 mod 4.
     
  8. Apr 15, 2009 #7
    I suppose that does work, too. Interestingly enough it is exactly what I did, except that I didn't realize that you only had to show it for 0, 1, 2, and 3. You're right, of course.
     
  9. Apr 15, 2009 #8

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    It is the same, you're right. Yours might even be more understandable. I claim only that mine is shorter. :)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: N congruent 3 mod 4
  1. Prime = 1 or 3 mod 4 (Replies: 6)

Loading...