Euclid's proof that there are infinitely many primes is famous, but I want to understand it deeply.
Assume $p_1, p_2, \ldots, p_n$ are all the primes. Consider $N = p_1 p_2 \cdots p_n + 1$. Then $N$ is either prime or has a prime factor not in our list, contradiction.