Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 2 down vote accepted

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

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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