How to apply the Chinese remainder theorem in proof of Euclid's theorem.

Question

Recently I saw a "sieve-theoretic" proof of Euclid's theorem (that there exist infinitely many primes) (e.g. https://math.stackexchange.com/a/1153069/567299). In that proof, one uses the fact that the density of the set $A$ of numbers that are not divisible by any of these (finitely many) primes is $d(A_n) =\prod_{i=1}^n\frac{p_i-1}{p_i}$. While I do understand this fact intuitively I cannot see how this fact follows from the Chinese remainder theorem. To my knowledge this theorem states that there is a ring isomorphism $\mathbb Z/N\mathbb Z \cong \mathbb Z / p_1 \mathbb Z \times \ldots \mathbb Z / p_k \mathbb Z$. But how can I use this to make a quantitative statement about the density of $A$? Can anyone help me out here?

Answer 1

Let $N = p_1p_2\cdots p_k$. Chinese Remainder Theorem says $\mathbb Z/N\mathbb Z \cong \mathbb Z/p_1 \mathbb Z\times \mathbb Z/p_2 \mathbb Z\times \cdots \times \mathbb Z/p_k \mathbb Z$, and $x\pmod N \mapsto (x \!\!\mod p_1, \cdots, x\!\! \mod p_k)$ gives a bijection.

If $x$ is not divisible by any of $p_1, \cdots, p_k$, then $x \pmod N$ is uniquely determined by $(x \!\!\mod p_1, \cdots, x \!\!\mod p_k)$, and there are $p_i-1$ possibilities for $x \!\!\mod p_i$ for each $p_i$, hence there are $\prod_{i=1}^k (p_i-1)$ possibilities for $x \pmod N$.

Then you need to calculate the density. What we know at this moment is that, for any consecutive $N$ numbers, there are exactly $\prod_{i=1}^k (p_i-1)$ numbers which is not divisible by $\{p_1, \cdots, p_k\}$.

Let $M>0$ be an integer. we need to count the numbers of integers in the range $[-M, M]$ which is not divisible by $\{p_1, \cdots, p_k\}$. We know that if we take the integers into groups, such that each group contains $N$ integers, the number of groups is between $\lfloor \frac{2M}N\rfloor$ and $\lfloor \frac{2M}N \rfloor + 1$. So the number of integers in $[-M, M]$ not divisible by $\{p_1, \cdots, p_k\}$ is bounded between $\lfloor \frac{2M}N\rfloor\prod_{i=1}^k (p_i-1)$ and $(\lfloor \frac{2M}N\rfloor+1)\prod_{i=1}^k (p_i-1)$, and the density is bounded between $\frac{1}{2M+1}\lfloor \frac{2M}N\rfloor\prod_{i=1}^k (p_i-1)$ and $\frac{1}{2M+1}(\lfloor \frac{2M}N\rfloor+1)\prod_{i=1}^k (p_i-1)$.

Taking the limit $M \to \infty$, and you get the desired density.

Answer 2

What he's saying is that if $x$ is not divisible by any of $p_1,p_2,...,p_n,$ then $x$ is a solution to$$ x\equiv a_1\pmod{p_1}\\ x\equiv a_2\pmod{p_2}\\ \vdots\\ x\equiv a_n\pmod{p_n}\\ $$ where $0<a_i<p_i,\space 1\le i\le n.$ Counting the number of such systems gives the result.