> [!NOTE] Proposition (Every natural number is divisible by a prime number) > Suppose $n\in \mathbb{N}$ is a [[Natural Numbers|natural number]] greater than $1.$ Then $n$ is [[Divisibility in Integers|divisible]] by some [[Prime numbers|prime]]. > Proof (WO -> Prop). Take $n\in\mathbb{N}$ such that $n>1.$ Define the set $S=\{ k\in \mathbb{N} \mid (k> 1) \land (k\mid n )\}$Note that $n\in S$ so $S$ is non-empty. Applying [[Well-Ordering Principle|WO]], let $s$ be the least element of $S.$ If $s$ is prime we are done. Suppose $s$ is not prime. So $s$ is divisible by some natural $t$ strictly between $1$ and $s.$ Since divisibility is transitive, we deduce that $t\in S$ which contradicts the fact $s$ is the least element in $S.$ **Application**: [[Infinitude of primes]].