Proof

Trivially, every prime divides the integer $0.$ Also, because with every divisor $d\mid n$ it is also true that $d\mid -1$, it is sufficient to show the existence of prime divisors for natural numbers $n > 1$, instead of integers $n\neq\pm 1$.
Let $D(n):=\{d\in\mathbb N:b>1,~d\mid n\}$ be the set of all divisors of $n$.
$D(n)$ is not empty, since $n\in D(n)$.
Therefore, according to the well-ordering principle, $D(n)$ must have a smallest element, which we denote by $p$.
By construction, $p > 1$.
We will now show that $p$ is a prime number.
- For if it was composite, then it would have a non-trivial divisor $q\mid p$, i.e. a divisor with $1 < q < p$.
- Because $q\mid p$ and $p\mid n$, it would follow from the divisibility laws that $q\mid n$ and so $q\in D(n)$.
- This is a contradiction to the minimality of $p$ in $D(n)$.
- Therefore, $p$ must be prime.
  ∎

Thank you to the contributors under CC BY-SA 4.0!

Kramer Jürg, von Pippich, Anna-Maria: "Von den natürlichen Zahlen zu den Quaternionen", Springer-Spektrum, 2013