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?

simpleproofs. $\endgroup$ – Włodzimierz Holsztyński Jun 10 '14 at 9:04