篩法

この同値性こそが篩を早期に止めることを可能にするものである:$\sqrt N$ までのすべての素数が倍数を消し終えれば、残るいかなる数も合成数だと立証する証人はもう存在しない。したがって、より大きい素数を検査する(あるいは消す)ことは証明可能に無駄な作業である。

($\Leftarrow$) $n$ が $\le\sqrt n$ の素因数を持たないと仮定する。もし $n$ が合成数なら $n=ab$、$1<a\le b<n$ と書ける。このとき $a\le\sqrt n$(そうでなければ $a>\sqrt n$ かつ $b\ge a>\sqrt n$ となり $ab>n$ を強制し矛盾)であり、$a$ の最小素因数 $p$ は $p\le a\le\sqrt n$ を満たすので、$p$ は $n$ の $\le\sqrt n$ の素因数となり——仮定に矛盾する。よって $n$ はそのような分解を持たず、$n$ は素数である。

($\Rightarrow$) $n$ が素数なら、その正の約数は $1$ と $n$ のみであり、$p<n$ を満たすいかなる素数もそれを割り切らない。特に $p\le\sqrt n$ のものも割り切らない。

これらを合わせると2つの条件が同値であることが示され、これはまさに篩で用いられる終了条件である:$\sqrt N$ までのすべての素数を処理した後、$[2,N]$ の中でまだマークされていないものはすべて右辺を満たし、したがって素数である。

これは「倍数を消す」という操作の正確で定量的なバージョンである:格子に物理的に印をつける代わりに、どの小さい素数がそれらを割り切るかについての包除原理で生存者を直接数える。これは双子素数や有界な素数間隔を攻略するために使われるすべての現代的な篩(ブラン、セルバーグ、大篩、GPY)の祖先であり——それらはすべて、根本的にはこの正確な公式が生み出す誤差項を制御するためのより賢い方法である。

任意の整数 $a\in A$ が $P(z)$ と互いに素であるための必要十分条件は、$p<z$ を満たすいかなる素数でも割り切れないことである。各約数 $d\mid P(z)$(これらの素数の部分集合の無平方な積)について、$A=\{1,\ldots,x\}$ における $d$ の倍数の個数はちょうど $\lfloor x/d\rfloor$ である。

$p<z$ に対する事象「$p\mid a$」に関する包除原理により、$\mathcal P$ の中の少なくとも1つの素数で割り切れる $a\in A$ の個数は $\sum_{p<z}\lfloor x/p\rfloor - \sum_{p<q}\lfloor x/(pq)\rfloor + \sum_{p<q<r}\lfloor x/(pqr)\rfloor - \cdots$ であり、掛け合わせる素数の個数に応じて符号が交代する。この交代する符号は、対応する無平方な $d\mid P(z)$ のメビウス関数 $\mu(d)$ そのものである:$\mu(1)=1$、$d$ が $k$ 個の異なる素数の積のとき $\mu(d)=(-1)^k$。

したがって $\mathcal P$ の中の少なくとも1つの素数で割り切れる個数は $-\sum_{d\mid P(z),\,d>1}\mu(d)\lfloor x/d\rfloor$。これを $|A|=\lfloor x\rfloor=x$($d=1$ の項、$\mu(1)\lfloor x/1\rfloor=x$)から引くと $P(z)$ と互いに素な個数が得られる:$S(A,\mathcal P,z)=x-\sum_{d\mid P(z),d>1}\mu(d)\lfloor x/d\rfloor=\sum_{d\mid P(z)}\mu(d)\lfloor x/d\rfloor$。

最後に $z=\sqrt x+1$ とすると $\mathcal P$ はちょうど $\le\sqrt x$ の素数となる:これらすべてと互いに素な任意の $a\in[2,x]$ は $1$ であるか、または(上の定理により $\le\sqrt x$ の素因数を持たないので)$>\sqrt x$ の素数であるので、$S(A,\mathcal P,\sqrt x+1)=1+\big(\pi(x)-\pi(\sqrt x)\big)$ となり、主張の等式が得られる。