# Proof: $m,n$ are integers: either $4$ divides $mn$ or else $4$ does not divide $n$. [duplicate]

I'm having some trouble in proving the following statement:

If $m$ and $n$ are integers, then either $4$ divides $mn$ or else $4$ does not divide $n$.

Any help is greatly appreciated! Cheers!

## marked as duplicate by Namaste, Stahl, Stefan4024, Dan Rust, Martin ArgeramiOct 31 '13 at 1:51

• I would think about three cases. $m$ and$n$ are both even, both odd, have different parity. – Wintermute Oct 30 '13 at 23:30
• Try rewriting your statement "P or Q" as "not Q implies P" – Eric Tressler Oct 30 '13 at 23:32
• Is this true? "Either A or B" means exactly one of A and B, but not both. So, $m = n = 2$ is a counterexample. Or does "Either A or else B" mean something else than "either A or B"? – Magdiragdag Oct 30 '13 at 23:46
• @Magdiragdag I'm not sure whether "either $A$ or else $B$" connotes "not both $A$ and $B$" in English, but in mathematical logic we would ignore the "either" and the "else" and consider the "or" as "inclusive or". – Trevor Wilson Oct 31 '13 at 0:08
• Yes, that's what I do. – Magdiragdag Oct 31 '13 at 0:13

Hint: This is equivalent to proving that if $4$ divides $n$ then $4$ divides $mn$.
• @wonggr It might help to think in terms of arbitrary statements $P$ and $Q$. The implication $P \implies Q$ is equivalent (in classical logic) to the disjunction $\neg P \vee Q$. The only way the implication is false is if $P$ is true, but $Q$ is still false. – Trevor Wilson Oct 30 '13 at 23:40
Let's try a truth table: $$\begin{array}{|c|c|c|l} \hline 4\text{ divides } n & 4\text{ divides }mn & 4\text{ does not divide }n & \\ \hline T & T & \text{?} \\ f & f & \text{?} \\ f & T & \text{?} & \longleftarrow\text{ This hapens if}\ldots \\ \hline \end{array}$$ . . . The situation in the third row happens if $2$ divides both $n$ and $m$, or if $4$ divides $m$.
Fill in the last column of the truth table, then ask whether it is true in in row that either $4$ divides $mn$ or $4$ does not divide $n$.