Proof that there is no largest prime number (idea)

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.