How to show the statement is false?

Question

How to do you show the statement is false and prove its negation is true?
$$\forall n \in\mathbb Z^+ \exists a \in\mathbb Z^+ \text{ such that } a|n\text{ and }\frac na\text{ is odd}$$

Answer 1

The statement, as it reads, is true: $\forall n \in \mathbb{Z}^+, \exists a = n \in \mathbb{Z}^+$, such that $a\mid n$, and $\dfrac na = \dfrac nn = 1$ is odd.

---

IF it is also required that $a \neq n$, then one counterexample suffices to prove the statement is false: for $n = 4$, exists $a=1$ or $a = 2$ or $a = 4$ $\implies \dfrac {n}{a}$ is even. Since $3\not\mid 4,$ and no $a>4$ divides 4.

Hence, the statement, with this modification, is false. And you have thus proved that the negation of the statement is therefore true.

Answer 2

Hint: Consider the case where $n=a$.

---

Generally a statement $\forall x\varphi(x)$ is true if and only if for every $u$ in our universe, the formula $\varphi$ is true when we assign $x$ the value $u$. In this case it means that the sentence is true if and only if for every $n\in\mathbb Z^+$ the formula $\exists a(a|n\land 2\nmid\frac na)$ is true.

Similarly a statement $\exists x\varphi(x)$ is true if and only if there exists some $u$ in our universe for which $\varphi$ is true when we assign $x=u$. In the case above it means that there exists some $a\in\mathbb Z^+$ such that $a|n$ and $\frac na$ is odd.

If so the negation of $\forall x\varphi$ would be a counterexample, and the negation of $\exists x\varphi$ would be to show that there is no such example. Combining the two we have that proving something of the form $\forall x\exists y\varphi(x,y)$ is false we need to show that there is some $u$ such that for all $v$, $\varphi(u,v)$ does not hold.

In our case it would mean to show that there is some positive integer that either have no divisors, or that every way we divide the number results in an even integer.

As remarked above this is impossible because the statement is true, simply because $n|n$ and $\frac nn$ is odd. But if we allowed $n=0$ (i.e. $\forall n\in\mathbb N$ instead of $\mathbb Z^+$) it could have served as the proper counterexample. Every way we divide zero we get zero.