infinitude of primes I have just started studying elementary number theory and I really enjoyed reading Euclid’s Theorem on the infinitude of primes . When talking with a colleague that loves that area he told me that there are some other proofs of this result. Can you please post some other proofs or at least indicate where I can find them?
 A: One of the more overkill proofs of this fact I'm aware of ties into the Riemann zeta function. It is well known, per Euler's solution to the Basel problem, that
$$\zeta(2) := \sum_{k=1}^\infty \frac{1}{k^2} = \frac{\pi^2}{6}$$
There is an equivalent definition for the zeta function in terms of a product in lieu of a sum:
$$\zeta(s) = \prod_{p \; \text{prime}} \frac{1}{1 - p^{-s}} \implies \prod_{p \; \text{prime}} \frac{1}{1 - p^{-2}} = \frac{\pi^2}{6}$$
Note that each operand in this product is a rational number, and the rational numbers are closed under (finite) multiplication. If there were only finitely many primes, then the result of this product should itself be a rational number; however, $\pi^2/6$ is clearly irrational, thus the supposition that there are finitely many primes is false.
A: Here is a slightly stronger result, coming for free (almost) from one of the standard proofs:
For any non-constant polynomial $f$ with integer coefficients, there are infinitely many distinct prime numbers that divide some $f(n)$ with $n$ an integer.
Proof:
Without loss of generality we may assume that $f$ has degree $n>0$ and its leading coefficient is positive (else consider $-f$, whose integer values are divisible by the same prime numbers as $f$).  Then for some sufficiently large integer $m$, $f(r)$ is a strictly increasing strictly positive valued function for $r\geq m$.
If the $f(r)$ are only divisible by prime numbers $p_1,\cdots,p_k$ then:$$\sum_{r=m}^\infty f(r)^{\frac{-1}{n+1}}\leq \prod_{i=1}^k\frac1{1-\left(\frac1{p_i}\right)^{\frac1{n+1}}},$$
as all the terms on the LHS are contained in the expansion of the right hand side.
However the left hand side diverges, as the terms of the sum are bounded below by $\frac\lambda r$ for some positive constant $\lambda$.
