What approach should I take to establish this logical proof?

I need to design a logical math proof:

Write a detailed structured proof to prove that if m and n are integers, then either 4 divides mn or else 4 does not divide n.

Hint: Think about the form of the statement.

I was thinking about first proving that either 4 should divide m or n in order for the first part to be true, then use proof by cases to prove what happened when m was 4, and another case when n was 4...

But I got stuck, what do you recommend:

This is what I got so far: Claim: (m ∈ Z ∧ n ∈ Z) => (4 | mn ˅ 4 ∤ n)

Negated claim: (m ∈ z ∧ n ∈ z) ∧ ( P(n) ∧ ¬P(mn) )

Assume m , n ∈ z:
Assume P(n) ∧ ¬P(mn):
Then ∃ q ∈ R, n = 4q
Let q0 be such that n = 4q0
Then mn = m(4q0)
Then mn = 4(mq0)
Then ∃ q ∈ R, mn = 4q
Then 4 | mn
Then P(n) ∧ P(mn)
Then (m , n ∈ z) ∧ P(n) ∧ P(mn))

I know that is wrong, how can I fix it?

• Follow the more straightforward approach I suggest in my post. – Namaste Oct 30 '13 at 12:24

Claim: $$m,n \in \mathbb{Z} \Rightarrow (4 \mid mn \vee 4 \nmid n).$$

Proof (by contradiction): Suppose the claim is false, that is, \begin{align*} \neg(m,n \in \mathbb{Z} \Rightarrow (4 \mid mn \vee 4 \nmid n)) &\equiv (m,n \in \mathbb{Z})\wedge\neg(4 \mid mn \vee 4 \nmid n) \\ &\equiv (m,n \in \mathbb{Z})\wedge(4 \nmid mn \wedge 4 \mid n). \end{align*} All that is left to show is that any part of the negation is false, ie. $(4 \nmid mn \wedge 4 \mid n)$ is impossible. Conclude that since the negation of the claim is false, the claim itself must be true.

• How do I show that they are false without using specific values for m and n? Since it is not existential... – JOX Oct 29 '13 at 19:42
• Consider $m,n \in \mathbb{Z}$, and the statement ($4\nmid mn \wedge 4 \mid n$). The statement $4 \mid n$ means $n$ is an integer multiple of $4$, that is, $n=4k$ for some $k \in \mathbb{Z}$. Rewrite $mn=m \cdot 4k$. See that when this is divided by $4$, the result is an integer, thus $4 \mid mn$, and the negation is false. – J. W. Perry Oct 29 '13 at 19:49
• Yeah, I demsotrated it using that, but I am having a problem trying to justify this on my notebooK. Doing it step by step, I start assuming that (m,n∈Z), then I dont know if I have to assume 4∣n, and then prove 4 | mn, or if I have to assume (4∤mn∧4∣n) all at once and then prove 4 | mn? – JOX Oct 29 '13 at 21:55
• To show that $((m,n \in \mathbb{Z}) \wedge (4 \mid n) \wedge (4 \nmid mn))$ is false, we need only show that one of the 3 atomic terms is false. Show that $((m,n \in \mathbb{Z}) \wedge (4 \mid n))\Rightarrow (4 \mid mn)$, and you are done. – J. W. Perry Oct 30 '13 at 2:06

You are to write your proof using only what is given: $m, n\in \mathbb Z$. You are then to prove that from this, it follows that

$(1)\quad 4 \mid mn$ or

$(2) \quad\lnot (4\mid n)$.

Suggestion: start by considering the two cases:

• $4 \mid n$, and
• $\lnot (4 \mid n)$,

which are mutually exclusive cases, exhausting all options for $n\in \mathbb Z$. One of these two cases must necessarily be true for any given $n$: Any $n$ whatsoever must be such that $4$ divides $n$, or $4$ does not divide $n$. That's a tautology, with no need for proof.

• Case (1): Suppose $4$ divides $n \in \mathbb Z.\;$ Then $\,n = 4k\,$ where $k$ is some integer (by the definition of divisibility by $4$). Then take any $m$ whatsoever. $$mn = m(4k) = 4(mk).$$ Hence $4$ divides $mn$. Hence the proposition is true when $4$ divides $n$, and it is true for all integers $m$.

• Case (2): Suppose $4$ does not divide $n\in \mathbb Z.\;$ Then the proposition is true in this case, (it satisfies the disjunction "or else $4$ does not divide $n$. And it is true for any $m\in \mathbb Z$.

It either case (and we have exhausted possible cases), the proposition is true.

• So what approach should I take to prove that one or the other must necessarily be true? – JOX Oct 29 '13 at 18:46
• See my suggestion above. – Namaste Oct 29 '13 at 18:47
• Can you help me ? I just added what I got so far to the main post. i know it is wrong tho – JOX Oct 29 '13 at 22:14
• @amWhy: this also needs a TU +1 – Amzoti Oct 30 '13 at 1:24