0
$\begingroup$

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.

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

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

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
-1
$\begingroup$

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.

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