Well-Ordering Principle (another Prime Pages' Glossary entries) 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)