Proof that there is no largest prime number

Suppose there were a largest prime number. Call it N. Now consider N! + 1. Clearly, N! + 1 does not have any number between 1 and N as a divisor. This means that either a) N! + 1 is prime, or b) N! + 1 has a prime divisor greater than N. In either case, we obtain a contradiction. Thus, there is no largest prime number.
QED. See also proof, mathematics.

Once upon a time, there were two writeups above this one which gave the original proof. It's one of the oldest known proofs of anything in number theory; attributed to Euclid, it might be considerably older. Both these writeups got nuked, for no apparent reason. That's what the "other" in "other proofs" (below) refers to: two different formulations (one Euclid's original, another a modern similar proof which seems easier to many modern readers) of the classic proof. If you think it leaves this writeup's author looking rather foolish, I agree. I was unaware that whenever anybody adds a writeup to the database others have to be deleted to make room.
But I'm not going to overwrite 2 perfectly good writeups with my own.

Other proofs (almost all from the book Proofs from The Book, chapter 1):

1. Fermat numbers: Not all are prime, but see abiessu's fine writeup on them for how to use them to prove.
2. Mersenne numbers: 2^p-1, where p is prime. Again, not all are prime, but...

   We claim that if p is prime, then any factor (except 1) of 2^p-1 is larger than p. In particular, there must be infinitely many prime numbers.

   Proof of the assertion:

   It is enough to prove that any prime factor q of 2^p-1 is larger than p. So suppose q is prime and divides 2^p-1. "Recall" that the integers modulo q (usually written down as Z/qZ) are a field, and that if we omit 0 then every integer {1,...,q-1} has an inverse mod q. This is the multiplicative group mod q on {1,...,q-1}. What is the order of 2 in this group? That is, what is the least n such that 2ⁿ≡1 (mod q)?

   We know that

   2^p ≡ 1 (mod q),

   so p divides the order of 2: p|n. On the other hand, from group theory we know that the order of any element divides the size of the group, so n|(q-1). So we see that p|(q-1), and in particular p≤(q-1).

   QED.

3. The sum of the reciprocals of the primes diverges. In particular, we have infinitely many of them.
4. Furstenberg's proof that there are infinitely many prime numbers is probably one of the strangest; it uses not number theory or analysis, but topology.
5. A counting proof that there are infinitely many prime numbers is another incredibly simple one; by taking logarithms, Chaitin has a very similar proof based on information.

It's not as neat as Furstenberg's proof that ariels demonstrated, but much more intuitive. First proved by Euclid and some say the first example of a proof by reductio ad absurdum

Proof:

Assume there are finitely many prime numbers, thus you can list them. Multiply together all the numbers in this list and then add one to the total. The number you have created by this process has a remainder of one when divided by any of these numbers that you just claimed were the only primes there are.

Clearly, either this number is prime or its prime factorization contains primes that this so-called list of ALL primes missed! So we make a new list with these primes, and repeat the process, and that list will be incomplete as well. It becomes clear that it is impossible to make a list of all the primes, so the assumption that there are finitely many primes must be false.

Also, a necessary consequence of this is that there is no largest prime number. If you think a number N is the largest prime number, take the primorial of that number, N#, which is the product of all primes less than or equal to that one. N#+1 will have a remainder of one when divided by any of the primes less than or equal to N, so it must contain primes larger than N in its prime factorization.

A common misunderstanding of this proof is that N#+1 will always be prime, but in fact, only in special cases is N#+1 prime itself. Such numbers are rare numbers called primorial plus one primes.