Well Ordering Principle

Recall that an integer p is prime if p ≥ 2, and if a, b are positive integers such that p = ab then either a = 1 or b = 1.

Theorem. Every integer n ≥ 2 has a prime factor.

One way to prove this for a given integer n ≥ 2 is to apply the Wellordering Principle to the set

X = {d ∈ Z : d ≥ 2 ∧ d | n},

the set of all factors d of n such that d ≥ 2.

(a) Prove that X is not empty.

(b) Prove that if p is the minimal element of X, then p must be a prime number. (c) Finish the proof of the theorem.

Last Updated on