Introduction

A prime number is a natural number greater than one whose only positive divisors are one and itself. An integer that is greater than one and is not a prime is called a composite number. 1 and 0 are neither prime nor composite. The property of being a prime is called primality.

The sequence of the primes begins:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, ...

Notice that 2 is the only even prime. The term odd prime is used to refer to all prime numbers except 2.

    Fundamental Theorem of Arithmetic

The fundamental theorem of arithmetic states that every positive composite integer can be written as a product of primes in a unique way.

This means that the prime numbers are the "basic building blocks" of all of the natural numbers.

For example, we can say:

45 = 3 x 3 x 5192 = 2 x 2 x 2 x 2 x 2 x 2 x 3            or            1679 = 23 x 73

The importance of this theorem is just one reason why the number 1 is excluded from the set of prime numbers. If 1 were said to be prime, the precise statement of the theorem would require ‘’additional qualifications’’.

Here is a simple proof through contradiction that every positive integer greater than 1 has a prime divisor:

‘‘Assume that there exists a number greater than one that has no prime divisors. Then, as the set of positive integers greater than one with no prime divisors is not an empty set, the well-ordering property tells us that there is a least one positive integer n greater than 1 with no prime divisors. Since n has no prime divisors and n divides n, we see that n is not prime. Hence we can write n=ab with 1<a<n and 1<b<n. Having assumed n to be the lowest integer in the set, a must have a prime divisor as a<n. But any divisor of a is also a divisor of n, so n must have a prime divisor, contradicting our statement that n has no prime divisors. Therefore we can conclude that every positive integer greater than one has a prime divisor.’’