A prime number is any number that can be divided only by itself and one. For example, 7 and 11 are prime numbers, but 12 is non-prime (because it can be divided by 2, 3, 4 and 6 in addition to itself and one).
Around 300 BCE, Euclid deduced that there must be an infinite number of primes. He used a clever construction to prove this. His argument went like this:
- If the number of primes is not infinite, then there must be a limited number of primes
- But, starting from this list of primes, I can show a way to generate another prime number
- Therefore there cannot be a limited number of primes.
Euclid’s proof works like this:
- Start with a list of all the primes that you know about so far
- Multiply them all together and add one, to produce a new number not on the list
This new number must be either prime or composite (nonprime). If it is prime, we have a new prime number, not already on our list. If our new number is not prime, it must be divisible by some prime factor. But that prime factor can’t already be on our list of primes (because those primes are all divisors of the number one less than our new number). So that prime factor must be a new prime number, not already on our list.
Either way, we have added one more prime number to our list of primes. We can apply the same process over and over again, generating a new prime number each time. Therefore the number of primes is infinite.
The statement that there are infinitely many primes is called Euclid’s theorem. Other mathematicians, including Euler, have formulated alternative proofs of the infiniteness of primes.
Need research? Quezi's researchers can answer your questions at uclue.com