Euclid's proof that there are infinitely many primes
Suppose that there is a largest prime. Then we can list them, like this: p1, p2, p3, ..., pN. Consider the numberQ = p1, p2, p3, ..., pN + 1.
If Q is prime, then we have found a prime larger than the largest prime pN. If Q is not prime, then it has a prime divisor p. This divisor must be one of the pi. But then it leaves a remainder of 1 when divided into Q. Again we arrive at a contradiction. Thus the assumption that there is a largest prime is false. That is, there are infinitely many primes.
The statement that there are infinitely many primes is Proposition 20 of Book IX of Euclid's Elements. See Sir Thomas Heath, p. 412 of Euclid, the thirteen books of the Elements, volume II, Dover Publications, 1956.