Q:

How to prove the statement directly: if $mn$ is odd, then both $m, n$ are odd.

Can this be proved directly? 

If $mn$ is odd, then both $m$ and $n$ are odd.

My homework is telling me to prove this directly, but I believe a  direct proof doesn't exist. Obviously this is an easy proof by contrapositive. 

A:

By Division Algorithm, if we divide $m$ and $n$ by $2$, we have $m=2p+r$ and $n=2q+s$ with $0\leq r,s <2$.  Then $r$ and $s$ are $0$ or $1$, so $rs = 0$ or $1$.  Then $mn = (2p+r)(2q+s) = 2(2pr +ps+qr) + rs$.  Since $mn$ is odd, $rs$=1.
So neither $r$ nor $s$ is $0$.  Therefore $r=s=1$ and so $m$ and $n$ are odd.

