# Is this negation correct?

The statement is: $\forall n \in \mathbb Z^+ \exists a \in \mathbb Z^+$ so that a|n and n/a is even
The statement is false because there is a counterexample n= 1, a=1 correct?
So its negation would be:
$\exists n\in \mathbb Z^+$~($\exists a \in \mathbb Z^+$so that a|n and n/a is even)
which is: $\exists n\in\mathbb Z^+$ such that $\forall a\in \mathbb Z^+ a \not|n \lor n/a$ is odd.
Is this correct? Now how can I prove the negation is true?

-
The counterexample you have in mind should be $n=1$, no mention of $a$. The $a$'s come in when you are doing the (easy!) proof that $n=1$ is a counterexample. – André Nicolas Jan 31 '13 at 1:37
I actually answered this in my answer to your previous question. – Asaf Karagila Jan 31 '13 at 1:44

Your negated statement is indeed true.

But to disprove a statement, it is enough to show prove by counterexample: the nice one happens to be when $n = 1$: there is no positive integer $a$ such that $a | n$, except for $a = 1$ in which case $1/a = 1/1 = 1\;$ which is odd.

You have to show the non-existence of any $a$ such that ($a \mid n$ and $n/a$ is even). This must fail for all positive integers $a$, not just $1$. It fails for $a=1$, and it fails for all positive integers greater than 1, since no integer $a>1$ divides $1$.

-
This proves the original statement is false, but I am actually asked to prove the negation is true which is what i am confused about. How is it possible to prove that for some positive integer n, all positive integers a either don't divide into n or n/a is odd. – user60334 Jan 31 '13 at 1:52
You have already proved the negation is true by proving the original statement is false. If p is the original claim, then the negation of p, which you wrote correctly, is $\lnot p$. Since you proved that p is false, it follows that $\lnot p$ must be true. That is also the case with your earlier problem. – amWhy Jan 31 '13 at 1:55
Another correction needed +1 :-) – Amzoti May 3 '13 at 2:29
Thanks, Amzoti...logic questions sometimes get low visibility, especially when "check my work"...Just seems to be the norm... – amWhy May 3 '13 at 2:32

This is the correct negation. To show that the negation is true you simply have to provide an example which shows the existence. You did this already $n = 1$. (There are many others though, infinitely many actually since all primes but $2$ are counterexamples)

Note: The counter example doesn't involve taking $a = 1$, you can't pick a specific $a$. What you need to say is the only $a$ which divides $1$ is $1$ and $\frac{1}{1} = 1$ is odd.

-