- #1

- 3

- 0

Prove that if n[tex]\equiv3[/tex] (mod 4), then n cannot be represented as a sum of two squares.

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter Abelian_Math
- Start date

- #1

- 3

- 0

Prove that if n[tex]\equiv3[/tex] (mod 4), then n cannot be represented as a sum of two squares.

- #2

- 494

- 0

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

CRGreathouse

Science Advisor

Homework Helper

- 2,824

- 0

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

- 494

- 0

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

- 20

- 0

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

CRGreathouse

Science Advisor

Homework Helper

- 2,824

- 0

"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

- 494

- 0

- #8

CRGreathouse

Science Advisor

Homework Helper

- 2,824

- 0

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

Share: