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$?
Best Answer
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$.