The proof that there are infinitely many prime numbers is a Proof by contradiction.

First, we note that there is indeed a prime: namely $~$2$~$. We will also state a lemma: that every number greater than $~$1$~$ has a prime which divides it. (This is the easier half of the Fundamental Theorem of Arithmetic, and the slightly stronger statement that "every number may be written as a product of primes" is proved there.)

Now we can proceed to the meat of the proof. Suppose that there were finitely many prime numbers $~$p_1, p_2, \ldots, p_n$~$. Since we know $~$2$~$ is prime, we know $~$2$~$ appears in that list.

Then consider the number $~$P = p_1p_2\ldots p_n + 1$~$ — that is, the product of all primes plus 1. Since $~$2$~$ appeared in the list, we know $~$P \geq 2+1 = 3$~$, and in particular $~$P > 1$~$.

The number $~$P$~$ can't be divided by any of the primes in our list, because it's 1 more than a multiple of them. But there is a prime which divides $~$P$~$, because $~$P>1$~$; we stated this as a lemma. This is immediately a contradiction: $~$P$~$ cannot be divided by any prime, even though all integers greater than $~$1$~$ can be divided by a prime.

Example

There is a common misconception that $~$p_1 p_2 \dots p_n+1$~$ must be prime if $~$p_1, \dots, p_n$~$ are all primes. This isn't actually the case: if we let $~$p_1, \dots, p_6$~$ be the first six primes $~$2,3,5,7,11,13$~$, then you can check by hand that $~$p_1 \dots p_6 + 1 = 30031$~$; but $~$30031 = 59 \times 509$~$. (These are all somewhat ad-hoc; there is no particular reason I knew that taking the first six primes would give me a composite number at the end.) However, we have discovered a new prime this way (in fact, two new primes!): namely $~$59$~$ and $~$509$~$.

In general, this is a terrible way to discover new primes. The proof tells us that there must be some new prime dividing $~$30031$~$, without telling us anything about what those primes are, or even if there is more than one of them (that is, it doesn't tell us whether $~$30031$~$ is prime or composite). Without knowing in advance that $~$30031$~$ is equal to $~$59 \times 509$~$, it is in general very difficult to discover those two prime factors. In fact, it's an open problem whether or not prime factorisation is "easy" in the specific technical sense of there being a polynomial-time algorithm to do it, though most people believe that prime factorisation is "hard" in this sense.