Here’s an awesome, easy, super clever, and really beautiful theorem/proof combination (which I cannot take credit for (Euclid can, though)). Once you’ve learned what a prime number is and how to use proof by contradiction, you’ll be good to go (seriously, that’s it).
The beginning of the list of primes goes as follows: . You can write out a thousand more primes if you’d like, but I’m sure you get the picture. The first natural question to ask is the following: does this list go on forever? In other words, are there infinitely many primes? It is clear that an equivalent question would be to ask if there is a largest prime (clearly there is a smallest prime (which is 2), so there is a finite list of primes if and only if there is a largest prime).
Now, there is no reason that there has to be an infinite amount of primes. As numbers get bigger they become more and more divisible (i.e., there are more numbers that are smaller than them, and therefore more candidates for things that could divide them), so it might be plausible for there to be a cut-off point above which every number can be divided and is therefore not prime.
How might we go about proving a statement regarding infinity? If the enemy listed a whole bunch of consecutive non-prime numbers, it might provide evidence for the fact that there is a “largest prime”, but that is in no way a proof. For I could just take the largest number that the enemy gave me and multiply it by itself a hundred billion billion trillion times and tell him to prove that we didn’t “miss” any primes. What do we do?
Proof by contradiction
We will suppose that there is a largest prime, and arrive at a contradiction. This contradiction will force us to draw the opposite conclusion, thus proving our claim. Here we go.
Theorem: There are infinitely many prime numbers.
Proof: Suppose there aren’t. Then there is a “largest prime”. We don’t know what this prime is, but we know it’s out there (because we just supposed it exists), so let’s call it P. Then the entire list of primes looks something like . This hypothetical list hypothetically contains all the primes. If the enemy gives us this list, we can define a new number in the following way: Let . In other words, N is the number defined by multiplying all of the prime numbers together and then adding 1. This number would be huge, but it is finite (because our assumption says that there are only a finite amount of primes).
Now we can ask whether or not N is prime. Remember, it is one or the other, but not both and not neither.
Well, clearly it can’t be prime, because it’s larger than P and we supposed that P was the largest prime. Thus if N were larger than P and prime, P wouldn’t be the largest prime, which is a contradiction! So then P must be not prime. Now if N is not prime, then N must be divisible by a prime number. This is because N is divisible by something (because it’s not prime), and this something is then either prime or not prime. If this something is prime, then we’ve shown that N is divisible by a prime. If this something is not prime, then this something is in turn divisible by something else. We now just apply the same logic to this “something else”, and eventually we’ll hit a prime. Thus, since we know N is not prime, it must be divisible by a prime.
Recall though that all of the primes are in our list . If we divide N by any of these numbers, we’ll always get a remainder of 1 because N was defined to be the product of multiplying all of these numbers together, and then adding 1. Thus none of these numbers divides N evenly, so N is not divisible by a prime. Since we know that every non-prime number is divisible by a prime, N must not be non-prime (sorry for the double negative). But this means that N is both not prime, and not not prime (double negative)! This is impossible, since we already know that every number is either prime or not prime. Thus we’ve reached a complete contradiction, which means that our initial supposition was wrong. And what was our initial supposition? It was that there was some largest prime P. Thus, there can’t be such a “largest prime”, and the only way that this can be true is if the primes go on forever. Thus there are infinitely many primes!
QED (which means “you just finished the proof and you’re a boss!” in Latin).