# Proof by contradiction proving both numbers are not odd.

I have to do a proof by contradiction:

Suppose $a,b,\in\mathbb{Z}$. If $4| (a^2 + b^2)$ then a and b are not both odd.

So far I know that I need to prove that if $4|(a^2+b^2)$ then a and b are both odd.

I would use the definition of an odd number $(2k+1), k\in\mathbb{Z}$

I'm a little but unsure of where to go from here. Any help would be appreciated.

• What is $a^2 mod 4$ if $a$ is odd? – Mathmo123 Jun 26 '14 at 21:33
• Do you know modular arithmetic, e.g. the meaning of $\,a\equiv b\pmod 4\ ?\ \$ – Bill Dubuque Jun 26 '14 at 22:28

If both are odd then $a=2n+1$, $b=2m+1$ and $$a^2+b^2=4(n^2+n+m^2+m)+2$$ which is never divisible by $4$.
I'm afraid you aren't correctly stating the goal of proof by contradiction. To prove "If $P$ then $Q$" by contradiction (where $P$ and $Q$ are some statements), we must assume that $P$ is true and $Q$ is false (which is not the same as proving "If $P$ then not $Q$"), and then try to derive a nonsensical conclusion.
In your particular case, you must assume that $4\mid(a^2+b^2)$ and that $a$ and $b$ are both odd. Since $a$ and $b$ are odd integers, then there are some integers $j,k$ such that $a=2j+1$ and $b=2k+1.$ Then $a^2=4j^2+4j+1$ and $b^2=4k^2+4k+1,$ so $$a^2+b^2=4j^2+4j+4k^2+4k+2=4(j^2+j+k^2+k)+2.$$ Since $j,k$ are integers, then so are $j^2,k^2,$ and so $j^2+j+k^2+k$ is an integer--let's call it $m$--and so since $4\mid(a^2+b^2),$ then $4\mid(4m+2).$ Can you take it from there to find the contradiction, and justify all the claims I made above?
Let $a = (2k+1)$ and let $b=2k'+1$ for some k in the naturals. If you assume both are odd, and you don't get a factor of 4, then clearly 4 doesn't divide $(a^2 + b^2)$ when both $a,b$ are odd.