I assume you know what a prime number is.
The following proof is one of the most famous, most often quoted, and most beautiful proofs in all of mathematics. It is due to Euclid who lived around 400 B.C. and proceeds by contradiction.
An interesting book on prime numbers is Paulo Ribenboim, The New Book of Prime Number Records, 2nd ed., Springer Verlag, 1996, ISBN 0-387-94457-5. Starting on page 3, it gives several proofs that there are infinitely many primes.
There's more:
Here are a couple more interesting references on prime numbers:
Fine print, your comments, more links, Peter Alfeld, PA1UM
[16-Aug-1996]