Using the Well-Ordering Principle to Prove Primality and Factorization

[skeough15]

Homework Statement

Use the well-ordering principle to show that every number greater than
1 is either a prime itself, or is the product of prime numbers.

Homework Equations

The Attempt at a Solution

I am sure this question isn't all that hard, I just don't have any idea what the well-ordering principle is. I know it's something to do with a smallest such number in a set... but I don't know how that would help here. If I assume that this is a set of numbers.. then the set S must have a smallest number. I don't know how that helps me in this case though.

 

[micromass]

The well-ordering principle says that "if S is a nonempty subset of N, then S has a minimum".

How does this help in this case?
Assume that there is an element without prime factorization. Let S be the set of such elements, then S is not empty. Thus S has a minimum a. There are 2 possibilities: a is prime or a is not prime. Show that every possibility leads to a contradiction...

 

[skeough15]

Oh I see, thank you.
1) So if a is such a minimum, and a is not prime, then a must be composite. If a is composite it can be written as the factors of integers r and s such that r and s are greater than 1. If r and s are greater than 1 than r or s is less than a, but a is the smallest number in our set. Contradiction.
2) If a is prime, then the theorem is true because a is either prime or the product of prime factors.

 

[micromass]

bingo!