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,\dots ,p_n$. Since we know $2$ is prime, we know $2$ appears in that list.

Then consider the number $P=p_1{p}_2\dots p_n+1$ — that is, the product of all primes plus 1. Since $2$ appeared in the list, we know $P\ge 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.