Quite a well-known and old problem. :smile: Suppose for contradiction that there exist a finite number of primes $p_1, p_2, \dots, p_n$. Let $Q=p_1p_2 \dots p_n+1$ All integers greater than 1 have a (unique) decomposition into primes, but $Q>1$ is not divisible by any prime- contradiction.

Lol, I can just imagine somebody saying "Dirichlet's Theorem states that there exist infinitely many primes of the form ak+b for constant a,b. Taking this set, we have a proof that there exist infinitely many primes."

Ilthigore wrote: Lol, I can just imagine somebody saying "Dirichlet's Theorem states that there exist infinitely many primes of the form ak+b for constant a,b. Taking this set, we have a proof that there exist infinitely many primes." Basicly that's the same discussion as we had here. It depends on wether you are trying to establish results as a research result, or by elementary means.

I always liked to look for elementary proofs of special cases of Dirichlet's theorem. Small moduli like $4$ (consider divisors of $n^2+1$ and $4n-1$) and $3$ (consider $x^2+x+1$ and $3x-1$) are well known, and so is $1 \mod n$ for arbitrary $n$ (consider cyclotomic polynomials; for $n$ prime some nice proofs are given by some Baltic Way problems). But if one wants to get more, it get's complicated (there is a polynomial that works out for primes $\equiv a \mod n$ iff $a^2 \equiv n$; especially $a=-1$ being the next easiest case after the already mentioned $a=1$ works).

Here I give the verbatim proof of this resultgiven by Furstenberg in 1955. Its a topological proof. His proof was:" In this note we would like to offer an elementary 'topological' proof of the infinitude of the prime numbers. We introduce a topology into the space of integers S, by using the AP as a basis. It is not difficult to verify that this actually yields a topological space. In fact, under this topology, S may be shown to be normal and hence metrizable. Each AP is closed as well as open, since its complement is the union of other APs (having same CD). As a result , the union of any finite number of APs is closed. Consider now the set A=union of A1, where A1 consists of all multiples of p, and p runs through the set of primes. The only number not belonging to A are -1 and 1, and since the set {-1,1} is clearly not an open set, A cannot be closed. Hence A is not a finite union of closed sets which proves that there are infinity of primes". Golomb developed this further and wrote an interesting short paper in 1959.

- Actually, every proof of E-24 can be regarded as a proof of the infinitude of primes. Well, as long as that E-24 proof doesn't take for granted what we wished to settle in the first place. - There is also this beautiful proof given by Pólya whose main ingredient is the pairwise coprimality of the Fermat numbers. - A proof which you are not likely to encounter in most textbooks is the one that resorts to the Chinese Remainder Theorem. In fact, this proof is nothing more than a disguised presentation of the well-known euclidean argument yet, you can't blame a man for dreaming... - I came up with the following wacky proof several months ago: fix $ n \in \mathbb{N}$. For every $ k \in \mathbb{Z}^{ + }$, Bertrand's Postulate allows us to ascertain the existence of a prime number $ p_{k}$ in the interval $ I_{k} = (2^{k} \cdot n,2^{k + 1} \cdot n]$. Since the intervals $ I_{k}$ are pairwise disjoint and there are infinitely many of them, the veracity of E-12 follows at once. How do you like this proof-proposal of mine?

Lemme add another proof. Suppose that $p_i \quad (1\leq i\leq s)$ are the only primes. But then $$\infty=\sum_{j\geq 1}{\dfrac{1}{j}}=\prod_{i=1}^{s}{\sum_{k=0}^{\infty}{\dfrac{1}{p_i ^k}}}=\prod_{i=1}^{s}{\dfrac{p_i}{p_i-1}}$$The last product however is finite $\therefore$ Contradiction .