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.