Why are there infinitely many prime numbers? Proof explanation

Euclid's proof is completely rigorous. Let me address your concerns and provide alternative proofs. **Why $N$ is not divisible by any $p_i$:** For any $p_i$ in our list: $$N = p_1 p_2 \cdots p_n + 1 = p_i \cdot (p_1 \cdots p_{i-1} p_{i+1} \cdots p_n) + 1$$ So $N = p_i \cdot k + 1$, where $k$ is an integer. Since $p_i \cdot k$ is divisible by $p_i$, and $1$ is not, $N \equiv 1 \pmod{p_i}$. Therefore $p_i \ mid N$. Now $N > 1$, so $N$ has at least one prime factor $q$. Since $q$ divides $N$ and none of the $p_i$ divide $N$, $q$ cannot be any of the $p_i$. Hence $q$ is a new prime, contradicting the assumption that the list was complete. **Alternative proofs:** 1. **Euler's proof:** $\sum_{p} \frac{1}{p}$ diverges, which would be impossible if there were finitely many primes. 2. **Topological proof (Fürstenberg):** Define a topology on $\mathbb{Z}$ using arithmetic progressions as basis. Each arithmetic progression is both open and closed. If there were finitely many primes, the set $\{-1, 1\}$ would be open, which contradicts compactness. 3. **Proof using Fermat numbers:** Fermat numbers $F_n = 2^{2^n} + 1$ are pairwise coprime. Each has at least one prime factor, so there are infinitely many primes. Euclid's proof remains the simplest and most elegant after 2300 years.