1. 无穷多的素数
让我们列出一些常见的素数：
\[2，3，5，7，9，11，13，17，19，23...\]首先我们可以发现：
当然，更重要的事实是在最后的省略号。
我们有无穷多个素数吗？
1.1 无穷多的素数
对于这一个问题，答案自然是肯定的。早在2000多年前，它就被欧几里得解决了：
$\quad$欧几里得证明：
假设有有限个素数，那我们必然可以按从小到大的顺序将他们排列：
\[p_1,p_2,p_3,...,p_r\]接着我们构造一个数$A=p_1p_2p_3…p_r+1$
如果$A$本身是素数，那么证明完成。如果$A$不是素数，那其必然会被现有的某个素数整除，这表明某个$p_i\in{p_1,p_2,p_3,…,p_r}$有$p_i\mid p_1p_2p_3…p_r+1$
即$p_i\mid 1$，矛盾，
1.2 模4余3的无穷素数
从2之后，所有的素数都是奇数了。它们模4均余1或3。那么这类型的素数是无穷多吗？
就目前的工具来说，我们可以证明模4余3的素数是无穷的。
假设其有限，则可以排成一张表：
\[3，p_1,p_2,p_3,...,p_r\]按照同样的方法构造$A=4p_1p_2p_3…p_r+3$
显然，$A$是模4余3的。我们知道，它是可以分解成若干个素数之积的：
\[A=q_1q_2...q_s\]首先，其中必然有奇数个模4余3类型的素数。因为模4余1类型的数乘起来还是模4余1；而两个模4余3的数乘起来，会得到模4余1的结果。综上，必然有奇数个模4余3类型的素数。
其次，这些模4余3的素数必然不在表${3，p_1,p_2,p_3,…,p_r}$，原因和之前的证明是一致的。
尽管我们现在缺少证明模4余1素数无穷的工具，但是我们可以直接给出终极定理：
- 算术级数的素数迪利克雷定理：设$a，m$是整数，若$\gcd(a,m)=1$。则存在无穷多个素数模$m$余$a$。
由于该定理的证明使用了微积分中的高级方法，所以不给出证明。
1.3 素数计数
尽管知道了素数有无穷多，但是我们仍然不满意。我们希望找到一个计数函数，他和素数的数量是同阶无穷大。这条路的一个里程碑式结果是：
- 素数定理：定义$\pi(x)={p\mid p\le x}$，也就是所有小于数$x$的素数个数。我们有如下结论：
这一结论是如此的漂亮，但是其证明过程却十分漫长。
1.3.1 两个有用的引理
- 引理1：令$T(x) = \prod_{p\le x, p\text{ prime}} p$，则对任意正整数$n$，$T(n)\le 4^n$。
证明：
证明的思路基于归纳法：
\[T(x) = \prod_{p\le x, p\text{ prime}} p = \left(\prod_{p\le x/2, p\text{ prime}}p\right)\left(\prod_{x/2 < p\le x, p\text{ prime}}p\right) \le \binom{x}{\frac{x}{2}} T\left(\frac{x}{2}\right)\]$m=2$成立，假设$m$成立，考虑$m+1$的情况。
当$2\mid m+1$时，其为偶数，不在累积范围内：
\[T(m+1) = T(m) \le 4^{m} < 4^{m+1}\]当$2\nmid m+1$，令$m+1=2t+1$。则有：
\[\prod_{t+1<p\le 2t+1,p\text{ prime}}p \le \frac{(2t+1)!}{(t+1)!t!} = \binom{2t+1}{t} \le \frac{2^{2t+1}}{2}\]左侧一个不等号，我们考察不等号左右侧的素数分解。左侧全是$t+1\sim 2t+1$之间的素数乘积，而右侧除了这些乘积，还有一些除法留得的商在。 右侧一个不等号，是对二项式定理的极大值估计。考虑式子$(1+1)^{2k+1}$，取其值的一半要比其中两个极大值要大。
最终有：
\[T(n) = \left(\prod_{p\le t+1, p \text{ prime}}p\right) \cdot \left(\prod_{t+1<p\le 2t+1,p\text{ prime}}p\right) \le T(t+1)\cdot \frac{1}{2}\cdot 2^{2k+1}\qquad\\ \le 4^{k+1}\cdot 2^{2k} = s^{2k+2}= 4^n\]还有另外一个小引理，是关于高斯取整函数的。
设$x\in \mathbb{R}$，定义
\([x] \text{ （或$ \lfloor x\rfloor $）}:= \max \{n|n\le x,n\in \mathbb{Z}\}\) \(\lceil x\rceil := \min \{n|n\ge x,n\in \mathbb{Z}\}\) \(\{x\}:=x-[x]\text{ （小数部分）}\)
有一个比较有用的性质：$ [x]+[y]\le[x+y]\le[x]+[y]+1 $
1.3.2 Bertrand-Chebyshev定理
- 定理内容：$\forall x>1$，存在素数$p\in[x,2x)$
证明：
首先，我们考察一般整数阶乘的素因子分解。
对于一整数$m$，对其阶乘的素因子分解有：
\[m!=p_1^{\alpha_1}p_2^{\alpha_2}...p_r^{\alpha_r}，\alpha_i\in\mathbb{N}\]定义每个素因子的指数为：$\alpha_p(m):=max{s:p^s\mid m!}$
对于$m\times (m-1)…\times2\times1$的素因子$p$，每隔$p$个数字，就有一个数字以$p$为因子；每隔$p^2$个数字，就有一个数字以$p^2$为因子。类似于模算术那篇文章中对欧拉函数的探究。
把这些因子都乘起来，得到的幂和就是最后的$\alpha_p$:
\[\alpha_p(n)=\left[\frac{n}{p}\right]+\left[\frac{n}{p^2}\right]+\left[\frac{n}{p^3}\right]+\cdots=\sum_{k\ge1}\left[\frac{n}{p^k}\right]\]考虑: \(\binom{2n}{n}= \frac{(2n)!}{n!n!}=\prod_{p\le2n,p\text{ prime}}p^{\alpha_p(2n)-2\alpha_p(n)}\)
我们利用反证法，假设$\exists n$，区间$ [n,2n]$中不存在素数。
则有 \({2n\choose n} = \frac{(2n)!}{n!n!}=\prod_{p\le n,p\text{ prime}}p^{\alpha_p(2n)-2\alpha_p(n)}\)
我们考虑把连乘式拆分成三部分，分别放缩（无特殊说明，$p$均为素数）：
\[\prod_{p\le n}p^{\alpha_p(2n)-2\alpha_p(n)} = \left(\prod_{p\le \sqrt{2n}}p^{\alpha_p(2n)-2\alpha_p(n)}\right) \cdot\left(\prod_{\sqrt{2n}< p\le \frac{2}{3}n}p^{\alpha_p(2n)-2\alpha_p(n)}\right)\\ \cdot\left(\prod_{\frac{2}{3}n<p\le n,}p^{\alpha_p(2n)-2\alpha_p(n)}\right)\]先放缩：
\[\prod_{\frac{2}{3}n<p\le n}p^{\alpha_p(2n)-2\alpha_p(n)}\]只需要当$n\ge4.5$时，$p^2\ge \frac{4}{9}n^2\ge 2n$。于是$\left[\frac{2n}{p}\right]$和$\left[\frac{n}{p}\right]$之后的项全部变成了0。
得到：$ p^{\alpha_p(2n)-2\alpha_p(n)}=p^{\left[\frac{2n}{p}\right]-2\left[\frac{n}{p}\right]}=p^0=1$
于是
\[\prod_{\frac{2}{3}n<p\le n}p^{\alpha_p(2n)-2\alpha_p(n)}=1\]再放缩：
\[\prod_{\sqrt{2n}< p\le \frac{2}{3}n}p^{\alpha_p(2n)-2\alpha_p(n)}\]由于$\sqrt{2n}< p$得到$p^2>2n$。与之前相同得到：$\alpha_p(2n)-2\alpha_p(n)=\left[\frac{2n}{p}\right]-2\left[\frac{n}{p}\right]$
由另一侧$p\le\frac{2n}{3}$，得到$\frac{2n}{p}\le3,\frac{n}{p}\le1$。最终得到：
\[\prod_{\sqrt{2n}< p\le \frac{2}{3}n}p^{\alpha_p(2n)-2\alpha_p(n)}\le \prod_{\sqrt{2n}< p\le \frac{2}{3}n}p^{1}\le 4^{\frac{2n}{3}}\]最后一个不等号基于引理1.
最后讨论：
\[\prod_{p\le \sqrt{2n}}p^{\alpha_p(2n)-2\alpha_p(n)}\]当$p\le \sqrt{2n}$时，有
\[\alpha_p(2n)-2\alpha_p(n) =\sum_{k\ge1}\left[\frac{2n}{p^k}\right]-2\sum_{k\ge1}\left[\frac{n}{p^k}\right] \\ =\sum_{k\ge1}\left(\left[\frac{2n}{p^k}\right]-2\left[\frac{n}{p^k}\right]\right) \\ =\sum_{k=1}^{[\log_p2n]}\left(\left[\frac{2n}{p^k}\right]-2\left[\frac{n}{p^k}\right]\right)\]由于$ [2x]\le2[x]+1,\forall x\in\mathbb{R} $，我们有 \(\left[\frac{2n}{p^k}\right]-2\left[\frac{n}{p^k}\right]\le1\)
所以
\[\alpha_p(2n)-2\alpha_p(n) \le [\log_p2n]\]所以
\[p^{\alpha_p(2n)-2\alpha_p(n)} \le p^{[\log_p2n]} \le 2n\]所以
\[\prod_{p\le \sqrt{2n}}p^{\alpha_p(2n)-2\alpha_p(n)}\le \prod_{p\le\sqrt{2n}}(2n)\le(2n)^{\sqrt{2n}} = 2^{\sqrt{2n}\log_22n}\]对三部分的分析完毕，接下来我们估计下界，最后导出下界大于上界，由此推出矛盾。
由于$ {2n\choose n} $是$ {2n\choose k} $中最大的，且$ \sum_{k=0}^{2n}{2n\choose k} = 2^{2n} $，所以有
\[{2n\choose n}>\frac{2^{2n}}{2n+1}=\frac{4^n}{2n+1}\]最后有不等式;
\[{2n\choose n}=\prod_{p\le n}p^{\alpha_p(2n)-2\alpha_p(n)}\le 2^{\sqrt{2n}\log_2(2n)}\cdot 2^{\frac{4n}{3}} \cdot 1<\binom{2n}{n}\]1.3.3 弱化版本的素数定理的证明
- 素数定理：定义$\pi(x)=#{素数p\mid p\le x}$，也就是所有小于数$x$的素数个数。我们有如下结论： \(\pi(x)\sim \frac{x}{\log_2 x}\)
证明：
即证明$n\ge 2$时$C_1\frac{n}{\log_2n}\le\pi(n)\le C_2\frac{n}{\log_2n}$。
先证明上界：
有：
\[(\sqrt{n})^{\pi(n)-\pi(\sqrt{n})}\le \prod_{\sqrt{n}\le p\le n}p\le \prod_{ p\le n}p \le 4^n\]对两侧取对数得到：
\[\pi(n)\le\pi(\sqrt{n})+ \frac{4n}{\log_2n}\]累加得到：
\[\pi(n)\le \frac{4}{\log_2n}\sum_{k=0}^{\log\log_2n}2^kn^{\frac{1}{2k}}\le C_2n\]再证明上界，类似地(运用到Bertrand定理的中间结果)：
\[(2n)^{\pi(2n)-\pi(n)}\ge\prod_{n\le p \le 2n}p=\frac{\binom{2n}{n}}{2^{\sqrt{2n}\log_2(2n)}\cdot 2^{\frac{4n}{3}} \cdot 1}\ge \frac{\frac{4^n}{2n+1}}{2^{\sqrt{2n}\log_2(2n)}2^{\frac{4n}{3}}}\ge 2^{\frac{n}{4}}\]同样取对数可得到最终结果。
这个定理只是给出了素数计数函数的一个同阶无穷大估计。而原来的素数定理给出的是一个等价无穷大的估计，此外素数计数函数还有另外一个等价无穷大估计：
\[\pi(x)\sim \int_2^x\frac{1}{\ln t}dt\]2. 梅森素数与完全数
这一节主要讨论形如$a^n-1$的素数，比如$7=2^3-1$
2.1 梅森素数
基于简单的分解：
\[a^n-1=(a-1)(a^{n-1}+...+a+1)\]由素数的定义，我们可以得到其为素数的一个必要条件：$a=2$.
遗憾的是，它不是充分的。比如$n=4$.
基于此，我们将$n$分解$n=mk$得到：
\[2^{mk}-1=(2^m-1)(2^{m(k-1)}+...+2^m+1)\]这表面当$n$为合数时，$2^n-1$必然为合数。考虑其逆否命题，则我们已经证明：
- 命题：对于整数$a\ge2,n\ge2$，$a^n-1$为素数，则$a=2$且$n$为素数。
对于梅森素数，尽管我们也找到过一些，比如：
\[2，3，5，7，13，17，19，31，61，89，107\]以及一些很大的梅森素数。
相关历史可以查询：历史
当然你也可以创造历史，加入GIMPS(大型因特网梅森素数搜索)：GIMPS
然而，对于数学来说。更感兴趣的问题是有没有无穷多的梅森素数？如果有，能不能给出计数函数？
2.2 完全数
这一小节讨论一类有意思的数，称为完全数。定义为其所有除本身之外的因数和等于自身(或者说所有因数和为自身的两倍。)
比如：
\[6 = 1+2+3\]我们能否对完全数给出一个描述呢？欧几里得又来了。
2.3 两个完全数定理
- 欧几里得完全数定理：若$2^p-1$为素数，则$2^{p-1}(2^p-1)$是完全数。
证明：
设$q=2^p-1$为素数，考察$2^{p-1}q$的真因数：
\[1,2,4,...,2^{p-1}\qquad q,2q,...,2^{p-2}q\]相加得到：
\[2^p-1+q(2^{p-1}-1)=2^{p-1}q\]既然给出了一定的描述。那么它是否完全呢？是否给出了所有完全数呢？
通过以下定理，至少可以确定欧几里得给出了所有偶完全数。
在此之前，我们先定义如下函数，它是一正整数的正因数之和：
\[\sigma(n)=\sum k,\qquad \forall k\in\mathbb{Z^+},k\mid n.\]比如$\sigma(6)=1+2+3+6=12$
对这个函数我们有如下性质：
- 对素数，$\sigma(p)=p+1$
- 对素数的$k$次方，$\sigma(p^k)=\frac{p^{k+1}-1}{p-1}$
- 对于合数$mn$，$\sigma(mn)=\sigma(m)\sigma(n)$
对于它们的证明并不复杂，只需要给出质因数分解即可。
- 欧拉完全数定理：如果$n$是偶完全数，那么其必为$2^{p-1}(2^p-1)$类型的数，其中$(2^p-1)$是梅森素数。
证明：
首先其为偶数，则有$n=2^km$，其中$m$为奇数。
由此得到等式1：
\[\sigma(n)=(2^{k+1}-1)\sigma(m)\]又知道其为完全数，得到等式2：
\[\sigma(n)=2n=2^{k+1}m\]综合得到：
\[2^{k+1}m=(2^{k+1}-1)\sigma(m)\]左侧$m$为奇数，右侧$2^{k+1}-1$为奇数。但是$\sigma(m)$奇偶性未知，于是存在整数$c$：
\[\sigma(m)=c \cdot 2^{k+1}\]同时得到：$m=(2^{k+1}-1)c$
若$c>1$，则$\sigma(m)\ge 1+c+m=1+c+(2^{k+1}-1)c=c \cdot 2^{k+1}+1>\sigma(m)$
矛盾，从而只有$c=1$。得到$\sigma(m)=m+1$，这说明$m=2^{k+1}-1$是素数。
由2.1的命题得到$k+1$为素数。令$p=k+1$，整理后即可完成本定理的证明。
尽管我们对于偶完全数得到了如此漂亮的结果。但是对于奇完全数，我们只能知道$10^300$内没有奇完全数。
3. 素性检测
(这一段和上一篇模算术的第四节一模一样)
对于大数字，用传统的方式去判别成为了一件十分困难的事情，比如：
\[m=113\ 736\ 947\ 625\ 310\ 405\ 231\ 177\ 973\ 028\ 344\ 375\ 862\ 964\ 001\]它实际上是两个相当大的素数的乘积，它们是：
\[40\ 103\ 836\ 670\ 582\ 470\ 495\ 139\ 653\cdot 2\ 836\ 061\ 511\ 010\ 998\ 317\]3.1 巧妙的费马小定理
对他们的计算十分繁复，但是将他们作为指数，就没有那么痛苦。根据前面所讲的逐次平方法，这种计算并没有那么困难。更何况，根据费马小定理，稍稍扩展一下就有(p是素数)：
\[a^p\equiv a(mod\ p)\]我们只需要用逆否命题巧妙的扭转一下，通过计算得到：
\[2^m\equiv 39\ 241\ 970\ 815\ 393\ 49\ 060\ 120\ 043\ 692\ 630\ 615\ 961\ 790\ 020(mod\ m)\]根据费马小定理的逆否命题，可以直接判定$m$不是素数。这个结论之强实在是平生罕见，你甚至都不需要进行任何的因数分解，就可以得到这个结论。
但是这离我们的目标还有一些差距。我们需要判定它是素数，而这个只能判断他不是素数。
退一步讲，即使条件：
\[a^p\equiv a(mod\ p)\]成立，我们也没有理由推断，$p$是素数。
比如说：
\[10^{15}=10(mod\ 15)\]但是我们知道15并不是素数。但15的确满足上式。(如果你把10换成2就可以得到15不是素数)
这时，你可以自信的说，对于$m$，我们可以选取$1\le a\le m$去一个个验证嘛。这个法子有一个显而易见的缺点，那就是计算量也挺大的。
但问题不出在这儿。而是一类极具迷惑性的数字。这个现象首先由卡米歇尔发现，满足上述条件的最小数字是$561=3·11·17$
3.2 恼人的卡米歇尔数
对于1到561间的任何整数，你都不能找到一个不符合$a^p\equiv a(mod\ p)$的整数。
类似还有：
\[1105=5·13·17\\ 1729=7·13·19\\ ...\]也许你会觉得它们都是三个素数的乘积，但是数学嘛，不会总让你舒服。
\[62745=3·5·47·89\]接下来我们直接给出卡米歇尔数的两个性质并证明。
- 肯定是个奇数
- 每个卡米歇尔数都是不同素数的乘积
1：取$a=m-1\equiv-1(mod\ m)$，有$a^m\equiv (-1)^m\equiv -1(mod\ m)$。这就保证了$m$必然为奇数。
2：假设$m$是卡米歇尔数，设$p$是整除$n$的素数。记$p^{e+1}$是整除$n$的最大幂方数。我们要证明$e$为0.
取$a=p^e$，则有$p^{ne}\equiv p^e(mod\ n)$。从而$n\mid (p^{ne}- p^e)$
又有$p^{e+1}\mid n$，则$p^{e+1}\mid (p^{ne}- p^e)$
这说明下面这个数是一个整数：
\[\frac{p^{ne}- p^e}{p^{e+1}}=\frac{p^{(n-1)e}-1}{p}\]它只能是$e=0$，因为有分解$p^{(n-1)e}-1=(p-1)(p^{(n-1)e-1}+…+p+1)$。
固然，这两个性质具有一些巧妙的应用，但是我们的目的是为了把这个卡米歇尔数给他杀了，免得它干扰我们挑一个可人的大素数。
于是我们给出卡米歇尔数的考塞特判别法：
- 设$n$是合数，则$n$是卡米歇尔数当且仅当它是奇数，且对于每个整除$n$的素数$p$都有
- $p^2\nmid n$
- $(p-1)\mid(n-1)$
这里我们不给出证明。
3.3 素性判断
卡米歇尔数的存在说明了，我们不能仅仅依靠式$a^m\equiv a(mod\ m)$来检验素数。所以我们给出一个对素数描述更加全面一些的性质。(仍然不是充分必要条件)
- 设$p$是奇素数，记$p-1=2^kq，q$是奇数。
- 设$a$是不被$p$整除的任何数，则下述两个条件之一成立：
- $a^q\equiv 1(mod\ p)$
- 数$a^q,a^{2q},a^{4q}…,a^{2^{k-1}q}$之一模$p$余$-1$.
由费马小定理，我们可以保证数表中的最后一个数字：
\[a^q,a^{2q},a^{4q}...,a^{2^{k-1}q}，a^{2^kq}\]模$p$必余1，进一步，表中每个数都是前一个数的平方，因此下述两种可能之一必成立：
- 表中第一个数模$p$必余1
- 表中某些数模$p$不余1，但它们平方后就是1，也就只能是-1了。
这就完成了对该性质的阐述。
综上，我们得到被称为拉宾-米勒测试的合数试验
- 合数的拉宾-米勒测试：假设$n$是奇素数，记$n-1=2^kq，q$是奇数。对不被$n$整除的某个$a$，如果下述两个条件都成立，则$n$是合数：
- $a^q \not\equiv 1(mod\ n)$
- 对所有$i=0,1,…,k-1，a^{2^iq}\not\equiv -1(mod\ n)$
乍一看，他和我们之前用式子$a^m\equiv a(mod\ m)$来检验素数没什么不同。事实上，目前采用拉宾-米勒测试的底气来源于一下两点：
- 每个合数都有许多$a$来证明它的合数性(这确保没有类似的”卡米歇尔数”来捣乱)
- 如果$n$是奇合数，则1到n-1之间至少有75%的数字可以用来证明$n$是个合数。
所以，当我们随机选取100个$a$来进行拉宾-米勒测试，如果它们均不能证明$n$是合数。那么$n$作为合数的可能性只有大概$0.25^{100}\approx 6\times 10^{-61}$。当然，你要是十分谨慎嗷，十分谨慎，不妨使用鸽笼原理取它个25%*n+1个数。