# Contrapositive: $\forall\; n > 1, n:$ composite $\implies\exists\; p$ (prime) s.t. $p \leq \sqrt n$ and $p\mid n$

Usually, I find it a cakewalk to write the contrapositive, but the following statement is quite complex for the task:

For all integers $$n > 1$$, if $$n$$ is not prime, then there exists a prime number $$p$$ such that $$p \leq \sqrt n$$ and $$n$$ is divisible by $$p$$.

Is it "There exists no prime number $$p$$ such that $$p \leq \sqrt n$$ and $$p \, | \, n$$ given that $$(n > 1)$$ for a prime integer $$n$$"? The weird thing here is that the first universal statement (for all integers $$n$$) was not converted into a conditional, which makes me uncomfortable.

I'd appreciate some guidance.

• Only a statement of the form "If A then B" has a contrapositive. The statement "For all integers..." etc. does not have a contrapositive. The statement within it, "if $n$ is not prime," etc., has a contrapositive. Commented Jul 23, 2013 at 17:27

You have the statement:

For all integers $n > 1$, if $n$ is not prime, then there exists a prime number $p$ such that $p \leq \sqrt n$ and $n$ is divisible by $p$.

This is a statement of the form $$\text{Let }\;n\in \mathbb Z, n > 1: \quad \forall n\left [\lnot P(n) \implies \exists p (Q(n, p) \land R(n, p))\right]$$

It's contrapositive is:

For all integers $n\gt 1$, if there does not exist a prime number $p$ such that $p \leq \sqrt n$ and $n$ is divisible by $p$, then $n$ is prime.

Which is a statement of the form $$\text{Let}\;n\in \mathbb Z, n > 1:\quad \forall n [\lnot \exists p(Q(n,p) \land R(n,p)) \implies P(n))$$

• Did you mean to write $p \leq \sqrt n$ instead of $p \geq \sqrt n$ in the contrapositive? Commented Jul 23, 2013 at 16:59
• Oh, yes, of course. So sorry for that typo! Commented Jul 23, 2013 at 17:00
• Phew! Scared the hell out of me for a while. :-) Commented Jul 23, 2013 at 17:00
• Sorry 'bout that, corrected. Your hunch is right on, in your post. As I wrote in a comment below another answer, you can think of the "for all integers $n > 1$..." as restricting the domain: "n is to be taken as any integer greater than one", and the rest is the conditional, over which we take the contrapositive. I understand that it can seem confusing. If we were negating the entire given statement, that would indeed modify the statement more drastically. Commented Jul 23, 2013 at 17:03
• Like in my comment above, yes. However, the statement at hand only makes sense when we take as given that $n$ is an integer greater than $1$: since it does not make sense to talk about 1 being prime, or of a non-integer being divisible, etc. A statement like "if all x are P, then some y is Q" would be" if there does not exist a y that is Q, then it is not the case that all x are P$. But that isn't really the case here. Commented Jul 23, 2013 at 18:12 The contrapositive is: Let$n > 1$be an integer. If there does not exist a prime$p$such that$p \leq \sqrt{n}$and$n$is divisible by$p$, then$n$is prime. Or in other words: let$n > 1$. If for all primes$p$, either$p > \sqrt{n}$or$n$is not divisible by$p$, then$n$is prime. We are starting out with an arbitrary integer$n > 1$. The contrapositive to "if$n$is not prime, then there exists a prime number$p$such that$p≤ \sqrt{n}$and$n$is divisible by$p$" is "if for all primes$p$, either$p > \sqrt{n}$or$n$is not divisible by$p$, then$n$is prime." The contrapositive to$A \implies B$is "if not$B$, then not$A$." But your original statement was of the form "For all$n > 1$,$A$implies$B$." So the "contrapositive" would be "For all$n > 1$, not$B$implies not$A$." Let's write it as FO formula: $$(n>1)\wedge(\mbox{ n is not prime})\Longrightarrow \exists p((p \mbox{ is prime}) \wedge (p\leq n)\wedge (p|n))$$ So the contapositive statement will be $$\sim( \exists p((p \mbox{ is prime}) \wedge (p\leq n)\wedge (p|n)))\Longrightarrow \sim ((n>1)\wedge(\mbox{ n is not prime}))$$ which is same as $$\forall p((p \mbox{ is not prime}) \vee (p> n)\vee (p\not|n))\Longrightarrow ((n\leq1)\vee(\mbox{ n is prime}))$$ • The conditional exists within the scope of the universal quantifier, so the contrapositive of the conditional must exist within the scope of the universal quantifier. The statement does NOT read: "IF (for all$n\gt 1$and blah) THEN (exists blah or blah or blah)". The universal quantifier remains unaltered. Commented Jul 23, 2013 at 16:33 • I think another way of looking at amWhy's point is that a statement of the form$\forall \cdots\$ doesn't itself have a contrapositive. Some expression within that may have one. Commented Jul 23, 2013 at 16:47
• I guess this was the stumbling block for me. I couldn't deal with the universal at the start. Commented Jul 23, 2013 at 17:02