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

$$(x_1+\cdots +x_r{)}^k=\sum _{1\le i_1,i_2,\dots ,i_k\le r}{x}_{i_1}{x}_{i_2}\cdots x_{i_k}\ge \sum _{\begin{array}{c}1\le i_1,i_2,\dots ,i_k\le r,\\ i_p=i_q⟹p=q\end{array}}{x}_{i_1}{x}_{i_2}\cdots x_{i_k}$$
となる。

$1\le j_1<j_2<\dots <j_k\le r$ となる $(j_1,j_2,\dots ,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,\dots ,i_k)$ が $(j_1,j_2,\dots ,j_k)$ の置換であるものであり、そのようなものに限られるから、
$$(x_1+\cdots +x_r{)}^k=\sum _{1\le i_1,i_2,\dots ,i_k\le r}{x}_{i_1}{x}_{i_2}\cdots x_{i_k}\ge (k!)\sum _{1\le j_1<j_2<\cdots <j_k\le r}{x}_{j_1}{x}_{j_2}\cdots x_{j_k}=(k!)s_k(x_1,\dots ,x_r)$$
となる。

相異なる素数の積 $d$ について、
$$A_d=\bigcap _{p\mid d}{A}_p$$
とおくと、
$$A_d=\mathrm{\#}\{n:M<n\le M+X,p\mid d⟹(1\le \mathrm{\exists }u(p)\le \rho (p))[n\equiv a(p,u(p))\left(\mathrm{mod}p\right)]\}$$
となる。

中国式剰余定理 から、相異なる素数の積 $d=p_1{p}_2\cdots p_k$ について、
$$n\equiv r_i\left(\mathrm{mod}{p}_i\right)(\mathrm{\forall }i=1,2,\dots ,k)⟺n\equiv U(r_1,r_2,\dots ,r_k)\left(\mathrm{mod}d\right)$$
となる剰余類 $U(r_1,r_2,\dots ,r_k)\left(\mathrm{mod}d\right)$ が一意的に定まる。$1\le d_i\le \rho (p_i)(1\le i\le k)$ となる $(d_1,d_2,\dots ,d_k)$ について
$$U(a(p_1,d_1),a(p_2,d_2),\dots ,a(p_k,d_k))\left(\mathrm{mod}d\right)$$
は相異なる剰余類で、
$$A_d=\mathrm{\#}\{n:M<n\le M+X,n\equiv U(a(p_1,d_1),a(p_2,d_2),\dots ,a(p_k,d_k))\left(\mathrm{mod}d\right)\}$$
となる（ただし、各 $d_i$ は $1\le \mathrm{\exists }{d}_i\le \rho (p_i)$ となる整数）ので、
$$\mathrm{\#}{A}_d\le \rho (d)(\lfloor \frac{(M+X)}{d}\rfloor -\lfloor \frac{M}{d}\rfloor )<\frac{\rho (d)X}{d}+\rho (d)$$
かつ
$$\mathrm{\#}{A}_d\ge \rho (d)(\lfloor \frac{(M+X)}{d}\rfloor -\lfloor \frac{M}{d}\rfloor )>\frac{\rho (d)X}{d}-\rho (d)$$
となる。つまり
$$\begin{array}{}\text{(2)}& |\mathrm{\#}{A}_d-\frac{X}{d}|<\rho (d)\end{array}$$
が成立する。

$${\mu }_k(d)=\{\begin{array}{cl}\mu (d)=(-1{)}^{\omega (d)}& (\omega (d)\le k),\\ 0& (\omega (d)>k)\end{array}$$
とおくと、$m$ が偶数のときBrunの最初の篩より
$$\mathrm{\#}S(A,z)\le \sum _{d\mid P(z)}{\mu }_m(d)\mathrm{\#}{A}_d$$
となる。

そこで、$m>2e(\kappa \log \log z+B_0)$ となるように偶数 $m$ をとると、 $\text{(2)}$より
$$\begin{array}{}\text{(3)}& \begin{array}{rl}\mathrm{\#}S(A,z)\le & \sum _{d\mid P(z),\omega (d)\le m}\mu (d)\mathrm{\#}{A}_d\\ =& \sum _{d\mid P(z),\omega (d)\le m}(\frac{\mu (d)\rho (d)X}{d}+O^{\ast }(\rho (d)))\\ =& X\sum _{d\mid P(z)}\frac{\mu (d)\rho (d)}{d}\\ & +O^{\ast }(X\sum _{d\mid P(z),\omega (d)\ge m+1}\mu (d)\frac{\rho (d)}{d}+\sum _{d\mid P(z),\omega (d)\le m}\rho (d))\end{array}\end{array}$$
が成り立つ。以下、この右辺の各項について考察する。

まず、$\mu (d)\rho (d)/d$ は乗法的関数だから
$$\begin{array}{}\text{(4)}& \sum _{d\mid P(z)}\frac{\mu (d)\rho (d)}{d}=\prod _{p<z}(1-\frac{\rho (p)}{p})\end{array}$$
となる。

$z$ 以下の素数を $p_1,\dots ,p_r$ とおくと
$$\begin{array}{rl}\sum _{d\mid P(z),\omega (d)\ge 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,\dots ,i_k\}\subset \{1,\dots ,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(\frac{\rho (p_1)}{p_1},\dots \frac{\rho (p_r)}{p_r})\end{array}$$
となるので、 補題1 およびStirlingの公式より
$$\begin{array}{rl}\sum _{d\mid P(z),\omega (d)\ge m+1}\frac{\rho (d)}{d}\le & \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{array}$$
となるが、仮定より
$$\sum _{d\mid P(z),\omega (d)\ge 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$ をとっているので、
$$\begin{array}{}\text{(5)}& \sum _{d\mid P(z),\omega (d)\ge m+1}\frac{\rho (d)}{d}<\sum _{k=m+1}^r\frac{1}{2^k}=\frac{1}{2^m}\end{array}$$
となる。

さらに、仮定より
$$\begin{array}{}\text{(6)}& \begin{array}{rl}\sum _{d\mid P(z),\omega (d)\le m}\rho (d)=& \sum _{k=1}^m\sum _{\{i_1,\dots ,i_k\}\subset \{1,\dots ,r\}}\rho (p_{i_1})\cdots \rho (p_{i_k})\\ \le & \sum _{k=1}^m{(\sum _{p<z}\rho (p))}^k\\ \le & {(1+\sum _{p<z}\rho (p))}^m\end{array}\end{array}$$
となる。

$\text{(4)}$, $\text{(5)}$, $\text{(6)}$を$\text{(3)}$に適用して
$$\mathrm{\#}S(A,z)=X\prod _{p<z}(1-\frac{\rho (p)}{p})+O^{\ast }(\frac{X}{2^m}+{(1+\sum _{p<z}\rho (p))}^m)$$
となって、定理が証明される。