No, it follows directly from the fact that the positive integers are well-ordered, i.e., any set of positive integers has a least element. And in case one is t

No, it follows directly from the fact that the positive integers are well-ordered, i.e., any set of positive integers has a least element. And in case one is tempted to think that well-ordering and divisibility are somehow equivalent, consider Presburger arithmetic[1]. It's not even possible to define a general notion of divisibility or primality in that context, but I'm almost positive the well-ordering principle holds (it's equivalent to the axiom schema of induction). [1]: https://en.wikipedia.org/wiki/Presburger_arithmetic https://en.wikipedia.org/wiki/Presburger_arithmetic