漫谈初等数论、素数及其它（上篇）

目录

• 前言
• 素数与其无限性：欧几里得定理
• 素数分解的存在性与唯一性：算术基本定理、欧几里得引理
• 算术基本定理的部分应用
• 素数出现规律的估计：素数定理
• 素数的一些有意思的特征
• 未完待续
  • 各种素性检验算法
  • 素数的用武之地：公钥密码学
  • 尚未被证明的关于素数的猜想

前言

初等数论（elementary number theory）是数论（也是数学）的最古老的分支，它用朴素的方法研究数的规律，特别是整数的相关性质。初等数论的核心是整除理论和同余理论，而整除理论和同余理论的核心就是本篇的主角——素数。

素数与其无限性：欧几里得定理

素数（prime number），又称质数，指大于1的自然数中，除了1与该数自身外，无法被其他数整除的数，即它只有1和它本身两个正因数。

相对地，如果一个大于1的自然数不是素数，则称为合数（composite number）。

人类对素数的认识有着非常悠久的历史。欧几里得在《几何原本》（公元前300年左右）中，提出了关于素数的第一个基本定理，即数论中的欧几里得定理（Euclid's theorem）：

素数有无限多个。

这不是废话吗？（逃

该定理有非常多种证明方法，欧几里得自己的经典证明方法简述如下。

取一个任意素数组成的有限集S=(p₁, p₂, ..., p_n)。

令p = p₁ · p₂ · ... · p_n，q = p + 1，那么q是素数或者合数。分两种情况讨论：

• q是素数，但是q∉S。
• q是合数，那么就存在一个质因数ρ整除q。若ρ∈S，则ρ必然整除p。也就是说，ρ同时整除p和q = p + 1，那么ρ应该整除q - p = (p + 1) - p = 1。但事实是没有素数能整除1，即在ρ整除q的前提下，不存在ρ整除p，因此ρ∉S。

综上所述，对任意有限素数集S，总有一个素数不在S中，即存在无限多个素数。定理得证。

素数的定义与欧几里得定理都是如此简单而优雅。下面来看确立了素数核心地位的重要定理——算术基本定理。

素数分解的存在性与唯一性：算术基本定理、欧几里得引理

算术基本定理（fundamental theorem of arithmetic）又称为正整数的唯一分解定理（unique factorization theorem），其内容为：

对于任何大于1的自然数：

• 要么本身是素数。
• 要么可以唯一分解成2个或多个素数的乘积——即将这些素因数按大小排列，仅有一种排列方式。或者如果不考虑它们的大小次序，就仅有一种分解方式。

用现代的说法陈述之：

N = p₁^α₁ · p₂^α₂ · ... · p_k^α_k［其中p₁ < p₂ < ... < p_k均为素数，各个指数α_i > 0］称为自然数N > 1的标准分解式。自然数N的标准分解式是存在且唯一的。

由算术基本定理可以看出，素数是一切自然数的基本元素（怪不得叫“素”数呢）。也就是说，所有对自然数的研究，都可以通过唯一分解最终转化为对素数的研究。

欧几里得虽然并未给出算术基本定理的标准化定义（因为在古代没有幂运算），但他还是在《几何原本》中给出了证明过程。该证明过程是反证法（proof by contradiction）的经典案例，详述如下。

首先需要证明存在性（existence）。

假设存在大于1的自然数不能分解成素数的乘积，将最小的这个数记为n，n只可能是素数或者合数。

• 若n是素数，但素数可以分解成自身的乘积（即p = p），产生矛盾，所以n只能是合数。
• n是合数就意味着它可以分解成两个整数乘积a · b的形式［注意1 < a, b < n］。按照此前的定义，n是大于1的自然数中不能分解成素数乘积的最小的数，因此a和b都可以分解成素数的乘积，从而n也可以分解成素数的乘积，产生矛盾。

综上所述，标准分解式的存在性得证。

然后需要证明唯一性（uniqueness）。

在证明之前，先引入欧几里得引理（Euclid's lemma）：

如果一个素数整除两个正整数的乘积，那么这个素数可以至少整除这两个正整数中的一个。即：如果素数p|ab，那么p|a或p|b成立。

欧几里得引理可以通过裴蜀定理（Bézout's theorem）证明，此处略去。唯一性的证明思路如下。

假设存在大于1的自然数可以用多种方式分解成素数的乘积，将最小的这个数记为n，显然n是个合数。用两种方式表示n：
n = p₁ · p₂ · ... · p_k = q₁ · q₂ · ... · q_m［其中各p_i、q_i均为素数］

根据欧几里得引理，p₁|q₁ · q₂ · ... · q_m，所以各q_i中有一个能被p₁整除，不妨设为q₁。但q₁也是个质数，所以只可能有p₁ = q₁。

所以，比n小的自然数n' = p₂ · p₃ · ... · p_k也可以分解成n' = q₂ · q₃ · ... · q_m，与n的最小性产生矛盾。标准分解式的唯一性得证。

算术基本定理将1排除在了素数之外。因为如果1是素数，上述唯一性就被破坏了（例如，21可以分解成3 · 7、1 · 3 · 7、1 · 1 · 3 · 7...）。

算术基本定理的部分应用

• 算术基本定理可以用来证明前文讲过的欧几里得定理，如欧拉、埃尔德什的证明方法。

• 推论：
  如果正整数N的标准分解式为N = p₁^α₁ · p₂^α₂ · ... · p_k^α_k ，那么N的正因数个数为：

σ(N) = ∏_i=1^k (1 + α_i)

而其全体正因数之和为：

Σ(N) = ∏_i=1^k [ (p_i^α_i+1 - 1) / (p_i - 1) ]

• 利用算术基本定理还能定义正整数A、B的最大公约数（GCD）和最小公倍数（LCM）。如果A的标准分解式为A = p₁^α₁ · p₂^α₂ · ... · p_k^α_k，B的标准分解式为B = p₁^β₁ · p₂^β₂ · ... · p_k^β_k，那么就有：

gcd(A, B) = p₁^{min(α₁, β₁)} · p₂^{min(α₂, β₂)} · ... · p_k^{min(α_k, β_k)}
lcm(A, B) = p₁^{max(α₁, β₁)} · p₂^{max(α₂, β₂)} · ... · p_k^{max(α_k, β_k)}

素数个数规律的估计：素数定理

长久以来，素数的出现规律一直困扰着数学家。单独地看，素数在正整数中的分布似乎无迹可寻。但是从总体看，仍然可以近似估计出一些规律。

定义素数计数函数（prime counting function）π(x)，它表示小于等于某个实数x的素数的个数。例如，π(10) = 4，因为小于等于10的素数有2、3、5、7四个。

高斯和勒让德在18世纪末分别提出了如下猜想：

lim_x→∞ π(x) / [x / ln x] = 1

该猜想在1896年被阿达马等人用很复杂的复变函数理论证明，称为素数定理（prime number theorum），也叫素数的渐近分布法则（the asymptotic law of distribution of prime numbers）。

用大白话来讲，当x很大的时候，π(x)差不多等于x / ln x，即π(x)和x / ln x的相对误差趋近于0。再换另一种不太严谨的说法：从不大于n的正整数中随机抽选一个数，它是素数的概率大约是1 / ln n。

素数定理的更精确的估计是：

其中Li(n)是对数积分。下图示出素数定理的两种表述随着n值增大的相对误差变化趋势，可见第二种估计的相对误差会更快地收敛到0。

素数的一些有意思的特征

以下是素数的其它一些不能被称为“定理”的有趣特征，有些是显而易见的，有些则需要思考一下。证明过程就略去了。

• 所有大于10的素数的个位数只可能是1、3、7、9。
• 所有大于2的素数都可以唯一地表示为两个平方数之差，即p = a² - b²。
• 若n为大于等于2的正整数，那么在n到n!之间至少有一个素数。
• 若n为正整数，那么在n²到(n + 1)²之间至少有一个素数。
• 若n为大于等于2的正整数，那么在2ⁿ - 1和2ⁿ + 1两个数中，如果其中一个为素数，那么另一个必为合数。
• 存在任意长的一段连续正整数，其中的所有数都是合数。
• 若素数p为小于等于n的最大素数，那么p > n / 2。

未完待续

本篇主要从理论的角度探索了初等数论中与素数相关的基础知识。接下来的内容会更具实用性，列出大纲如下：

• 如何判断素数：各种素性检验算法
  • 确定性算法
    • 试除法
    • 埃拉托斯特尼筛法
    • 欧拉筛法（线性筛法）
  • 随机性算法
    • 费马小定理与费马素性检验
    • 米勒-拉宾素性检验
• 素数的用武之地：公钥密码学与公钥加密算法
  • 和女朋友相遇的契机RSA算法
  • 如何选择安全的大素数
• 尚未被证明的关于素数的猜想

明天早起搬砖，民那晚安晚安。