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) )

Proof by contradiction

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?

  • $\begingroup$ Follow the more straightforward approach I suggest in my post. $\endgroup$ – 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.

  • $\begingroup$ How do I show that they are false without using specific values for m and n? Since it is not existential... $\endgroup$ – JOX Oct 29 '13 at 19:42
  • $\begingroup$ 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. $\endgroup$ – J. W. Perry Oct 29 '13 at 19:49
  • $\begingroup$ 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? $\endgroup$ – JOX Oct 29 '13 at 21:55
  • $\begingroup$ 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. $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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