Let $m$ and $n$ be two integers. Prove that if $m^2 + n^2$ is divisible by $4$, then both $m$ and $n$ are even numbers.
I think I have to use the contrapositive to solve this. So I assume $\neg P\implies Q$ and I have to derive $\neg Q$? I know its easier to show odd numbers rather than even... but im still unsure how to do this practice problem.
Can only one of them be odd?
Next assume they are both odd. Write $m = 2s + 1$ and $n = 2t + 1$ for some integers $s, t$ (this can be done since we assumed $m, n$ to be odd). Try inserting this into $m^2 + n^2$, expand the resulting parentheses, and see if there are any choices for $s$ and $t$ which makes the result divisible by $4$.
If you get the answer in both these cases (only one of $m$ and $n$ odd, respectively both of them odd) that $m^2 + n^2$ cannot be divisible by $4$, then you have proven that if $m^2 + n^2$ is to be divisible by $4$, they both have to be even.
HINT:
$1$ and $0$ are the only quadratic residues modulo 4.
$(2m+1)^2+(2n+1)^2=4m^2+4m+1+4n^2+4n+1=4(m^2+n^2+n+m)+2$??
$(2m+1)^2+(2n)^2=4m^2+4m+1+4n^2=4(m^2+n^2+m)+1$??
I choose to use a and b instead of m and n because I already answered this somewhere else using a and b. Let $a=2\cdot x+1$, $b=2\cdot y+1$, where x and y are integers. This way a and b are odd numbers by definition. For example if x is 0, $a=2\cdot 0+1=1$. If x is 1, $a=2\cdot 1+1=3$. Repeating the pattern x and y can be any integer and a and b will always be an odd number by definition.
Now lets substitute a and b in $a^2+b^2$.
$a^2+b^2=\left(2\cdot x+1\right)^2+\left(2\cdot \:y+1\right)^2$
Expand the right side
$a^2+b^2=4x^2+4\cdot \:x+1+4\cdot \:y^2+4\cdot \:y+1$
Factor out a four
$a^2+b^2=4\left(x^2+x+y^2+y\right)+2$
Now Lets Say we have a number $n=4\cdot k+2$ where k is any integer. If $k=0, n=4\cdot 0+2=2$.If $k=1, n=4\cdot 1+2=6$. If $k=2, n=4\cdot 2+2=10$. And so on. The point is the values of n are even number not divisible by four. You can test that out...$n=\left\{...-18-14,-10,-6,-2,2,6,10,14,18...\right\}$
So let say $x^2+x+y^2+y=k$ and since x and y are integers k must be an integer as well. Due to closure of integers under multiplication and addition.
So going back to $a^2+b^2=4\left(x^2+x+y^2+y\right)+2$ can also be written as $a^2+b^2=4\left(k\right)+2$. And we know that is the set of even numbers not divisible by four as we showed above.
So $a^2+b^2\in \left\{...-18-14,-10,-6,-2,2,6,10,14,18...\right\}$.
Suppose $m^2+n^2\equiv 0 \mod 4$. The squares $\mod 4$ are $0,1$. Then checking all posibilities, we get that $m^2\equiv 0 \mod 4$ and $n^2\equiv 0 \mod 4$. Now, this implies that $n^2$ and $m^2$ are both even. Since odd times odd is odd ......
Remember that any odd number can be written in the form $2k+1$ with $k$ integer.
Now remember that the square of an odd number is odd, and the square of an even number is even, and the sum of two numbers one of which is even and the other is odd is always odd (and therefore cannot be divisible by $4$).
The only two possible alternatives are thus "both even" and "both odd". You can then prove your result by reductio ad absurdum (that is just as you said "taking the contrapositive") assuming that both $m$ and $n$ are odd.
Then by substituting $m=2k+1$, $n=2h+1$, your expression becomes
$m^2 + n^2 = 4k^2 + 4h^2 + 4k + 4h + 2 = 4(k^2 + h^2 + k + h) + 2$
And this is not divisible by $4$ since it is a multiple of $4$ plus $2$, which is a number not divisible by $4$.
Having a contradiction, we are then left with the only case "both even", which indeed satisfies always the request.
Proceeding contrapositively, I assume at least one of m, n is odd.
WOLOG, let the odd one of the two be m. n may or may not be odd.
$\therefore m \equiv_{4} \pm 1 $
Hence $ m^2 \equiv_{4} 1 $.
$ m^2 + n^2 \equiv_{4} 0 \iff n^2 + 1 \equiv_{4} 0 \iff n^2 \equiv_{4} 3$
But there is nothing which squares to 3 in mod 4: $ 0^2 \equiv_{4} 0; \space 1^2 \equiv_{4} 1; \space 2^2 \equiv_{4} 0; \space 3^2 \equiv_{4} 1 $
Hence $ m^2 + n^2 \not \equiv_{4} 0 $
