1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ So, if one of $m$ or $n$ is odd (say $m$ is odd), then $m = 2k+1$ for some integer $k$. If $n$ is even (say $n = 2l$), then what is $m^2 + n^2$? what about when $n$ is odd? $\endgroup$ – tylerc0816 Dec 12 '13 at 21:48
  • 1
    $\begingroup$ That would work. Modular arithmetic can help shorten the proof: what happens when you square in $\mathbb{Z}/4\mathbb{Z}$? $\endgroup$ – Julien Dec 12 '13 at 21:50
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I tried putting the m = 2s+1 and n = 2t+1 into my equation, however I am left with 2 which is not divisible by 4.. $\endgroup$ – baller20201 Dec 12 '13 at 21:56
  • $\begingroup$ @baller20201 And thus you have proven that no matter what $s$ and $t$ are, the result cannot be divisible by $4$. Therefore you are done with your proof as soon as you have pointed this out. $\endgroup$ – Arthur Dec 12 '13 at 21:58
  • $\begingroup$ You are proving the contra+. I was doing this out and had the same problem. $\endgroup$ – Mac Dec 12 '13 at 21:59
  • $\begingroup$ @Arthur I thought we were proving $\neg P$ $\endgroup$ – baller20201 Dec 12 '13 at 22:01
  • $\begingroup$ Oh .. I think I understand now! Thanks. $\endgroup$ – baller20201 Dec 12 '13 at 22:05
6
$\begingroup$

HINT:

$1$ and $0$ are the only quadratic residues modulo 4.

|cite|improve this answer
$\endgroup$
2
$\begingroup$

$(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$??

|cite|improve this answer
$\endgroup$
2
$\begingroup$

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\}$.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

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

|cite|improve this answer
$\endgroup$
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

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 $

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.