Prove: n ≡ 3 (mod 4) Cannot be Sum of Two Squares

  • Thread starter Abelian_Math
  • Start date
In summary: It is the same, you're right. Yours might even be more understandable. I claim only that mine is shorter. :)
  • #1
Prove that if n[tex]\equiv3[/tex] (mod 4), then n cannot be represented as a sum of two squares.
 
Physics news on Phys.org
  • #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
 
  • #3
AUMathTutor said:
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

Squares are zero or one mod 4.
Thus the sum of two squares cannot be 3 mod 4.
 
  • #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.
 
  • #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.
 
  • #6
AUMathTutor said:
"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.

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.
 
  • #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.
 
  • #8
AUMathTutor said:
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.

It is the same, you're right. Yours might even be more understandable. I claim only that mine is shorter. :)
 

1. What does it mean for a number to be congruent to 3 (mod 4)?

Congruence in modular arithmetic signifies that a number is equivalent to another number when divided by a specified modulus, with the remainder being the same for both numbers. In this case, n ≡ 3 (mod 4) means that when n is divided by 4, the remainder is 3.

2. Why can't a number congruent to 3 (mod 4) be written as the sum of two squares?

This is because a number congruent to 3 (mod 4) can only have a remainder of 3 when divided by 4. When a perfect square is divided by 4, the only possible remainders are 0 or 1. Therefore, it is impossible for two perfect squares to add up to a number that is congruent to 3 (mod 4).

3. Can you provide an example to illustrate this statement?

One example is the number 7. When divided by 4, the remainder is 3. However, when trying to express 7 as the sum of two squares, it is not possible. 7 is not a perfect square, and the only possible combination of two perfect squares that add up to 7 (1 and 4) do not fit the criteria of having a remainder of 3 when divided by 4.

4. Is there a proof for this statement?

Yes, there is a proof for this statement. It is known as Fermat's theorem on sums of two squares. The proof involves using modular arithmetic and the properties of perfect squares to show that a number congruent to 3 (mod 4) cannot be expressed as the sum of two squares.

5. Are there any other values for n that cannot be written as the sum of two squares?

Yes, there are other values for n that cannot be written as the sum of two squares, such as numbers congruent to 2 (mod 4). Similarly, there is a proof for this statement known as Euler's theorem on sums of two squares. In general, numbers congruent to 0 or 1 (mod 4) can be written as the sum of two squares, while numbers congruent to 2 or 3 (mod 4) cannot.

Suggested for: Prove: n ≡ 3 (mod 4) Cannot be Sum of Two Squares

Replies
6
Views
972
Replies
1
Views
565
Replies
6
Views
968
Replies
25
Views
1K
Replies
7
Views
1K
Replies
13
Views
1K
Back
Top