## The Infinitude Of Primes

A prime number (such as 2 or 3 or 5) is a natural number (positive whole number) which is only divisible by itself and one (and no other natural number). The other natural numbers (greater than one), are called composite numbers, and are the products of prime numbers. See my article, Sieve Of Eratosthenes. Euclid's proof that there are infinitely many prime numbers is considered a particularly nice proof. This is essentially how it goes:

In order to prove that there are infinitely many primes, we will assume that there are a finite number of primes and then show that this leads to a contradiction.

Assume that there are a finite number of primes. Then there is a largest prime, p. Now, consider the number (2x3x5x7x...xp)+1, one more than the product of all primes up to p. This number is larger than p. And, this number is not divisible by any prime up to p. For example, it is not divisible by 7, as it is one more than a multiple of 7.

Now, is this larger number a prime greater than p? Maybe. Maybe not. If it is not a prime, then it is composite. But it is not divisible by any prime less than p. So if it is composite, it is divisible by some prime greater than p. So, either way, there is a prime greater than p.

That is a contradiction, as p was assumed to be the largest prime. So, there is no largest prime. In other words, there are infinitely many primes.

1 is neither prime nor composite, to avoid complicating certain ideas of number theory. For example, if 1 were prime, then all the other primes would be composite (divisible by 1).