# There exists a prime $p$ such that $p \mid n$ for all $n \in\mathbb N$, $n > 1$

My textbook asks these following true or false questions but provides two different answers even though, in my opinion, the questions are asking the exact same thing. Could someone explain how the questions are different?

True or False?

(a) For all $$n \in\mathbb N$$, $$n > 1$$, there exists a prime $$p$$ such that $$p \mid n$$.

(b) There exists a prime $$p$$ such that $$p \mid n$$ for all $$n \in\mathbb N$$, $$n > 1$$.

Part (a) can be proven using the Lemma, but part (b) is apparently false because the prime can't be $$2$$, since $$2 \nmid 3$$, and can't be odd since if $$p$$ is an odd prime, $$p \nmid 2$$.

But why is that the case for part (b) and not part (a)? And why is it trying to do $$2 \nmid 3$$, instead of $$2 \mid4$$ or $$2 \mid 6$$?

• $p|n \implies p\not |n+1$ – Fallen_Prince Nov 18 at 16:08
• @Fallen_Prince \mid rather than | looks nicer, as it gets a bit of spacing. And \nmid instead of \not\mid looks nicer as well. – Arthur Nov 18 at 16:15
• @Arthur Yup.I just forgot what it was called . Lol. – Fallen_Prince Nov 18 at 16:16
• The argument for b) is awkward. The try to figure that if b) is true what values $p$ could be. They conclude it can't be $2$ (because it must divide odd numbers) and it cant be odd (because it must divide $2$). This is fine but... weird. The statement is so obviously false, I'd just say pick two different primes; if the statement is true $p$ divides both primes, but being prime, they have no common divisors. – fleablood Nov 18 at 16:47
• Hint: the quantifers are swapped in the statements - see my answer. – Bill Dubuque Nov 18 at 17:37

Part (a) asks whether any natural number (greater than 1) has a prime divisor. Part (b) asks whether there is a single prime that divides all natural numbers (i.e. there exists some sort of "universal prime number"). The difference between these two statements is quite stark.

In the proof of part (b), they use $$2\nmid 3$$ to show that if there is such a universal prime number, then it cannot be $$2$$, as $$2$$ does not divide $$3$$. And also, the universal prime can't be odd, since no odd prime divides $$2$$. Thus there cannot be a single universal prime that divides all natural numbers.

There is no specific reason they used $$2\nmid 3$$ to prove that the prime cannot be $$2$$. They could just as well have tried $$2\nmid 5$$ or $$2\nmid 7$$, and so on. Any one of them proves that whatever this universal prime might be, it's not $$2$$. On the other hand, we actually do have $$2\mid 4$$ and $$2\mid 6$$, so these are not hinderances for this universal prime to exist and be equal to $$2$$.

The difference is that in (a) you can choose $$p$$ differently for any given $$n$$, while in (b) the same $$p$$ is supposed to work for all $$n$$.

They've $$\rm\color{#c00}{swapped}$$ quantifiers $$\forall$$ (forall) and $$\exists$$ (exists), which alters the meaning.
Namely if $$\,n>1\,$$ denotes a natural and $$\,p\,$$ a natural prime then they state

$$(a)_{\phantom{|_|}} \ \ \color{#c00}{\forall\, n}\ \exists\ p\!:\,\ p\mid n,\$$ i.e. every $$\,n>1\,$$ has a prime factor $$\,p\ \,$$ [$$p = p_n$$ may depend upon $$\,n$$]
$$(b)\ \ \ \ \exists\, p\ \ \color{#c00}{\forall n}\!:\,\ p\mid n,\$$ i.e. some fixed prime $$\,p\,$$ divides every $$n>1\ \ \$$ [$$p$$ is independent of $$\,n$$]

Remark  If you know some calculus you might find it instructive to examine the effect of permuting the quantifiers in the definition of continuity and differentiability. In the 1980 Monthly paper Differentiability and Permutations of Quantifiers by Thomas Whaley & Judson Williford, they show that all $$\,5! = 120\,$$ permutations of quantifiers in the differentiability formula - which has the form $$\, \forall a \,\exists b \,\forall c \,\exists \delta \,\forall x\ P(a,b,c,\delta,x)$$ - leads only to one of the following $$4$$ classes of functions.

$$(1)\ \$$ the class of all functions.

$$(2)\ \$$ the class of differentiable functions.

$$(3)\ \$$ the class of differentiable functions with uniformly continuous derivatives.

$$(4)\ \$$ the class of linear functions.

Below is an excerpt showing the precise formula conisdered. Note $$\$$ The number of alternations of quantifiers is often used a measure of the logical complexity of a statement - something you will appreciate if you attempt the above classification. One of the reasons that nonstandard analysis simplifies some calculus problems is that it reduces the number of such quantifier alternations.

• In your remark, I'm having trouble understanding what you mean by a "differentiability permutation". I think your starting with a particular definition of continuity and differentiability, but your remark would benefit with that definition stated. – Teepeemm Nov 19 at 1:37
• @Teepeemm See the edit. The paper is linked above. – Bill Dubuque Nov 19 at 2:36
• Really interesting thanks for sharing! – clark Nov 24 at 5:48

It may help you understand this if you see that what matters here is the order of the statements. Consider the two assertions

a) For every state there's a city that is its capitol.

b) There is a city that is the capitol of every state.

Clearly one of these is true and the other false.

You can rewrite these to turn them into your number theory question, but number theory has little to do with the logical difference between them.

They are two completely different questions.

a) says that every number $$n > 1$$ has some prime that divides it. This prime is not specific and if $$n = 52$$, say, then choices for $$p$$ ($$p$$ could be $$2$$ or $$p$$ could be $$13$$) might be different than the choices of $$p$$ for a different value of $$n$$; say $$n=25$$ (then $$p$$ must be $$5$$).

b) says that there is some specific prime that divides every number greater than one. This is a specific number $$p$$ and it is the same $$p$$ that divides every number. This $$p$$ divides $$52$$. This $$p$$ also divides $$25$$. It divides every number. It divides the 37th Mersenne prime. It divides every prime. It divides $$17$$. It divides $$19$$. And it is prime itself so $$p \ne 1$$.