第一章 素数(1)

1、Divisibility of integers(整除性)

如下的数

⋯ ,−3,−2,−1,0,1,2,⋯\cdots,-3,-2,-1,0,1,2,\cdots

称为 rational integers(有理整数)，或者简单地称为 integers(整数)

如下的数

0,1,2,3,⋯0,1,2,3,\cdots

称为 non-negative integers(非负整数)

如下的数

1,2,3,⋯1,2,3,\cdots

称为 positive integers(正整数)

整数 aa 能被另一个整数 b(b≠0)b(b\neq 0) 整除，当且仅当存在一个整数 cc 使得

a=bca=bc

如果 a,b,ca,b,c 都是正数，我们称 a is divisible by b(a能被b整除)

以及 b is a divisor of a(b是a的因子)，记作：

b∣ab\mid a

特别地，b∣0b\mid 0 恒成立，但是 0∣00\mid 0 不成立

相反的，我们用

b∤ab\nmid a

来表示 b∣ab\mid a 的反面，即 a不能被b整除，b不是a的因子

根据整除性的定义，我们可以得到如下结论

b∣a,c∣b→c∣ab\mid a,c\mid b\rightarrow c\mid a

b∣a→bc∣ac(c≠0)b\mid a\rightarrow bc\mid ac(c\neq 0)

c∣a,c∣b→c∣ma+nbc\mid a,c\mid b \rightarrow c\mid ma+nb

2、Prime numbers(质数)

如果数 pp 满足 p>1p>1 且除了 11 和 pp 以外没有其它因子，则称 pp 为 prime(质数/素数)

对应的，大于 11 且不是质数的数称为 composite(合数)

Theorem 1
每个正整数（除了11）都能分解为若干质数的乘积

证明思路非常显然，如果 nn 是质数，那么已经满足要求

否则 nn 必有 n=bcn=bc，重复该过程，直至不能继续分解，即乘积中的数都是质数

根据该定理，我们将该乘积式整理，可以得到

n=p1a1p2a2⋯pkak=∏piain=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}=\prod p_i^{a_i}

这个式子称为 nn 的 standard form(标准分解式)

3、Fundamental theorem of arithmetic(算术基本定理)

Theorem 2（算术基本定理）
nn 的标准分解式是唯一的

这个定理的证明我们将推迟在第二章（原文就是这样写的）

并且这个定理是下一个定理（Theorem 3）的推论

Theorem 3（Euclid's First Theorem（欧几里得第一定理））
如果 pp 是质数，且p∣abp\mid ab，那么p∣a或p∣bp\mid a或p\mid b

这个定理的证明我们将在第二章给出

这个定理可以推广到：

p∣abc⋯l→p∣a或p∣b或p∣c⋯或p∣lp\mid abc\cdots l\rightarrow p\mid a或p\mid b或p\mid c\cdots或p\mid l

特别地，如果 a,b,c,⋯ ,la,b,c,\cdots,l 都是质数，那么 pp 是 a,b,c,⋯ ,la,b,c,\cdots,l 中的一个

接下来我们尝试用定理三去推导定理二

假设

n=p1a1p2a2⋯pkak=q1b1q2b2⋯qjbjn=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}=q_1^{b_1}q_2^{b_2}\cdots q_j^{b_j}

由于 pi∣q1b1q2b2⋯qjbjp_i|q_1^{b_1}q_2^{b_2}\cdots q_j^{b_j}，所以每一个 pp 都在 qq 中，同理，每一个 qq 都在 pp 中，故 k=jk=j

且排序之后有 pi=qip_i=q_i

如果 ai>bia_i>b_i，两边同除以 pibip_i^{b_i}，得到

p1a1⋯piai−bi⋯pkak=p1b1⋯pi−1bi−1pi+1bi+1⋯pkbkp_1^{a_1}\cdots p_i^{a_i-b_i}\cdots p_k^{a_k}=p_1^{b_1}\cdots p_{i-1}^{b_{i-1}} p_{i+1}^{b_{i+1}}\cdots p_k^{b_k}

这样的话，pi∣Leftp_i\mid Left，pi∤Rightp_i\nmid Right，两边不可能相等

ai<bia_i<b_i 的情况也是一样的，所以我们知道 ai=bia_i=b_i，这样我们就证明了定理二

4、The sequence of primes(质数序列)

质数序列是

2,3,5,7,11,13,17,19,26,29,31,37,41,43,47,53,⋯2,3,5,7,11,13,17,19,26,29,31,37,41,43,47,53,\cdots

使用 sieve of Eratoshenes(埃氏筛) 可以得到给定范围内的所有质数

Theorem 4（Euclud's Second Theorem（欧几里得第二定理））
素数的个数是无限的

我们将在第二章证明这个定理，记

q=2×3×5⋯pq=2\times 3\times 5\cdots p

那么容易发现

q+2,q+3,q+4,⋯ ,q+pq+2,q+3,q+4,\cdots,q+p

都是合数，我们有下面的定理

Theorem 5
对于任意的正整数 NN，存在连续的 NN 个正整数都是合数

据此，我们还可以有下面的推测：

形如 (p,p+2)(p,p+2) 的质数对是无限的，(p,p+4,p+6)(p,p+4,p+6) 的质数对也是无限的

但是 (p,p+2,p+4)(p,p+2,p+4) 一定不是质数对，因为其中必有一个是 33 的倍数

5、Some question(若干问题)

（1）是否存在一个简单的公式可以计算第 nn 个质数 pnp_n 的值？

目前没有，而且这个公式存在的可能性是微乎其微的

目前的公式要么依赖于 pnp_n 本身，要么本质上和埃氏筛等价或者比埃氏筛更为复杂

（2）是否存在一个简单的公式可以由 pn−1p_{n-1} 得到 pnp_n ？

（3）是否存在一条规则可以找到一个比 pnp_n 大的质数

曾经 Fermat(费马) 找到过一个这样的公式，但是后来被证明是错误的

（4）在小于给定的 xx 之内，有多少个质数？

我们记 π(x)\pi(x) 表示不超过 xx 的质数个数，那么有

π(pn)=n\pi(p_n)=n

所以 π(n)\pi(n) 与 pnp_n 互为 inverse function(反函数)

所以该问题与问题（1）等价

6、Some notations(若干符号)

这里我们要说明一些常用的符号

O,o,∼,≺,≻,≍\mathcal{O},\mathcal{o},\sim,\prec,\succ,\asymp

设 ϕ(x)\phi(x) 是取值为正的函数，f(x)f(x) 是任一函数，当 x→x0（或±∞）x\rightarrow x_0（或\pm\infty） 时

（1）f(x)=O(ϕ(x))f(x)=\mathcal{O}(\phi(x))：存在常数 AA 使得 ∣f(x)∣<Aϕ(x)|f(x)|<A\phi(x)

（2）f(x)=o(ϕ(x))f(x)=\mathcal{o}(\phi(x))：f(x)ϕ(x)→0\frac{f(x)}{\phi(x)}\rightarrow 0

（3）f(x)∼ϕ(x)f(x)\sim \phi(x)：f(x)ϕ(x)→1\frac{f(x)}{\phi(x)}\rightarrow 1

（4）f(x)≺ϕ(x)f(x)\prec \phi(x)：f(x)ϕ(x)→0\frac{f(x)}{\phi(x)}\rightarrow 0

（5）f(x)≻ϕ(x)f(x)\succ \phi(x)：f(x)ϕ(x)→∞\frac{f(x)}{\phi(x)}\rightarrow \infty

（6）f(x)≍ϕ(x)f(x)\asymp \phi(x)：存在常数 A1,A2A_1,A_2 使得 A1ϕ(x)<f(x)<A2ϕ(x)A_1 \phi(x)<f(x)<A_2\phi(x)

根据上面的定义，我们发现 o\mathcal{o} 隐含了 O\mathcal{O} 且比 O\mathcal{O} 更强，o\mathcal{o} 与 ≺\prec 等价

f(x)≍ϕ(x)f(x)\asymp \phi(x) 的意思是 f,ϕf,\phi 有相同的 magnitude(规模)

我们的定义是 f=O(ϕ)f=\mathcal{O}(\phi)，O(ϕ)\mathcal{O}(\phi)不是单独出现的，如果单独写出O(ϕ)\mathcal{O}(\phi)，它就表示f=O(ϕ)f=\mathcal{O}(\phi)

下面举几个例子：

当 n→∞n\rightarrow \infty 时

10x=O(x)，sin⁡x=O(1)，x=O(x2)10x=\mathcal{O}(x)，\sin{x}=\mathcal{O}(1)，x=\mathcal{O}(x^2)

x=o(x2)，sin⁡x=o(x)，x+1∼xx=\mathcal{o}(x^2)，\sin{x}=\mathcal{o}(x)，x+1\sim x

当 n→0n\rightarrow 0 时

x2=O(x)，x2=o(x)，sin⁡x∼x，1+x∼1x^2=\mathcal{O}(x)，x^2=\mathcal{o}(x)，\sin{x}\sim x，1+x\sim 1

注意等号并不总是对称的，比如 O(1)=o(1)\mathcal{O}(1)=\mathcal{o}(1) 是正确的，但是 o(1)=O(1)\mathcal{o}(1)=\mathcal{O}(1) 是错误的

f∼ϕf\sim \phi 等价于

f=ϕ+o(ϕ)f=\phi+\mathcal{o}(\phi)

在这种情况下我们称 f,ϕf,\phi 是 asymptotically equivalent(渐进相等)

假设 PP 表示正整数的一个属性（比如是否为质数），P(x)P(x) 表示小于 xx 的具有属性 PP 的正整数的个数，如果 P(x)∼x（x→∞）P(x)\sim x（x\rightarrow \infty），那么不具有属性 PP 的个数就是 o(x)\mathcal{o}(x)，那么我们说几乎所有数都具有属性 PP

我们将会看到 π(x)=o(x)\pi(x)=\mathcal{o}(x)，所以几乎所有数都是合数

7、The logairthmic function(对数函数)

有关素数分布方面的研究总是出现对数函数 log⁡x\log x

这里及下文中出现的 log⁡x\log x 都是以自然对数 ee 为底

所以我们需要重视对数函数以及 exponentials function(指数函数)

由于

ex=1+x+⋯+xnn!+⋯e^x=1+x+\cdots +\frac{x^n}{n!}+\cdots

所以我们得到结论

x−nex>x(n+1)!→∞（x→∞）x^{-n}e^x>\frac{x}{(n+1)!}\rightarrow\infty（x\rightarrow\infty）

所以 exe^x 趋近无穷的速度远高于 xx 的任意次幂

对应的 log⁡x\log{x} 趋近无穷的速度远低于 xx，确切的

log⁡xxδ→0，log⁡x=o(xδ)（δ>0）\frac{\log{x}}{x^\delta}\rightarrow 0，\log{x}=o(x^\delta)（\delta>0）

所以一个十分重要的函数

f(x)=xlog⁡xf(x)=\frac{x}{\log{x}}

增长速度比 xx 慢，却比 x1−δx^{1-\delta} 快

8、The prime number theorem(素数定理)

Theorem 6（素数定理）
不超过 xx 的素数个数与 xlog⁡x\frac{x}{\log{x}} 渐进相等
π(x)∼xlog⁡x\pi(x)\sim \frac{x}{\log{x}}

这个定理是素数分布的核心定理，我们将在第二十二章证明它

这个定理的证明相当困难，但是下面的定理的证明却要简单一些

Theorem 7（Tchebychef's Theorem）
函数 π(x),xlog⁡x\pi(x),\frac{x}{\log{x}} 规模相等
π(x)≍xlog⁡x\pi(x)\asymp \frac{x}{\log{x}}

Theorem 8
pn∼nlog⁡np_n\sim n\log n

我们考虑函数

y=xlog⁡xy=\frac{x}{\log{x}}

log⁡y=log⁡x−log⁡log⁡x\log{y}=\log{x}-\log{\log{x}}

log⁡log⁡x=o(x)\log{\log{x}}=o(x)

log⁡y∼log⁡x\log{y}\sim\log{x}

x=ylog⁡x∼ylog⁡yx=y\log{x}\sim y\log{y}

所以

π(pn)=n∼pnlogpn⇔pn∼nlog⁡n\pi(p_n)=n\sim\frac{p_n}{log{p_n}}\Leftrightarrow p_n\sim n\log{n}

故该定理和素数定理等价

类似的，定理 77 和下面的定理等价

Theorem 9
pn≍nlog⁡np_n\asymp n\log n

Notes

一个对 π(x)\pi(x) 的更为精确地逼近是 logarithmic integral(对数积分)

Li(x)=∫2xdtlog⁡tLi(x)=\int_{2}^{x}\frac{dt}{\log{t}}