2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\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.