Well-Ordering Principle
(another Prime Pages' Glossary entries)
The Prime Glossary
Glossary: Prime Pages: Top 5000:
GIMPS has discovered a new largest known prime number: 282589933-1 (24,862,048 digits)

When we seek to develop the integers axiomatically (from a short list of basic assumptions), we usually include the Well-Ordering Principle as one of these assumptions:

Well-Ordering Principle
Every nonempty set S of positive integers contains a least element; that is, there is some element a of S such that a < b for all elements b of S.

Notice that the positive real numbers do not have this property. For example, there is no smallest positive real number r, because r/2 is a smaller positive real number! The negative integers also lack this property because if r is a negative integer, then r-1 is a smaller negative integer.

This simple principle of positive integers has many consequences. Let us demonstrate one by proving the following:

Theorem: Every integer n greater than one can be written as a product of primes.
Proof: Either n is prime (in which case we are done because it is the product of the one prime n), or it has a positive divisor other than one and itself. Let p1 be the least of these divisors. Notice that p1 must be prime, otherwise there is an integer k with 1 < k < p1, and k divides p1, so k divides n, which contradicts the choice of p1! So n = p1n1 where p1 is prime and n > n1.

Now we repeat this argument with n1 to find out that it is either prime (and we are done with n = p1n1), or n1 = p2n2, where p2 is prime and n1 > n2.

Now again repeat the argument with n2, ... This process can not continue indefinitely because by the Well-Ordering Principle, the set of positive integers

n > n1 > n2 > n3 . . .
has a least element, say pk. Then n = p1p2. ... .pk.
This factorization is also unique (up to the order of the factors), see the Fundamental Theorem of Arithmetic.

Chris K. Caldwell © 1999-2019 (all rights reserved)