Playing around with elementary inclusion-exclusion, I arrived at two simple variations of proofs of Euclid's theorem that I thought would be long known in the literature. So far I haven't been able to find any mention of them, despite their simplicity, but perhaps someone here knows where to look.

In it's simplest form, one proof is just the realization that in any interval of length $p_k\#:=\prod_{p\in P_k} p$, where $P_k:=\{p_1,\dots,p_k\}$ is the set of the $k$ first primes, there are exactly $$ p_k\# \cdot \prod_{p\in P_k} \left(1 - \frac{1}{p}\right)=\prod_{p\in P_k} \left(p - 1\right)\geq1 $$ integers coprime to $p_k\#$. Since this holds for any $k$, there must be infinitely many primes.

It seems useful, however, to formulate the proofs in terms of sieving: Let the number of coprimes to $p_k\#:=\prod_{p\in P_k} p$ in the random interval $A$ be represented by the sifting function $$ S(A,p_k\#) := |\{n: n\in A, (n,p_k\#)=1 \}|. $$ By definition, the sifting function is periodic with period $p_k\#$, so that $$ S(A,p_k\#)=S(A+p_k\#,p_k\#), $$ where $A+p_k\#$ denotes a left-shift of $A$ of length $p_k\#$. For a random interval $A$, it follows from the argument of inclusion-exclusion that $S(A,p_k\#)$ has expectation value $$ E[S(A,p_k\#)] = |A| \cdot \prod_{p \in \mathcal P_k} \left(1- \frac{1}{p}\right). $$ In general, the error term is problematic. By expanding the Euler product, we arrive at $$ S(A,p_k\#) = \lfloor |A| \rceil - \sum_{q\in \mathcal P_k} \left\lfloor \frac{|A|}{q} \right\rceil + \sum_{\substack{{q_1, q_2 \in \mathcal P_k} \\ {q_1 < q_2}}} \left\lfloor \frac{|A|}{q_1 q_2} \right\rceil - \dots \pm \sum_{\substack{{q_1, \dots, q_k \in \mathcal P_k} \\ {q_1 < \dots < q_k} }} \left\lfloor \frac{|A|}{q_1 \dots q_k} \right\rceil, $$ where $\lfloor x \rceil$ is defined to mean that $x$ take either values $\lfloor x \rfloor$ or $\lceil x \rceil$. Since there are $2^k$ terms in this expansion that each can be rounded up or down, this gives an error term of order $2^k$. For this reason, proving Euclid's theorem is hard from a sieve theoretic perspective. However, this situation changes if we exploit the periodicity of $S(A,p_k\#)$, as the two proofs below demonstrates.

Theorem (Euclid's theorem) There are infinitely many primes.

Proof 1 Assume two intervals $A=\{1\}$ and $B=\{1+p_k \#\}$ of length 1. Because of periodicity and the fact that 1 is coprime to any prime, we have for $k\geq1$ that $$ S(B,p_k \#) = S(A,p_k \#) = 1. $$ Hence, $1+p_k\#$ is coprime to $p_k\#$ and is either a prime $p>p_k$ or a composite of primes all larger than $p_k$. Either way, there is always a prime $p>p_k$ for any $k$, and therefore infinitely many primes.

Proof 2 Let $A$ be an arbitrary interval of length $|A|=p_k\#$. Because of periodicity, $S(A,p_k\#)$ takes the exact same value for any $A$: $$ S(A,p_k\#)= p_k\# \cdot \prod_{p \in \mathcal P_k} \left(1- \frac{1}{p}\right) = \prod_{p\in P_k} \left( p-1 \right) \geq 1. $$ Hence, in any sequence of length $p_k\#$, we find $\prod_{p\in P_k} \left( p-1 \right)$ integers coprime to $p_k\#$, each of which is either a prime $p > p_k$ or a composite with prime factors all larger than $p_k$. Either way, there is always a prime $p>p_k$ for any $k$, and therefore infinitely many primes.

Note that Proof 1 is very close to Euclid's original proof, with the difference that here we explicitly exploit the periodic structure that follows from a finite number of sieve steps. There are several more comments to make on this perspective, but let me initially boil it all down to the sharp question:

Are these proofs of Euclid's theorem known?

  • $\begingroup$ Perhaps you can derive more with your method than Euclid theorem alone. Glancing at your post I don't feel need for a relatively complex proof of simply the infinitude of primes, while I am sure that several people, including myself, enjoy making up new simple proofs. $\endgroup$ – Włodzimierz Holsztyński Jun 10 '14 at 9:04
  • $\begingroup$ Did you read the short version of the proof in the second paragraph? Doesn't really get much simpler than that. The reason for adding the sieve notation further down in the text is that it is useful for doing more as you suggest, as e.g. looking at arithmetic progressions and gap structures, but I wouldn't want to obscure the question too much. $\endgroup$ – user45947 Jun 11 '14 at 13:19
  • 1
    $\begingroup$ This time I've concentrated on your second paragraph. It's cute, I like it and I up-voted your question. Let me also add that the Euclid proof is so fundamental and simple that any other reasonable simple proof of infinitude actually has to be strengthening of the original. $\endgroup$ – Włodzimierz Holsztyński Jun 13 '14 at 6:12

Your Answer

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

Browse other questions tagged or ask your own question.