let $m,n$ be two positive integers. prove that if $4$ does not divide $mn$, then $2$ does not divide $m$ or $2$ does not divide $n$

Question

I understand there are two positive integers. I don't know how to prove that if $4$ does not divide $n$, then $2$ does not divide $m$ or $2$ does not divide $n$.

Answer 1

Simply, the condition, $4$ does not divide $mn$, means both $m$ and $n$ cannot be even natural numbers. That's because even $m$ and $n$ such as $m=2p$ and $n=2q$ (where $p,q\ge1$) give you $mn=4pq$, which is divisible by $4$. Thus, they are either both odd or odd-even combinations.

Case 1: Let both $m$ and $n$ be odd. Thus, none is divisible by $2$. In addition, $mn=(2s+1)(2t+1)=4st+2(s+t)+1=2(2st+s+t)+1$, is odd as well (where $s,t\ge1$), therefore not divisable by $4$ (initial condition).

Case 2: Let one be odd, and the other be even. Thus, only one of them (either $m$ or $n$) is divisible by $2$. For example, let $m$ be even and $n$ be odd such that $m=2p$ and $n=2q+1$ where $p,q\ge1$. Between them, only $m$ is divisible by $2$ (and vise versa if let $n$ be even). Also, $mn=2p(2q+1)$, is even in both instances, and divisible only by $2$ for all odd $p$ (the initial condition).

Answer 2

Hint:

by contraposition, suppose that $4$ does not divide $mn$ but $m=2k$ and $n=2h$