# Question on negation of a quantified statement

There is a slight confusion I am having when comparing my answer to a solution for a problem. Basically, the question asks me to state the negation of

For every integer $n$ such that if $n$ is divisible by 3, then $n^2$ is divisible by 3.

I had always thought that the negation of this statement would be: There exists an integer $n$ such that if $n$ is not divisible by 3, then $n^2$ is divisible by 3. So that $$\neg(\forall n \in Z, p \implies q) = \exists n \in Z, \neg p \implies \neg q)$$

However, the answer states the negation as: There exists an integer $n$ such that $n$ is divisible by 3 and $n^2$ is not divisible by 3.

Is it just a typo in the answer or am I misunderstanding something here ?

Help would be appreciated ! Thank you

An implcation is false only when the premise is true and the conclusion is false. Thus if you want the negation of an implication you need to state exactly that the premise is true and the conclusion is false. In this case it becomes that $n$ is divisible by $3$ and $n^2$ is not divisible by $3$.
The problem with your answer in general is that implications are true if the premise is false. Thus any statement "There exists an integer n such that if $n$ is not divisible by 3..." will be true since if we choose $n=3$ the statement will hold.
• Oh I see, so it is not a matter of negating the $p$ and $q$ statements but rather negating the implication itself ? – PutsandCalls May 20 '16 at 5:41
• @PutsandCalls you use that $\lnot(p \Rightarrow q) \equiv (p \land \lnot q)$ – Henno Brandsma May 20 '16 at 6:41