Asklemmy

If you want to show there are infinitely many primes, one way is to first note that every integer greater than 1 has a prime factor. This is because if an integer n is prime, n is a prime factor of itself, and if n is not prime then it must have a smaller factor m other than 1, 1< m < n. If m is also not prime, it too must have a smaller factor other than 1, and you can keep playing this game but there are only so many integers between 1 and n so eventually you'll get to a factor of n that has no smaller factors of its own other than 1, which means it is prime.

Let's now suppose there is only a finite number of primes, we'll try to show that this assumption leads to nonsense so can't be possible.

We can multiply any finite number of integers together to get a new integer. Let's multiply all of the primes together to get a new number M. Then M + 1 gives a remainder of 1 when you divide by any prime number. Since dividing by a factor will always give a remainder of 0, none of the prime numbers can be a factor of M + 1. So M + 1 is an imteger bigger than 1 with no prime factors. This is impossible, so there must be a mistake somewhere in this argument.

The only thing we said that we're not 100% sure is true was that there are a finite number of primes, so that has to be our mistake. So there must be infinitely many prime numbers.