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

Question

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

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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