eli5 How does Euclid’s theorem prove that there are infinite prime numbers.
In: Mathematics
if there are a finite number of primes, you can put all of them in a list.
if you take this list, and multiply it together you get a huge highly composit number. If you add 1 to it, it is now an even bigger number that isnt divisible by anything in the list of primes. This is the definition of a prime number, so your finite list was incomplelete.
since this is a contradiction for any finite number of primes, there must not be a finite number of primes, i.e, there must be an infinite number of primes
It’s a proof by contradiction. You assume something, then show that the assumption leads to a contradiction, which means the assumption must be false. In that proof, you assume there’s a complete list of primes, and use that assumption to show that the list is incomplete. That’s a contradiction, so the assumption that there’s a complete list of primes must be false.
Latest Answers