Prove every natural number n > 1 has a prime factor.

Prime numbers are numbers which have no divisors other than 1 (i.e. 1,3,5,7,11...)

Composite numbers have more than one divisor (i.e. 4,6,8,9...)

If n is prime (has no divisor other than 1), then n is a prime factor of n. If n is composite then n has divisors other than 1 and n. We will make p a number that is the smallest divisor of n (other than 1), and show that p is prime.

To do this we will use a proof by contradiction, so start by assuming the opposite. Assume p is composite and not prime, then p must also have a divisor d, where 1 < d < p. So now d divides p, and p divides n, but then d < p which contradicts the definition of p being the smallest divisor. Thus p must be prime if it is the smallest divisor, and so every natural number has a prime factor.

## Wednesday, December 10, 2008

### Prove every natural number n > 1 has a prime factor

Labels:
contradiction,
divisor,
factor,
natural numbers,
prime,
well ordering principle

Subscribe to:
Post Comments (Atom)

## No comments:

Post a Comment