1.1. Eratosthenes 筛法和等差数列上的筛法

筛法最早起源于古希腊的 Eratosthenes. 他在研究数论问题的时候构思出了一种快速寻找素数的办法. 这种方法后来演变成了一种计算机算法, 但本讲义中我们只关注这个方法的数论部分.

简而言之, 他发现如果正整数 $n$ 不能被 $\le \sqrt{n}$ 的素数整除, 那么它必然不可能是合数. 我们可以定义符号 $\pi (x;p_1,p_2,\dots ,p_r)$, 来表示满足下列条件的正整数 $n$ 之个数:

$$n\le x,n\not\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{p}_i)(1\le i\le r),$$(1.1.1)

则当 $2=p_1<p_2<\cdots <p_r\le \sqrt{x}$ 表示所有大小不超过 $x$ 的素数时, 总有:

$$\pi (x;p_1,p_2,\dots ,p_r)=\pi (x)-\pi (\sqrt{x})+1.$$(1.1.2)

从 (1.1.2) 中, 我们可以看出 $\pi (x;p_1,\dots ,p_r)$ 可以被用来估计 $\pi (x)$ 的大小. 更一般地, 当 $p_1,p_2,\dots ,p_r$ 仅表示一些不同的素数时总有:

$$\pi (x)\le \pi (x;p_1,p_2,\dots ,p_r)+r-1.$$(1.1.3)

这是因为对于所有的 $1\le i\le r$, 素数 $p$ 只可能满足下面两个性质中的一个:

1.	$p\not\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{p}_i)$,
2.	$p\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{p}_i)$.

其中第一种情况会被 $\pi (x;p_1,\dots ,p_r)$ 数到, 而第二种情况最多只能出现 $r$ 次. 因为 $\pi (x;p_1,\dots ,p_r)$ 在计数的时候删去了一些落在特定同余类中的整数, 所以此类函数也被称为筛函数 (sieve function) .

筛函数 $\pi (x;p_1,\dots ,p_r)$ 是直接在整数集里删除同余类的, 但实际上我们可以在此基础上再限制这些整数落在一个特定的同余类中. 因此 Brun 定义了 $N(a,q,x;p_1,\dots ,p_r)$ 来统计满足下列条件的正整数 $n$ 的个数:

$$n\le x,n\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}q),n\not\equiv a_i(\mathrm{m}\mathrm{o}\mathrm{d}{p}_i)(1\le i\le r),$$(1.1.4)

其中对于所有的 $1\le i\le r$ 均有 $0\le a_i<p_i$. 特别地, Brun [2] 证明了 $(a,q)=1$ 时对于所有的 $a_i$, 当 $x$ 充分大、$p_1,\dots ,p_r$ 表示全体大小不超过 $x^{1/6}$ 且不整除 $q$ 的素数时, 总有:

$$N(a,q,x;p_1,\dots ,p_r)>\frac{1.007x}{\phi (q)\log x}.$$(1.1.5)

对于任何正整数 $N$, 若其没有 $\le N^{1/6}$ 的素因子则其素因子个数必然不超过 5. 利用这一点, Brun [2] 得到了结论:

定理 1.1.0.1 (Brun). 任何首项与公差互素的等差数列上都具有无穷个素因子个数不超过 5 的整数.

虽然这个结论远远弱于等差数列上的 Dirichlet 定理, 但它是通过一种极其初等的手段推导出来的. 从这个具体的例子中我们可以看出 Brun 方法得到的筛函数下界与具体的 $a_1,a_2,\dots ,a_r$ 的取值无关, 而仅仅与同余方程的个数有关. 在接下来的例子中我们可以更加深刻地认识到筛法的这种特点.