15
$\begingroup$

Many guides will refer to Euler's product formula as simple way to prove that the number of primes is infinite.

$$\sum_n\frac{1}{n} = \prod_p \frac{1}{1-\frac{1}{p}}$$

The argument is that if the primes were finite, the product on the right hand side is finite, noting that $1-\frac{1}{p}$ is never zero.

However, the product formula itself is constructed by application of the fundamental theorem of arithmetic to an infinite series with terms involving only primes.

Does this mean such proofs are a circular argument - because they use a product formula whose construction depends entirely on the infinitude of primes?

$\endgroup$
9
  • 2
    $\begingroup$ "Many guides will refer to Euler's product formula as simple way to prove that the number of primes is infinite." Can you name such a guide? How do such guides prove Euler's product formula? I'm having a hard time seeing how anyone would accept and believe it on faith be then require a proof that there are infinitely many primes. $\endgroup$
    – fleablood
    Jul 5, 2020 at 22:01
  • 1
    $\begingroup$ Euler formula is a trivial corollary of the formula for the sum of geom progression and the standard way of multiplying absolutely converging series. $\endgroup$
    – markvs
    Jul 5, 2020 at 22:26
  • 18
    $\begingroup$ How does the Fundamental Theorem of Arithmetic rely on the infinitude of primes? All it says is that every integer greater than $1$ is uniquely, modulo rearrangement, the product of a finite number of primes. $\endgroup$
    – robjohn
    Jul 5, 2020 at 22:26
  • 3
    $\begingroup$ @JiK: The point is, that if there were finitely many primes, the Fundamental Theorem of Arithmetic says that the infinte sum (which diverges) equals the finite product (which converges because it is finite). The infinite series depends on the infinitude of the integers. The product is taken over the primes, whether they be finite or infinite. If the are finite, we have a contradiction. $\endgroup$
    – robjohn
    Jul 7, 2020 at 10:05
  • 3
    $\begingroup$ @JK: My original comment was to question why the OP thinks that this is "a product formula whose construction depends entirely on the infinitude of primes". The construction does not rely on the infinitude of primes, only on the Fundamental Theorem of Arithmetic. There is no "infinite series with terms involving only primes"; the terms of the infinite series only involves consecutive integers. There is a product (which might be finite or infinite) which equals the series by the Fundamental Theorem of Arithmetic. $\endgroup$
    – robjohn
    Jul 7, 2020 at 10:23

3 Answers 3

26
$\begingroup$

To prove the equality you need that every natural number is uniquely represented as a product of primes. It does not need the fact that the set of primes is infinite. In fact to prove that the set of primes is infinite, you do not need Euler equality. You only need inequality $LHS \le RHS$ which follows from the fact that every number is a product of primes (uniqueness is not needed). If you compare that proof with Euclid's original proof, it is not clear which one uses less prior infomation about primes.

$\endgroup$
19
$\begingroup$

No, the proof is not circular. If we assume there are a finite number of primes $p_1,\ldots,p_k$, then we would assume that any $n\in\mathbb{N}$ would be able to be factorized as $p_1^{\alpha_1}\ldots p_k^{\alpha_k}$. (The proof of the Fundamental Theorem of Arithmetic does not require that there be an infinite number of primes.) This would lead to the Euler product formula, which we would then use to provide the contradiction, once we have shown that $\sum_{n\in\mathbb{N}} \frac1n$ is infinite.

$\endgroup$
3
  • $\begingroup$ This is what is unclear to me: there may be an integer $n$ on the LHS that has a prime factorisation not found on the RHS because the RHS is limited to using finite primes. Only if we have infinite primes can we guarantee that any given $n$ has a prime factorisation on the right. Where am I going wrong? $\endgroup$
    – Penelope
    Jul 7, 2020 at 1:04
  • 5
    $\begingroup$ @TariqRashid Reread the proof of the Fundamental Theorem of Arithmetic. The proof of existence involves strong induction; for any $n\in\mathbb{N}$, either $n$ is prime, or $n$ is composite, meaning it is the product of two factors, each of which has a prime factorization. If we assume that there are finitely many primes, then past a certain point, every $n$ will be composite, and thus can be factorized by $p_1,\ldots,p_k$. Nowhere do we assume that there are infinitely many primes. $\endgroup$ Jul 7, 2020 at 2:08
  • 2
    $\begingroup$ In other words, if there are only finitely many primes, then the fact that the RHS has only finitely many primes isn't a limitation—there are, in this supposition, no primes missing from that infinite product. Of course this isn't a fact, and so you can point out all kinds of problems with it, but that's how an argument by contradiction works: it postulates a world counter to expectations, and then shows how rigorous reasoning within that world leads to contradiction. $\endgroup$
    – LSpice
    Jul 18, 2020 at 15:21
7
$\begingroup$

As others already noted, it's non-circular because the FTA doesn't assume infinitely many primes. In fact, the original proof there are infinitely many primes uses a fragment of the FTA. We multiply together finitely many primes and add $1$, and to continue the argument we need to know the result will have some prime factor. We prove this helpful result early in the proof of the FTA.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.