素数问题是数论中描述最简单却是棘手的问题, 历代数学家都在素数上耗费了大量精力, 得到了一些令人惊叹的结论, 但素数中仍存在这许多谜题…
我们研究的素数, 一般是指正整数中的一类数.
素数
一个正整数$p$称为素数, 如果
- $p>1$
- $p$仅有$1$和$p$两个约数
不将”$1$”视作素数是因为我们不希望自找麻烦. 如果”1”视作素数, 我们仍然可以进行数论研究, 但是你会经常发现叙述中需要加入”除了$1$之外的$\cdots$”.
定理1
除了1以外的每个正整数都是素数的乘积.
证明: 哈代采用归纳法证明, 首先这个定理对素数肯定成立, 因此只需要证明合数也满足这个定理.
对于合数$m$, 可以将其所有非$1$约数列出, 其中最小的那个$p$肯定是素数. 将$m$表示成$m=p\cdot m_1$. 如果$m_1$是合数则重复以上步骤. 仅需要有限步的以上步骤即可将$m$表示成素数的乘积.
标准型
将任意数$m$写成素数乘积的形式, 称为$m$的标准型, 如
$$
m=p_1p_2\cdots p_n
$$
其中$p_1,p_2,\cdots,p_n$是素数.
通过算法证明
证明某个东西$a$存在性的时候, 完全可以通过算法来进行, 主要有两种方式
- 构造一个能够找出$a$的算法.
- 构造一个概率算法, 算法能够以大于$0$的概率找出$a$.
定理2 算术基本定理
任何大于$1$正整数其标准型是唯一的, 即它能且仅能写成一种一些列素数的乘积.
定理3 Euclid第一定理
如果$p$是素数, 且$p\mid ab$, 那么$p\mid a$或$p\mid b$.
根据定理3可以证明定理2, 定理3的证明将在之后给出.
定理4 Euclid第二定理
素数有无限多个.
证明方法实在太多, 最简单的还是反证法, 请自行复习.
定理5 对任意给定的正整数$N$, 都存在连续的$N$个自然数均为合数.
证明方法: 构造出来一个满足条件的序列即可.
提示: 如果$N$个连续自然数都依次能被另一组$N$个连续自然数整除, 那么对于前面的数有什么要求呢?
! 反民科警告
不要看着素数的简单简单就去毫无准备地研究它的性质. 目前研究数论基本是用分析学的方法和代数学的方法, 衍生出的两个学科是代数数论和分析数论, 要学习他们都不是简单的事情. 要想研究, 先学好基础知识, 如果真的那么简单, 那么早就被历代数学家研究出来了. 在希望被像科学家一样被尊重之前, 想想你相比科学家付出了多少, 学习了多少?
定理6 素数定理
不超过$x$的素数个数渐进于$\frac{x}{\ln x}$, 即$\pi(x)\sim \frac{x}{\ln x}$.
注意$\pi(x)$是一个函数, 表示不超过$x$的素数的个数. 而$\sim$表示二者是等价无穷大, 这个和$\Theta(\cdot)$还是有一定的区别. 前者表示是等价, 而后者仅表示同阶. 现在用上述记号表示一个较定理6较弱的版本.
定理7 Tchebychef定理
$$
\pi(x)\sim\frac{x}{\ln x}
$$
这个定理比定理6的证明简单很多. 两个定理的证明都将在之后的章节给出.
现在我们不满足于定理4, 而是要给第$n$个素数$p_n$估一个上下界.
根据欧几里得对定理4的证明有,
$$
p_{n+1}\leq p_1p_2\cdots p_n+1
$$
因此
$$
p_{n+1}\leq 2^{2+4+\cdots+2^n}+1<2^{2^n}+1
$$
请自己根据上述推导证明下面的定理
定理8
$$
\pi(x)\geq \ln\ln x
$$
现在证明存在无限多个Blum素数
定理9
存在无穷多个形如$4m+3$的素数.
证明: 设
$$
q_n=2^2\times 3\times 5\times\cdots\times p_n-1
$$
那么$q_n$就是形如$4m+3$的数. 由于它不能被任何一个不超过$p$的素数整除, 且也不可能被表示为一些形如$4m+1$的素数的乘积, 因此它必定有一个因子是形如$4m+3$的素数. 通过这种方式可以确定一个$p_n<r_n\leq q_n$的形如$4m+1$的素数$r_n$.
定理10
如果$a$和$b$互素, 则$a^+b^2$的任何奇素因子都必定形如$4n+1$.
这个定理的证明将在之后的章节完成.
定理11 Dirichlet定理
如果$a$是一个正整数, 且$a$和$b$互素, 则存在无穷多个形如$an+b$素数存在.
该定理的证明过于复杂, 不适合放在本书中证明.
Fermat数
形如
$$
F_n=2^{2^n}+1
$$
的数称为Fermat数.
定理12
任何两个Fermat素数都互素.
证明: 用反证法构造证明即可.
下面一个经典结论请自行证明.
定理13
如果$a\geq 2$且$a^n+1$是素数, 那么$a$必为偶数且$n=2^m$.
由于数学家根据一个数是素数的概率进行猜想, 认为Fermat素数的个数为有限个, 因此如果猜想成立, 那么形如$2^n+1$的素数也为有限个.
定理14
如果$n>1$且$a^n-1$是素数, 那么$a=2$且$n为素数$.
如果$a$为合数显然由于$(a-1)\mid (a^n-1)$, $a^n-1$就不是素数. 这个定理我们暂时不证明, 将在后面进行讨论.
下面展示书上给出的Euclid定理的一种证明.
设$2,3,\cdots,p_j$是第$j$个素数. 令$N(x)$是不超过$x$且不被任何素数$p>p_j$整除的数$n$的个数. 则可以将这样的数$n$表示为
$$
n=q^2m
$$
其中, $m$没有任何平方因子, 即它不能被任何素数的平方整除, 这样就有
$$
m=2^{b_1}3^{b_2}\cdots p_j^{b_j}
$$
其中每个$b_i$的值都是$0$或$1$, 则$m$有$2^j$种不同的取值. 此外, $q\leq \sqrt n\leq \sqrt x$, 因此$q$有至多$\sqrt x$个值. 故有
$$
N(x)\leq2^j\sqrt x
$$
如果素数的个数有限, 设共有$j$个素数$2,3,\cdots,p_j$, 则对于每个$x$有$N(x)=x$, 即
$$
x\leq 2^j\sqrt x,\quad x\leq 2^{2^j}
$$
则显然对于$x> 2^{2^j}$是错误的.
该证明的方法可以用于证明一个重要的结论,
定理15
级数
$$
\sum\frac1p=\frac12+\frac13+\frac15+\frac17+\cdots
$$
是发散的.
证明: 要搞懂这个定理的证明, 首要任务就是搞懂$x-N(x)$是什么意思, 根据定义, 它表示的是”$n\leq x$且能被$p_{j+1},p_{j+2},\cdots$中至少一个数整除的数$n$的个数”.
假设级数收敛, 则选取第$j$项使得第$j$项之后的项和小于$1/2$, 即
$$
\frac 1{p_{j+1}}+\frac 1{p_{j+2}}+\cdots<\frac12
$$
满足$n\leq x$且能被$p$整除的数$n$的个数至多有$x/p$个, 因此$x-N(x)$不多于
$$
\frac x{p_{j+1}}+\frac x{p_{j+2}}+\cdots<\frac12 x
$$
因此有
$$
\frac 12 x<N(x)\leq 2^j\sqrt x, \quad x<2^{2j+2}
$$
选取$x\geq 2^{2^j+2}$即是错误的. 证毕.
定理16
$$
\pi(x)\geq \frac{\ln x}{2\ln2}
$$
证明: 选取$j=\pi(x)$和$p_j+1>x$再套用结论$x=N(x)\leq2^j\sqrt x$即可.
接下来介绍数模, 个人认为这是欧几里得算法的最佳引入方式. 注意这里有时会翻译成”模”, 个人认为”模”应该用作”modulo”的翻译, 而modulus应该翻译成”数模”. 我们只关心整数模. 原书上讨论的是数模, 但是我认为数模不方便给出最小数的直观概念.
整数模
设$S\subseteq \mathbb Z$, $S$称为整数模如果对于任意$m,n\in S$有$(m\pm n)\in S$.
当然, 也有零数模(null modulus), 它仅包含一个数$0$.
定理17
除零数模以为外, 任何整数模都是某个正整数$d$的整倍数组成的集合.
我们跳过最小公约数的介绍部分, 但是应当知道, 讨论最小公约数时, 一般是对正数进行讨论.
定理18
模$ax+by$是由$d=\gcd(a,b)$的所有整数倍数组成.
根据定理18显然有,
推论2
方程$ax+by=n$有整数解$x,y$, 当且仅当$\gcd(a,b)\mid n$.
现在可以来证明定理3)了.
引理1
设$p\mid ab$, 且$p\nmid a$, 则$p\mid b$.
证明: 由于$p\nmid a$, 则$\gcd(a,p)=1$即存在$x,y$使得$xa+yp=1$, 也就是
$$
xab+ypb=b
$$
显然左边被$p$整除, 因此右边也被$p$整除.
习题
- 证明: 存在无穷多个形如$6m+5$的素数.
- 利用定理10仿照定理9的证明方式结论证明: 存在无穷多个形如$8m+5$的素数.