Proving Modular Arithmetic for x^2 = 0 or 1 (mod 4)

[cocoabeens]

Hello, new to the forums here.

I need to prove that for all integers x, x^2 = 0(mod4) or x^2 = 1(mod4).

I started out by making a table of different cases.

case 1: y=0 ->0mod4
case 2: y=1 ->1mod4
case 3: y=2 ->0mod4
...
case odd: y=2n ->0mod4
case even: y=2n+1 ->1mod4

From here, I'm not quite sure how to say in words the rest of the proof.
In the next part, I use what's proved above to prove that x^2 + y^2 = 5003 doesn't have any integer solutions. I wasn't quite sure how to start this one.

Do I need to solve for two cases, where I assume x is odd in the first, and even in the second? I'm not sure how to use the Y^2 value at all.

I'd appreciate how to get the ball rolling on this one. Thanks so much in advance!

 

[Evgeny.Makarov]

Hi and welcome to the forum!

case 1: y=0 ->0mod4
case 2: y=1 ->1mod4
case 3: y=2 ->0mod4
...
case odd: y=2n ->0mod4
case even: y=2n+1 ->1mod4

From here, I'm not quite sure how to say in words the rest of the proof.

Each integers is either even or odd, and in both cases you proved the statement. This concludes the proof. If you've covered residue classes, then you can work within $\Bbb Z_4$. Each integer is in one of the classes 0, 1, 2 or 3 modulo 4, so it is enough to check the claim only for these four values.

In the next part, I use what's proved above to prove that x^2 + y^2 = 5003 doesn't have any integer solutions. I wasn't quite sure how to start this one.

Consider $x^2 + y^2$ modulo 4. It is the sum of $x^2$ modulo 4 and $y^2$ modulo 4. Each of these values is either 0 or 1, so $x^2 + y^2$ modulo 4 equals 0, 1 or 2, but not 3, which is 5003 modulo 4.

 

[cocoabeens]

Thanks for the response!

So for the first part, I was told that I need to deliver a formal proof, and that a table going over the cases was an insufficient proof. Would a formal proof be something like this-

"Based on the table (of cases), we have shown that for all integers x,if x is even, it will always be 0mod4, and if x is odd, it will always be 1mod4." Or is that not a sufficient enough statement?For the second part, I'm still a little confused- do I start out saying that x^2+y^2 modulo 4 =5003mod4, the left side being the sum of x^2mod4 and y^2mod4, and I can assume that y will also always be either 1mod4 or 0mod4 as well because it is also an integer? And then because x^2 and y^2 are both equal to 0 or 1, it will never be 3 = 5003mod4?

 

[Deveno]

It is $x^2$ that will be 0 mod 4 if $x$ is even. This is because any even number squared is a multiple of 4:

$(2k)^2 = 4k^2$.

On the other hand, it is easy to see that:

$(2k+1)^2 = 4k^2 + 4k + 1 = 4(k^2 + k) + 1$

which is clearly 1 mod 4, for $x$ odd. So the only possibilities are:

$x^2 + y^2 = 0 + 0 = 0$ mod 4,
$x^2 + y^2 = 0 + 1 = 1$ mod 4,
$x^2 + y^2 = 1 + 0 = 1$ mod 4,
$x^2 + y^2 = 1 + 1 = 2$ mod 4.

You could expand this to (for example, in the second case):

$x$ even, $y$ odd means that:

$x = 2k, y = 2m+1$, so that:

$x^2 + y^2 = 4k^2 + 4m^2 + 4m + 1 = 4(k^2 + m^2 + m) + 1$.

Clearly $k^2 + m^2 + m$ is an integer if $k,m$ are. So if:

$x^2 + y^2 = 5003$, in the case that $x$ is even, and $y$ is odd, we have:

$x^2 + y^2 = 4t + 1 = 5003$, for some integer $t$.

Now 5003 = 4*1250 + 3, so if:

$4t + 1 = 4(1250) + 3$ we have:

$4(t - 1250) = 2$, which implies 2 is a multiple of 4, a contradiction

(equivalently, we have that the integer $t - 1250 = \dfrac{1}{2}$).

Personally, I take issue with the notion that a "proof by cases" is not "formal enough", an idea I find absurd.

 

[Evgeny.Makarov]

"Based on the table (of cases), we have shown that for all integers x,if x is even, it will always be 0mod4, and if x is odd, it will always be 1mod4."

For this proof, you only need to consider the cases where x is even and x is odd. You don't have to consider separately x = 0, x = 1 and x = 2, which you did in post #1. Correspondingly, you don't really build a table of cases, but consider two possible options.