Brunの最初の篩（素数による篩）

$$(x_1+\cdots +x_r)^k=\sum_{1\leq i_1, i_2, \ldots, i_k\leq r} x_{i_1}x_{i_2}\cdots x_{i_k} \geq \sum_{\substack{1\leq i_1, i_2, \ldots, i_k\leq r,\\ i_p=i_q\Longrightarrow p=q}} x_{i_1}x_{i_2}\cdots x_{i_k}$$
となる。

$1\leq j_1< j_2<\ldots< j_k\leq r$ となる $(j_1, j_2, \ldots, j_k)$ をひとつとる。右辺の和のなかにある項で、$x_{i_1}x_{i_2}\cdots x_{i_k}=x_{j_1}x_{j_2}\cdots x_{j_k}$ となるのは、$(i_1, i_2, \ldots, i_k)$ が $(j_1, j_2, \ldots, j_k)$ の置換であるものであり、そのようなものに限られるから、
$$(x_1+\cdots +x_r)^k=\sum_{1\leq i_1, i_2, \ldots, i_k\leq r} x_{i_1}x_{i_2}\cdots x_{i_k} \geq (k!)\sum_{1\leq j_1< j_2< \cdots< j_k\leq r} x_{j_1}x_{j_2}\cdots x_{j_k}=(k!)s_k(x_1, \ldots, x_r)$$
となる。

相異なる素数の積 $d$ について、
$$A_d=\bigcap_{p\mid d} A_p$$
とおくと、
$$A_d=\#\{n: M< n\leq M+X, p\mid d\Longrightarrow (1\leq \exists u(p)\leq \rho(p))[n\equiv a(p, u(p))\Mod{p}]\}$$
となる。

中国式剰余定理 から、相異なる素数の積 $d=p_1 p_2 \cdots p_k$ について、
$$n\equiv r_i\Mod{p_i}\ (\forall i=1, 2, \ldots, k)\Longleftrightarrow n\equiv U(r_1, r_2, \ldots, r_k)\Mod{d}$$
となる剰余類 $U(r_1, r_2, \ldots, r_k)\Mod{d}$ が一意的に定まる。$1\leq d_i\leq \rho(p_i)\ (1\leq i\leq k)$ となる $(d_1, d_2, \ldots, d_k)$ について
$$U(a(p_1, d_1), a(p_2, d_2), \ldots, a(p_k, d_k))\Mod{d}$$
は相異なる剰余類で、
$$A_d=\#\{n: M< n\leq M+X, n\equiv U(a(p_1, d_1), a(p_2, d_2), \ldots, a(p_k, d_k))\Mod{d}\}$$
となる（ただし、各 $d_i$ は $1\leq \exists d_i\leq \rho(p_i)$ となる整数）ので、
$$\# A_d\leq \rho(d)\left(\floor{\frac{(M+X)}{d}}-\floor{\frac{M}{d}}\right)<\frac{\rho(d)X}{d}+\rho(d)$$
かつ
$$\# A_d\geq \rho(d)\left(\floor{\frac{(M+X)}{d}}-\floor{\frac{M}{d}}\right)>\frac{\rho(d)X}{d}-\rho(d)$$
となる。つまり
$$\label{eq2}\abs{\# A_d-\frac{X}{d}}<\rho(d)\tag{2}$$
が成立する。

$$\mu_k(d)=\left\{\begin{array}{cl} \mu(d)=(-1)^{\omega(d)} & (\omega(d)\leq k), \\ 0 & (\omega(d)>k) \end{array}\right.$$
とおくと、$m$ が偶数のときBrunの最初の篩より
$$\# S(A, z)\leq \sum_{d\mid P(z)} \mu_m(d)\# A_d$$
となる。

そこで、$m>2e(\kappa\log\log z+B_0)$ となるように偶数 $m$ をとると、 \eqref{eq2}より
$$\label{eq3}\begin{split} \# S(A, z)\leq & \sum_{d\mid P(z), \omega(d)\leq m} \mu(d) \# A_d \\ = & \sum_{d\mid P(z), \omega(d)\leq m} \left(\frac{\mu(d)\rho(d) X}{d}+O^*(\rho(d))\right) \\ = & X\sum_{d\mid P(z)} \frac{\mu(d)\rho(d)}{d} \\ & +O^*\left(X\sum_{d\mid P(z), \omega(d)\geq m+1} \mu(d)\frac{\rho(d)}{d}+\sum_{d\mid P(z), \omega(d)\leq m} \rho(d)\right) \end{split}\tag{3}$$
が成り立つ。以下、この右辺の各項について考察する。

まず、$\mu(d)\rho(d)/d$ は乗法的関数だから
$$\label{eq4}\sum_{d\mid P(z)} \frac{\mu(d)\rho(d)}{d}=\prod_{p< z}\left(1-\frac{\rho(p)}{p}\right)\tag{4}$$
となる。

$z$ 以下の素数を $p_1, \ldots, p_r$ とおくと
$$\begin{split} \sum_{d\mid P(z), \omega(d)\geq m+1} \frac{\rho(d)}{d} = & \sum_{k=m+1}^r \sum_{d\mid P(z), \omega(d)=k} \frac{\rho(d)}{d} \\ = & \sum_{k=m+1}^r \sum_{\{i_1, \ldots, i_k\} \subset \{1, \ldots, r\}} \left(\frac{\rho(p_{i_1})}{p_{i_1}}\right)\cdots\left(\frac{\rho(p_{i_k})}{p_{i_k}}\right) \\ = & \sum_{k=m+1}^r s_k\left(\frac{\rho(p_1)}{p_1}, \ldots \frac{\rho(p_r)}{p_r}\right) \end{split}$$
となるので、 補題1 およびStirlingの公式より
$$\begin{split} \sum_{d\mid P(z), \omega(d)\geq m+1} \frac{\rho(d)}{d} \leq & \sum_{k=m+1}^r \frac{1}{k!}\left(\sum_{p< z} \frac{\rho(p)}{p}\right)^k \\ < & \sum_{k=m+1}^r \left(\frac{e}{k}\right)^k \left(\sum_{p< z} \frac{\rho(p)}{p}\right)^k \\ < & \sum_{k=m+1}^r \left(\frac{e}{m}\right)^k \left(\sum_{p< z} \frac{\rho(p)}{p}\right)^k \end{split}$$
となるが、仮定より
$$\sum_{d\mid P(z), \omega(d)\geq m+1} \frac{\rho(d)}{d}<\sum_{k=m+1}^r \left(\frac{e(\kappa \log\log z+B_0)}{m}\right)^k$$
となる。
$m>2e(\kappa\log\log z+B_0)$ となるように $m$ をとっているので、
$$\label{eq5}\sum_{d\mid P(z), \omega(d)\geq m+1} \frac{\rho(d)}{d}<\sum_{k=m+1}^r \frac{1}{2^k}=\frac{1}{2^m}\tag{5}$$
となる。

さらに、仮定より
$$\label{eq6}\begin{split} \sum_{d\mid P(z), \omega(d)\leq m} \rho(d) = & \sum_{k=1}^m\sum_{\{i_1, \ldots, i_k\} \subset \{1, \ldots, r\}}\rho(p_{i_1})\cdots \rho(p_{i_k}) \\ \leq & \sum_{k=1}^m \left(\sum_{p< z}\rho(p)\right)^k \\ \leq & \left(1+\sum_{p< z}\rho(p)\right)^m \end{split}\tag{6}$$
となる。

\eqref{eq4}, \eqref{eq5}, \eqref{eq6}を\eqref{eq3}に適用して
$$\# S(A, z)=X\prod_{p< z}\left(1-\frac{\rho(p)}{p}\right)+O^*\left(\frac{X}{2^m}+\left(1+\sum_{p< z}\rho(p)\right)^m\right)$$
となって、定理が証明される。