哈代数论读书笔记(一)——素数(1)

1、Divisibility of integers(整除性)

如下的数

$$\cdots,-3,-2,-1,0,1,2,\cdots$$

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

如下的数

$$0,1,2,3,\cdots$$

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

如下的数

$$1,2,3,\cdots$$

称为 positive integers(正整数)

整数 $a$ 能被另一个整数 $b(b\neq 0)$ 整除,当且仅当存在一个整数 $c$ 使得

$$a=bc$$

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

以及 b is a divisor of a(b是a的因子),记作:

$$b\mid a$$

特别地,$b\mid 0$ 恒成立,但是 $0\mid 0$ 不成立

相反的,我们用

$$b\nmid a$$

来表示 $b\mid a$ 的反面,即 a不能被b整除b不是a的因子

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

$$b\mid a,c\mid b\rightarrow c\mid a$$

$$b\mid a\rightarrow bc\mid ac(c\neq 0)$$

$$c\mid a,c\mid b \rightarrow c\mid ma+nb$$


2、Prime numbers(质数)

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

对应的,大于 $1$ 且不是质数的数称为 composite(合数)

Theorem 1
每个正整数(除了$1$)都能分解为若干质数的乘积

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

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

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

$$n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}=\prod p_i^{a_i}$$

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


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

Theorem 2(算术基本定理)
$n$ 的标准分解式是唯一的

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

并且这个定理是下一个定理(Theorem 3)的推论

Theorem 3(Euclid’s First Theorem(欧几里得第一定理))
如果 $p$ 是质数,且$p\mid ab$,那么$p\mid a或p\mid b$

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

这个定理可以推广到:

$$p\mid abc\cdots l\rightarrow p\mid a或p\mid b或p\mid c\cdots或p\mid l$$

特别地,如果 $a,b,c,\cdots,l$ 都是质数,那么 $p$ 是 $a,b,c,\cdots,l$ 中的一个

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

假设

$$n=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}$$

由于 $p_i|q_1^{b_1}q_2^{b_2}\cdots q_j^{b_j}$,所以每一个 $p$ 都在 $q$ 中,同理,每一个 $q$ 都在 $p$ 中,故 $k=j$

且排序之后有 $p_i=q_i$

如果 $a_i>b_i$,两边同除以 $p_i^{b_i}$,得到

$$p_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}$$

这样的话,$p_i\mid Left$,$p_i\nmid Right$,两边不可能相等

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


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

质数序列是

$$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\times 3\times 5\cdots p$$

那么容易发现

$$q+2,q+3,q+4,\cdots,q+p$$

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

Theorem 5
对于任意的正整数 $N$,存在连续的 $N$ 个正整数都是合数

据此,我们还可以有下面的推测:

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

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


5、Some question(若干问题)

(1)是否存在一个简单的公式可以计算第 $n$ 个质数 $p_n$ 的值?

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

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

(2)是否存在一个简单的公式可以由 $p_{n-1}$ 得到 $p_n$ ?

(3)是否存在一条规则可以找到一个比 $p_n$ 大的质数

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

(4)在小于给定的 $x$ 之内,有多少个质数?

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

$$\pi(p_n)=n$$

所以 $\pi(n)$ 与 $p_n$ 互为 inverse function(反函数)

所以该问题与问题(1)等价


6、Some notations(若干符号)

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

$$\mathcal{O},\mathcal{o},\sim,\prec,\succ,\asymp$$

设 $\phi(x)$ 是取值为正的函数,$f(x)$ 是任一函数,当 $x\rightarrow x_0(或\pm\infty)$ 时

(1)$f(x)=\mathcal{O}(\phi(x))$:存在常数 $A$ 使得 $|f(x)|<A\phi(x)$

(2)$f(x)=\mathcal{o}(\phi(x))$:$\frac{f(x)}{\phi(x)}\rightarrow 0$

(3)$f(x)\sim \phi(x)$:$\frac{f(x)}{\phi(x)}\rightarrow 1$

(4)$f(x)\prec \phi(x)$:$\frac{f(x)}{\phi(x)}\rightarrow 0$

(5)$f(x)\succ \phi(x)$:$\frac{f(x)}{\phi(x)}\rightarrow \infty$

(6)$f(x)\asymp \phi(x)$:存在常数 $A_1,A_2$ 使得 $A_1 \phi(x)<f(x)<A_2\phi(x)$

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

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

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

下面举几个例子:

当 $n\rightarrow \infty$ 时

$$10x=\mathcal{O}(x),\sin{x}=\mathcal{O}(1),x=\mathcal{O}(x^2)$$

$$x=\mathcal{o}(x^2),\sin{x}=\mathcal{o}(x),x+1\sim x$$

当 $n\rightarrow 0$ 时

$$x^2=\mathcal{O}(x),x^2=\mathcal{o}(x),\sin{x}\sim x,1+x\sim 1$$

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

$f\sim \phi$ 等价于

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

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

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

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


7、The logairthmic function(对数函数)

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

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

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

由于

$$e^x=1+x+\cdots +\frac{x^n}{n!}+\cdots$$

所以我们得到结论

$$x^{-n}e^x>\frac{x}{(n+1)!}\rightarrow\infty(x\rightarrow\infty)$$

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

对应的 $\log{x}$ 趋近无穷的速度远低于 $x$,确切的

$$\frac{\log{x}}{x^\delta}\rightarrow 0,\log{x}=o(x^\delta)(\delta>0)$$

所以一个十分重要的函数

$$f(x)=\frac{x}{\log{x}}$$

增长速度比 $x$ 慢,却比 $x^{1-\delta}$ 快


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

Theorem 6(素数定理)
不超过 $x$ 的素数个数与 $\frac{x}{\log{x}}$ 渐进相等
$$\pi(x)\sim \frac{x}{\log{x}}$$

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

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

Theorem 7(Tchebychef’s Theorem)
函数 $\pi(x),\frac{x}{\log{x}}$ 规模相等
$$\pi(x)\asymp \frac{x}{\log{x}}$$

Theorem 8
$$p_n\sim n\log n$$

我们考虑函数

$$y=\frac{x}{\log{x}}$$

$$\log{y}=\log{x}-\log{\log{x}}$$

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

$$\log{y}\sim\log{x}$$

$$x=y\log{x}\sim y\log{y}$$

所以

$$\pi(p_n)=n\sim\frac{p_n}{log{p_n}}\Leftrightarrow p_n\sim n\log{n}$$

故该定理和素数定理等价

类似的,定理 $7$ 和下面的定理等价

Theorem 9
$$p_n\asymp n\log n$$


Notes

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

$$Li(x)=\int_{2}^{x}\frac{dt}{\log{t}}$$

此条目发表在数学, 数论分类目录。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注