梅森素数

梅森素数 (Mersenne prime) 是人类目前已知的最大的一类素数. 它是指形如 `M_p = 2^p - 1` 的素数. 若 `p = a b`, 则 `2^(a b) - 1` 可以因式分解. 因此 `2^p - 1` 是素数的前提条件是 `p` 为一素数. 前几个梅森素数的 `p` 值是 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127... 晚年的 Euler 在双目失明的情况下通过心算验证 `M_31 = 2147483647` 为素数.

完全数 (perfect number) 是指满足方程 `sigma(n) = 2n` 的正整数. 其中 `sigma(n)` 表示 `n` 的所有正因子之和. 前几个完全数是 6, 28, 496, 8128, 33550336... 它们正好是偶数. 奇完全数是否存在仍是一个未解之谜.

梅森素数与偶完全数的一一对应 若 `M_p` 为梅森素数, 则 `M_p(M_p+1)//2` 是完全数. 反之, 偶完全数必然具有这种形式.

1. [古希腊, Euclid] 考虑 `2^(p-1) * (2^p-1)` 的全体正因子 `1, 2, cdots, 2^(p-1)`,
   `M_p, 2 M_p, cdots, 2^(p-1) M_p`. 求和即得结论.
2. [Leonhard Euler] 下证偶完全数必然形如 `M_p(M_p+1)//2`. 设这个偶完全数是 `2^a b`, 其中 `a` 是正整数, `b` 是奇数. 由于 `sigma` 是积性函数, 有 `2^(a+1) b` `= sigma(2^a b)` `= sigma(2^a) sigma(b)` `= (2^(a+1) - 1) sigma(b)`. 记 `n = a+1`, 则 `2^n b = (2^n - 1) sigma(b)`. 这指出 `2^n - 1` 整除 `b`, 且 `2^n` 整除 `sigma(b)`. 设 `sigma(b) = 2^n c` 则 `b = (2^n - 1) c`. 假如 `c gt 1`, 显然 `2^n - 1` 也大于 `1`, 则 `b` 至少有三个不同因子 `1, c, b`, 于是 `sigma(b) ge 1 + c + b` `= 1 + c + (2^n - 1) c` `= 1 + 2^n c` `= 1 + sigma(b)`, 矛盾. 因此 `c = 1`, 即 `b = 2^n - 1`, `sigma(b) = 2^n`. 这又推出 `b` 是素数.

设 `p` 为奇素数, 则 `2^p - 1` 的所有因子都形如 `2n p+1`, `n` 是正整数.

由于两个形如 `2n p + 1` 的数相乘, 结果仍为同一形式, 我们只需对素数作出证明. 令 `q` 是 `2^p - 1` 的素因子, 则 `q` 是奇素数. 由费马小定理, `q | 2^(q-1) - 1`. 利用公式 `gcd(2^a - 1, 2^b - 1) = 2^(gcd(a,b)) - 1`, 我们有 `2^(gcd(p, q-1)) - 1` `ge q gt 1`, 即 `gcd(p, q-1) gt 1`, 即 `p | q-1`. 又 `q-1` 是偶数, 所以存在正整数 `n` 使得 `q = 2n p + 1`.

Lucas-Lehmer 算法 用于验证 `M_p` 是否为梅森素数. 设 `p` 是素数, `M_p = 2^p - 1`. 令 `r_1 = 4`, `r_n = (r_(n-1)^2 - 2) mod M_p`, (取最小非负剩余) 则 `M_p` 是素数当且仅当 `r_(p-1) = 0`.

素数定理

关于素数分布的一个重要结论是素数定理: `pi(x) ~ "li"(x) ~ x/(ln x)`, `quad x to oo`. 其中 `pi(x)` 是 `x` 以内 (即 `le x`) 的素数个数, 而 `"li"(x) = int_0^x dt/(ln t)` `= lim_(epsi to 0^+) int_0^(1-epsi) + int_(1+epsi)^x`. 它的证明比较复杂, 我们只证较弱的结论 `pi(x) = Theta(x/(ln x))`. 换言之, `x` 充分大时, 存在正的常数 `c_1, c_2` 使 `c_1 x/(ln x) le pi(x) le c_2 x/(ln x)`. 此即著名的 Чебышев 不等式.

由素数定理推出 `p_n ~ n ln n`, `p_n` 是第 `n` 个素数.

[来自 zz] 由 `pi(x) ~ x/(ln x)` 取对数得 `ln pi(x) = ln x - ln ln x + o(1)`. 于是 `p_n/(n ln n)` `= p_n/(pi(p_n) ln pi(p_n)` `= (ln p_n)/(ln p_n - ln ln p_n + o(1))` `to 1`.

筛法

用 Eratosthenes 筛法求 100 以内的素数个数.

`sqrt 100 = 10`, 而 10 以内的素数为 2, 3, 5, 7. 对于 `10 lt n le 100`, 只要 `n` 与 2, 3, 5, 7 互素, 就能保证为素数. 而对于 `n le 10`, 只有 1 与 2, 3, 5, 7 互素. 换言之, 100 以内与 2, 3, 5, 7, 互素的整数个数为 `pi(100) - pi(10) + 1`. 记 `P = 2 * 3 * 5 * 7`, 称为一个筛子. `A = {1, cdots, 100}` 是待筛的整数. 定义筛函数为 `S(A, P) = sum_(a in A, (a,P) = 1) 1`, 表示通过了筛选的整数个数. 于是 `S(A, P) = pi(100) - pi(10) + 1`. 又记 `A_d` 为 `A` 中所有 `d` 的倍数, 则 `|A_d| = |__100/d__|`. 由容斥原理, `S(A, P)` `= |A| - |A_2| - |A_3| - |A_5| - |A_7|` `+ |A_(2*3)| + |A_(2*5)| + |A_(2*7)| + |A_(3*5)| + |A_(3*7)| + |A_(5*7)|` `- |A_(2*3*5)| - |A_(2*3*7)| - |A_(2*5*7)| - |A_(3*5*7)|` `+ |A_(2*3*5*7)|` `= 100 - 50 - 33 - 20 - 14 + 16 + 10 + 7 + 6 + 4 + 2` `- 3 - 2 - 1 - 0 + 0` `= 22`. 因此 `pi(100) = S(A, P) + pi(10) - 1 = 22 + 4 - 1 = 25`.

设 `A` 为有限个整数的集合, `A_d` 为 `A` 中所有 `d` 的倍数. 筛子 `P` 为一个正整数, 且 `P` 的所有素因子为 `p_1, cdots, p_s`. 那么 `S(A, P) := sum_(a in A, (a,P) = 1) 1` `= sum_(r=0)^s (-1)^r sum_(i_1 lt cdots lt i_r) |A_(p_(i_1) cdots p_(i_r))|`. 使用 Möbius 函数 `mu(n) = { 1, if n = 1; (-1)^r, if n = p_1 cdots p_r 为不同素数的乘积; 0, if n 含有平方因子 :}` 结论简记为 `S(A, P) = sum_(d | P) mu(d) |A_d|`. 特别当 `A = {1, cdots, n}`, `P = n` 时, 得到 Euler 函数的表达式 `varphi(n) = sum_(d | n) mu(d) n//d` `= n prod_(p | n) sum_(p^a | n) mu(p^a)//p^a` `= n prod_(p | n) (1 - 1//p)`.

利用公式 `sum_(d | P) mu(d) = { 1, if P = 1; 0, if P gt 1 :}` 有 `sum_(a in A, (a,P) = 1) 1` `= sum_(a in A) sum_(d | (a,P)) mu(d)` `= sum_(d | P) mu(d) sum_(a in A, d | a) 1` `= sum_(d | P) mu(d) |A_d|`.

Чебышев 不等式

Чебышев 不等式 记 `pi(x)` 是不超过 `x` 的素数个数, `p_n` 为第 `n` 个素数. 我们有 `color(#663)(1/3 ln 2)x/(ln x)` `lt pi(x)` `lt color(#663)(6 ln 2)x/(ln x)`, `quad AA x ge 2`
`color(#663)(1/(6 ln 2)) n ln n` `lt p_n` `lt color(#663)(8/(ln 2)) n ln n`, `quad AA n ge 2`.

为证明 `pi(x)` 的上下界, 我们从 `M = (2 m; m)` 的估计入手, `m` 为正整数.
1. 联系第一章 Kummer 定理的相关内容, 记 `v_p(n)` 为素数 `p` 在 `n` 中的次数, 有 `v_p(n!) = sum_(i ge 1) |__n/p^i__|`. 取对数有 `ln M` `= ln((2m)!) - 2 ln(m!)` `= sum_(p lt 2m) v_p((2m)!) ln p` `- 2 sum_(p le m) v_p(m!) ln p` `= sum_(p le m) [v_p((2m)!) - 2 v_p(m!)] ln p` `+ sum_(m lt p lt 2m) v_p((2m)!) ln p` `= A + B`.
2. 对 `y gt 0` 有 `0 le |__2y__| - 2|__y__| le 1`, 于是 `0 le (|__(2m)/p^i__| - 2|__m/p^i__|) le 1`, `quad i ge 1`. 上式求和得到 `A` 的系数的估计 `0 le v_p((2m)!) - 2 v_p(m!)` `le sum_(p^i | 2m) 1` `= |__ln(2m)/ln p__|`. 另一方面, `m lt p lt 2m` 时, 显然 `p` 在 `(2m)!` 中的次数为 `1`, 即 `B` 的系数 `v_p((2m)!) = 1`. 于是 `sum_(m lt p lt 2m) ln p` `le ln M` `le sum_(p lt 2m) |__ln(2m)/ln p__| ln p`. 因而 `(pi(2m)-pi(m)) ln m` `le ln M` `le pi(2m) ln(2m)`.
3. 通过直接估计 `M` 的上下界得到 `M = (2m)/m * (2m-1)/(m-1) cdots (m+1)/1 ge 2^m`;
   `M = (2m; m) lt (1+1)^(2m) = 2^(2m)`. 于是 `pi(2m) ln(2m) ge m ln 2`,
   `(pi(2m)-pi(m))ln m lt 2m ln 2`.
4. 当 `x ge 6` 时, 取 `m = |__x//2__| gt 2`, 此时成立 `2m lt x lt 3m`, 因此 `pi(x) ln x ge pi(2m) ln(2m)` `ge m ln 2` `gt x/3 ln 2`. 直接验算知上式对 `2 le x lt 6` 也成立; 这证明了不等式的左半部分.
5. 当 `m = 2^k` 时, `(pi(2^(k+1)) - pi(2^k)) k lt 2^(k+1)`, 又显然 `pi(2^(k+1)) le 2^k`, 两式相加得 `(k+1)pi(2^(k+1)) - k pi(2^k) lt 3 * 2^k`. 令 `k` 从 0 到 `h-1` 求和有 `h pi(2^h) lt 3 * 2^h`. 设 `2^(h-1) lt x le 2^h`, 则 `pi(x) le pi(2^h)` `lt 3 * 2^h//h` `lt 3 * (2 x)/(ln x//ln 2)` `= 6 ln 2 x/(ln x)`. 这证明了不等式的右半部分.

1. 从 `pi(x)` 的估计出发, 取 `p_n = x`, 得到 `n lt 6 ln 2 p_n/(ln p_n)`. 再由 `p_n gt n` 得 `p_n gt (n ln n)/(6 ln 2)`; 这证明了左半不等式.
2. `n = 2` 时直接验证右半不等式成立. 下设 `n ge 3`, 因此 `p_n` 为奇素数. 在不等式 `pi(2m) ln(2m) ge m ln 2` 中取 `2m = p_n + 1`, 得 `n ln(p_n+1) ge (p_n+1)/2 * ln 2`, `ln(p_n+1) le ln(2n//ln 2) + ln ln(p_n+1)`. 利用不等式 `ln(1+s) le s`, 取 `s = y//2 - 1` 有 `ln y le y//2 - 1 + ln 2 lt y//2`, `quad y gt 0`. 再令 `y = ln(p_n+1)`, 有 `ln ln(p_n+1) lt 1/2 ln(p_n+1)`. 由 得 `ln(p_n+1) le 2 ln(2n//ln 2) lt 4 ln n`, `quad n ge 3`. 再由 即完成右半不等式的证明.

Чебышев 函数 两个 Чебышев 函数定义为
1. `vartheta(x) = sum_(p le x) ln p`, 其中 `p` 为素数;
2. `psi(x) = sum_(p^a le x) ln p`, 其中 `p` 为素数, `a` 为正整数.
若定义 Mangoldt 函数为 `Lambda(n) = { ln p, if n = p^a; 0, "otherwise" :}`, 则 `psi(x) = sum_(n le x) Lambda(n)`.

Mangoldt 函数的和函数是对数函数: `sum_(d | n) Lambda(d) = ln n`.

设 `p` 在 `n` 中的次数为 `a_p`, 利用算术基本定理, 左边等于 `sum_(p^a | n) ln p` `= a_p sum_(p | n) ln p` `= ln(prod_(p | n) p^(a_p))` `= ln n`.

`x ge 1` 时, `sum_(n le x) psi(x // n) = ln(|__x__|!)`.

由定义, 左边等于 `sum_(n le x) sum_(k le x//n) Lambda(k)` `= sum_(n le x) sum_(n k le x) Lambda(k)` `==^(n k = m) sum_(m le x) sum_(n | m) Lambda(m/n)` `= sum_(m le x) ln m` 等于右边.

Чебышев 函数是 `pi(x)` 的良好替代, 事实上存在常数 `c_gamma gt 0` 使得
1. `(ln x - c_gamma) pi(x) lt vartheta(x) lt ln x pi(x)`;
2. `vartheta(x) le psi(x) le vartheta(x) + sqrt x ln x`.

以下三个命题等价:
1. 存在常数 `d_1, d_2 gt 0` 使得 `d_1 x // ln x lt pi(x) lt d_2 x // ln x`;
2. 存在常数 `d_3, d_4 gt 0` 使得 `d_3 x lt vartheta(x) lt d_4 x`;
3. 存在常数 `d_5, d_6 gt 0` 使得 `d_5 x lt psi(x) lt d_6 x`;
以下三个命题等价: `x to oo` 时
4. `pi(x) ~ x // ln x`;
5. `vartheta(x) ~ x`;
6. `psi(x) ~ x`.