Wednesday, December 10, 2008

Prove every natural number n > 1 has a prime factor

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.

No comments: