1
$\begingroup$

This question already has an answer here:

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!

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ I would think about three cases. $m$ and$n$ are both even, both odd, have different parity. $\endgroup$ – Wintermute Oct 30 '13 at 23:30
  • 1
    $\begingroup$ Try rewriting your statement "P or Q" as "not Q implies P" $\endgroup$ – Eric Tressler Oct 30 '13 at 23:32
  • $\begingroup$ 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"? $\endgroup$ – Magdiragdag Oct 30 '13 at 23:46
  • $\begingroup$ @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". $\endgroup$ – Trevor Wilson Oct 31 '13 at 0:08
  • 1
    $\begingroup$ Yes, that's what I do. $\endgroup$ – Magdiragdag Oct 31 '13 at 0:13
4
$\begingroup$

Hint: This is equivalent to proving that if $4$ divides $n$ then $4$ divides $mn$.

$\endgroup$
  • 1
    $\begingroup$ Thanks! I understand it better now! $\endgroup$ – wonggr Oct 30 '13 at 23:38
  • $\begingroup$ @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. $\endgroup$ – Trevor Wilson Oct 30 '13 at 23:40
0
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.