# How to show the statement is false?

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

-
It's true, which will be a problem. –  Chris Eagle Jan 31 '13 at 0:14
To show a statement being false you need to find an example, it called a counter-example. In this case there is none because you could take $n=a$ when $n/a=1$ an odd number. –  Maesumi Jan 31 '13 at 0:17

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.

-
So to prove it's true we would let a = n? –  user60334 Jan 31 '13 at 0:21
exactly!! you got it! For every $n$, put $a = n$ –  amWhy Jan 31 '13 at 0:26
I'd think that the simplest counterexample is $n=1$. :-) –  Asaf Karagila Jan 31 '13 at 0:26
I agree with @Asaf. –  Babak S. Jan 31 '13 at 6:53

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.

-