- #1
Abelian_Math
- 3
- 0
Prove that if n[tex]\equiv3[/tex] (mod 4), then n cannot be represented as a sum of two squares.
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
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.
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.
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.