- #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

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

- #1

- 3

- 0

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

- 498

- 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

Science Advisor

Homework Helper

- 2,844

- 0

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

- 498

- 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

Science Advisor

Homework Helper

- 2,844

- 0

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

- 498

- 0

- #8

Science Advisor

Homework Helper

- 2,844

- 0

AUMathTutor said:

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

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.

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).

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.

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.

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.

Share:

- Replies
- 13

- Views
- 1K

- Replies
- 6

- Views
- 972

- Replies
- 6

- Views
- 823

- Replies
- 1

- Views
- 565

- Replies
- 6

- Views
- 968

- Replies
- 7

- Views
- 2K

- Replies
- 25

- Views
- 1K

- Replies
- 7

- Views
- 1K

- Replies
- 13

- Views
- 1K

- Replies
- 11

- Views
- 1K