Assume P is the largest prime number. Consider the integer N = 2*3*5*7*...*P + 1, which is one more than all the primes multiplied together.

Is N divisible by 2? No. The integer 2*3*5*7*...*P is divisible by 2, so if N has a remainder of 1 when divided by 2. Therefore N is not evenly divisible by 2.

Is N divisible by 3? No. The integer 2*3*5*7*...*P is divisible by 3, so if N has a remainder of 1 when divided by 3. Therefore N is not evenly divisible by 3.

Likewise, for every other prime p, N is not divisible by p. Therefore, N must be prime. Since this contradicts the assumption that there are a finite number of primes, there must be an infinite number of primes.

This proof dates back to Euclid, around 300 BC.