Appearance
特殊数列的数论性质（Number Theoretic Sequences）
核心定位
特殊数列的数论性质是数论竞赛的高频考点，涵盖 $n^2 + 1$型素数、Mersenne 数$2^p - 1$、Fermat 数 $2^{2^n} + 1$、$k$-次幂和数列、$a^n - b^n$、阶乘与超阶乘等。这些数列与 整除与同余基础、组合数论：卢卡斯与库默尔、不定方程与丢番图方程 形成紧密网络，是高联二试、CMO、IMO 与 TST 中考查整除性、周期性、整解数等问题的核心工具。
一、$n^2 + 1$ 型数列
1.1 基本性质
$n^2 + 1$ 的素因子
$n^2 + 1$的所有奇素因子$p$都满足$p \equiv 1 \pmod 4$。
证明：$p \mid n^2 + 1 \Rightarrow n^2 \equiv -1 \pmod p \Rightarrow \left(\dfrac{-1}{p}\right) = 1 \Rightarrow p \equiv 1 \pmod 4$。
1.2 Bunyakovsky 猜想
Bunyakovsky 猜想（未证）
若 $f(x) \in \mathbb{Z}[x]$ 不可约、首项系数正、$\gcd(f(1), f(2), \ldots) = 1$，则 $f(n)$ 取无穷多个素数值。
特别地，$n^2 + 1$是否取无穷多素数未知。已知结果：Friedlander-Iwaniec（1998）证明$x^2 + y^4$ 取无穷多素数。
$n^2 + 1$ 的素数值
$n = 1, 2, 4, 6, 10, 14, 20, 26, 36, 40, \ldots$给$n^2 + 1 = 2, 5, 17, 37, 101, 197, 401, 677, 1297, 1601, \ldots$ 均为素数。
二、Mersenne 数 $M_p = 2^p - 1$
2.1 定义与基本性质
Mersenne 数
对素数 $p$，$M_p = 2^p - 1$称为 Mersenne 数。若$M_p$ 本身为素数，则称为 Mersenne 素数。
Mersenne 素数的必要条件
若 $M_p = 2^p - 1$为素数，则$p$ 必为素数。
证明：若 $p = ab$（$a, b > 1$），则 $2^p - 1 = 2^{ab} - 1 = (2^a)^b - 1 = (2^a - 1)(1 + 2^a + 2^{2a} + \cdots + 2^{(b-1)a})$，可分解。
反例：$p$素但$M_p$ 合
$p = 11$：$M_{11} = 2047 = 23 \times 89$。 $p = 23$：$M_{23} = 8388607 = 47 \times 178481$。
2.2 Lucas-Lehmer 检验
Lucas-Lehmer 检验
定义 $s_0 = 4$，$s_{n+1} = s_n^2 - 2$。则 $M_p$为素数当且仅当$s_{p-2} \equiv 0 \pmod{M_p}$。
检验 $M_7 = 127$
$s_0 = 4$ $s_1 = 16 - 2 = 14$ $s_2 = 196 - 2 = 194 \equiv 194 - 127 = 67 \pmod{127}$ $s_3 = 67^2 - 2 = 4489 - 2 = 4487$，$4487 = 127 \times 35 + 42$，$\equiv 42 \pmod{127}$ $s_4 = 42^2 - 2 = 1762 = 127 \times 13 + 111$，$\equiv 111 \pmod{127}$ $s_5 = 111^2 - 2 = 12319 = 127 \times 97 + 0$，$\equiv 0 \pmod{127}$ ✓
$p - 2 = 5$，$s_5 \equiv 0$，故 $127$ 是素数 ✓
2.3 已知 Mersenne 素数
至 2024 年共发现 51 个 Mersenne 素数。最大的是 $M_{82589933}$（2018 年发现），有约 $2486$ 万位十进制数字。
2.4 完全数与 Mersenne 素数
Euclid-Euler 完全数定理
偶数 $n$ 是完全数（$\sigma(n) = 2n$）$\iff$ $n = 2^{p-1} M_p$，其中 $M_p$ 为 Mersenne 素数。
完全数列表
- $p = 2$：$6 = 1 + 2 + 3$
- $p = 3$：$28 = 1 + 2 + 4 + 7 + 14$
- $p = 5$：$496$
- $p = 7$：$8128$
- $p = 13$：$33550336$
奇完全数猜想
是否存在奇完全数至今未决。已知若存在，则大于 $10^{1500}$，至少有 $9$ 个不同素因子。
三、Fermat 数 $F_n = 2^{2^n} + 1$
3.1 定义与性质
Fermat 数
$$F_n = 2^{2^n} + 1 \quad (n \ge 0)$$ $F_0 = 3, F_1 = 5, F_2 = 17, F_3 = 257, F_4 = 65537$ 均为素数。
Fermat 数的乘积恒等式
$$F_n = F_0 F_1 \cdots F_{n-1} + 2 \quad (n \ge 1)$$
故 $\gcd(F_m, F_n) = 1$（$m \ne n$），推出素数无穷。
Fermat 数的素因子形式
若 $p \mid F_n$，则 $p \equiv 1 \pmod{2^{n+2}}$。
证明：$p \mid F_n \Rightarrow 2^{2^n} \equiv -1 \pmod p \Rightarrow 2^{2^{n+1}} \equiv 1 \pmod p$，故 $\operatorname{ord}_p(2) = 2^{n+1}$（因 $2^{2^n} \not\equiv 1$）。又 $\operatorname{ord}_p(2) \mid p - 1$，故 $2^{n+1} \mid p - 1$。结合 $p$ 奇，$2^{n+2} \mid p - 1$。
Lucas 分解 $F_5$
$F_5 = 2^{32} + 1 = 4294967297 = 641 \times 6700417$。
验证 $641 \equiv 1 \pmod{2^7} = 1 \pmod{128}$ ✓（$641 = 5 \times 128 + 1$）。 Euler 用此性质寻找 $641$ 作为候选因子。
3.2 Fermat 素数猜想
Fermat 猜想与现状
Fermat 猜想所有 $F_n$为素数。Euler（1732）反例$F_5$。至今未发现 $n \ge 5$的 Fermat 素数，猜想$F_n$（$n \ge 5$）均合。
3.3 Fermat 数与正多边形作图
Gauss-Wantzel 定理
正 $n$边形可用尺规作图$\iff$ $n = 2^a p_1 p_2 \cdots p_k$，其中 $p_i$ 为互不相同的 Fermat 素数。
故正 $3, 5, 17, 257, 65537$边形可作图，但正$7, 9, 11, 13$ 边形不可。
四、$a^n - b^n$ 型数列
4.1 基本分解
几何级数分解
$$a^n - b^n = (a - b)(a^{n-1} + a^{n-2} b + \cdots + b^{n-1})$$ 若 $n$ 合，$n = mn'$，则 $a^n - b^n = (a^{n'})^{m} - (b^{n'})^m$ 进一步分解。
素数情形
若 $a^n - b^n / (a - b)$为素数，则$n$ 必为素数。这种形式的素数称为广义 Mersenne 素数。
4.2 Zsygmondy 定理
Zsygmondy 定理（1892）
对互素整数 $a > b > 0$，$n \ge 1$，$a^n - b^n$有原根素因子（即不整除$a^k - b^k$对所有$k < n$），除了两种例外：
- $n = 2$，$a + b$是$2$ 的幂
- $n = 6$，$a = 2, b = 1$
应用：$a^n - b^n$的不同素因子数$\ge 1$（除例外情形），这是 不定方程与丢番图方程 中 Catalan 与 Fermat 类问题的重要工具。
4.3 Lucas-Carmichael 定理
$a^n - b^n$的素因子模$n$
若 $p$是$a^n - b^n$（$\gcd(a, b) = 1$）的原根素因子，则 $p \equiv 1 \pmod n$。
4.4 分圆多项式
分圆多项式
$$\Phi_n(x) = \prod_{\substack{1 \le k \le n \newline \gcd(k, n) = 1}} (x - e^{2\pi i k/n})$$ 满足 $x^n - 1 = \prod_{d \mid n} \Phi_d(x)$。
$\Phi_n(a)$的素因子$p$满足$p \equiv 1 \pmod n$（除 $p \mid n$ 的例外情形）。
分圆多项式
$\Phi_1(x) = x - 1$ $\Phi_2(x) = x + 1$ $\Phi_3(x) = x^2 + x + 1$ $\Phi_4(x) = x^2 + 1$ $\Phi_5(x) = x^4 + x^3 + x^2 + x + 1$ $\Phi_6(x) = x^2 - x + 1$
$x^6 - 1 = \Phi_1 \Phi_2 \Phi_3 \Phi_6 = (x-1)(x+1)(x^2+x+1)(x^2-x+1)$ ✓
五、阶乘与超阶乘
5.1 $n!$ 的整除性
Legendre 公式
$$v_p(n!) = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor = \frac{n - s_p(n)}{p - 1}$$
$v_2(10!)$
$\lfloor 10/2 \rfloor + \lfloor 10/4 \rfloor + \lfloor 10/8 \rfloor = 5 + 2 + 1 = 8$ 验证：$10! = 3628800 = 2^8 \cdot 14175$ ✓
5.2 Wilson 定理与 $p!$
Wilson 定理
$(p - 1)! \equiv -1 \pmod p \iff p$ 素数。
Wilson 商
$$W_p = \frac{(p-1)! + 1}{p}$$ 当 $W_p \equiv 0 \pmod p$ 时，$p$称为 Wilson 素数。已知 Wilson 素数仅有$5, 13, 563$（搜索至 $5 \times 10^8$ 内）。
5.3 Bertrand 假设与 $n!$
由 Bertrand 假设，$\binom{2n}{n}$中含$(n, 2n)$的素数贡献，可证$\binom{2n}{n} \ge 4^n / (2n+1)$。
5.4 超阶乘与乘积表示
超阶乘 $H_n$
$$H_n = \prod_{k=1}^{n} k! = 1! \cdot 2! \cdot 3! \cdots n!$$ 满足递推 $H_n = H_{n-1} \cdot n!$，与 组合数论：卢卡斯与库默尔 中的二项式系数紧密相关。
六、Lucas 序列（复习）
Lucas 序列回顾
$U_n = (\alpha^n - \beta^n)/(\alpha - \beta)$，$V_n = \alpha^n + \beta^n$，其中 $\alpha, \beta$为$x^2 - Px + Q$ 的根。
- Fibonacci：$F_n = U_n(1, -1)$，$F_n \approx \varphi^n / \sqrt 5$（$\varphi = (1+\sqrt 5)/2$）
- Lucas 数：$L_n = V_n(1, -1)$，$L_n \approx \varphi^n$
详见 组合数论：卢卡斯与库默尔。
七、幂次和 $S_k(n) = \sum_{i=1}^{n} i^k$
7.1 公式
幂次和公式
- $S_1(n) = n(n+1)/2$
- $S_2(n) = n(n+1)(2n+1)/6$
- $S_3(n) = (n(n+1)/2)^2 = S_1(n)^2$（Nicomachus 恒等式）
- $S_4(n) = n(n+1)(2n+1)(3n^2+3n-1)/30$
- 一般：$S_k(n) = \dfrac{B_{k+1}(n+1) - B_{k+1}(0)}{k+1}$（Bernoulli 多项式）
7.2 Bernoulli 数
Bernoulli 数 $B_n$
生成函数 $\dfrac{t}{e^t - 1} = \sum_{n=0}^{\infty} B_n \dfrac{t^n}{n!}$。
前 $10$ 项：$B_0 = 1, B_1 = -1/2, B_2 = 1/6, B_3 = 0, B_4 = -1/30, B_5 = 0, B_6 = 1/42, B_7 = 0, B_8 = -1/30, B_9 = 0$。
Clausitz-von Staudt 定理
$$B_{2k} \equiv -\sum_{\substack{p \text{ 素} \newline (p-1) \mid 2k}} \frac{1}{p} \pmod 1$$ 即 $B_{2k}$的分母是$\prod_{(p-1) \mid 2k} p$。
Bernoulli 数分母
$B_2 = 1/6$，$2k = 2$，$p - 1 \mid 2 \Rightarrow p = 2, 3$，分母 $2 \cdot 3 = 6$ ✓ $B_4 = -1/30$，$2k = 4$，$p - 1 \mid 4 \Rightarrow p = 2, 3, 5$，分母 $2 \cdot 3 \cdot 5 = 30$ ✓ $B_6 = 1/42$，$2k = 6$，$p - 1 \mid 6 \Rightarrow p = 2, 3, 7$，分母 $2 \cdot 3 \cdot 7 = 42$ ✓
7.3 Kummer 同余式
Kummer 同余
若 $a \equiv b \pmod{\varphi(p)}$且$a, b$ 偶，$p - 1 \nmid a$，则 $$\frac{B_a}{a} \equiv \frac{B_b}{b} \pmod p$$
这是 整除与同余基础 中 Fermat 小定理在 Bernoulli 数上的推广，与 同余方程进阶与Hensel引理 中 $p$-adic 数论相关。
八、其它经典数列
8.1 Catalan 数复习
详见 组合数论：卢卡斯与库默尔：$C_n = \dfrac{1}{n+1} \binom{2n}{n}$。
8.2 Stirling 数复习
详见 组合数论：卢卡斯与库默尔。
8.3 Bell 数
Bell 数 $B_n$
$B_n$是$n$ 元集合的分拆方式数。 $$B_{n+1} = \sum_{k=0}^{n} \binom{n}{k} B_k,\quad B_0 = 1$$
前 $10$ 项：$1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147$。
Dobinski 公式：$B_n = e^{-1} \sum_{k=0}^{\infty} \dfrac{k^n}{k!}$。
8.4 Euler 数
Euler 数 $E_n$
$\operatorname{sech} t = \sum E_n t^n / n!$
前 $6$ 项：$E_0 = 1, E_1 = 0, E_2 = -1, E_3 = 0, E_4 = 5, E_5 = 0$。
Euler 数与 $\zeta(2k+1)$
Euler 数与 $\zeta$ 函数奇数点相关：$\zeta(2k+1)$的特殊值可用 Euler 数表示（但$\zeta(2k+1)$ 是否无理数至今未决）。
九、典型例题
例 1：$n^2 + 1$ 的素因子
求 $n^2 + 1 \le 100$中素因子均$\equiv 1 \pmod 4$的$n$。
解：枚举 $n \le 9$：
- $n = 1$：$2$（仅 $2$）
- $n = 2$：$5$ ✓
- $n = 3$：$10 = 2 \cdot 5$ ✓
- $n = 4$：$17$ ✓
- $n = 5$：$26 = 2 \cdot 13$ ✓
- $n = 6$：$37$ ✓
- $n = 7$：$50 = 2 \cdot 5^2$ ✓
- $n = 8$：$65 = 5 \cdot 13$ ✓
- $n = 9$：$82 = 2 \cdot 41$ ✓
所有奇素因子 $\equiv 1 \pmod 4$。
例 2：Mersenne 素性检验
检验 $M_{11} = 2047$ 是否素。
解：$p = 11$，需算 $s_9 \bmod 2047$。Lucas-Lehmer： $s_0 = 4$ $s_1 = 14$ $s_2 = 194$ $s_3 = 194^2 - 2 = 37634 = 2047 \times 18 + 788$，$\equiv 788$ $s_4 = 788^2 - 2 = 620944 - 2 = 620942 = 2047 \times 303 + 1301$，$\equiv 1301$ $s_5 = 1301^2 - 2 = 1692601 - 2 = 1692599 = 2047 \times 826 + 1497$，$\equiv 1497$ $s_6 = 1497^2 - 2 = 2241009 - 2 = 2241007 = 2047 \times 1094 + 1329$，$\equiv 1329$ $s_7 = 1329^2 - 2 = 1766241 - 2 = 1766239 = 2047 \times 862 + 1205$，$\equiv 1205$ $s_8 = 1205^2 - 2 = 1452025 - 2 = 1452023 = 2047 \times 709 + 0$，$\equiv 0$？检查：$2047 \times 709 = 1451323$，$1452023 - 1451323 = 700$，$\equiv 700$ $s_9 = 700^2 - 2 = 489998 = 2047 \times 239 + 705$，$\equiv 705 \ne 0$。
故 $M_{11}$非素。验证$2047 = 23 \times 89$ ✓
例 3：完全数检验
验证 $n = 496$ 是完全数。
解：$496 = 2^4 \cdot 31 = 2^{5-1} (2^5 - 1) = 16 \cdot 31$。$M_5 = 31$ 是 Mersenne 素数（$2^5 - 1 = 31$）。 $\sigma(496) = \sigma(2^4) \sigma(31) = (1+2+4+8+16)(1+31) = 31 \cdot 32 = 992 = 2 \cdot 496$ ✓
例 4：Fermat 数分解
求 $F_5 = 4294967297$ 的素因子。
解：$F_5 = 2^{32} + 1$，素因子 $p \equiv 1 \pmod{128}$。候选 $p \in \lbrace 129, 257, 385, 513, 641, \ldots\rbrace $。$129 = 3 \cdot 43$ 合，$257$素但$257 \nmid F_5$（验证 $2^{32} \bmod 257$：$257 = 2^8 + 1$，$2^8 \equiv -1 \pmod{257}$，$2^{32} = (2^8)^4 \equiv 1 \ne -1$）。$641$ 素：$641 = 5 \cdot 2^7 + 1 = 5 \cdot 128 + 1$。$641 \mid F_5$（Euler 1732 验证）。$F_5 / 641 = 6700417$。
例 5：Zsygmondy 应用
证明 $2^n - 1$有不同素因子数$\ge n / \log_2 n$（粗略）。
解：由 Zsygmondy，$2^n - 1$有原根素因子$p_n \equiv 1 \pmod n$。不同 $n$给不同$p_n$（因 $\operatorname{ord}_{p_n}(2) = n$ 唯一）。$\lbrace p_n : n \le N\rbrace $共$N$个不同素数，且$p_n \le 2^n - 1 \le 2^N$。
例 6：分圆多项式值
求 $\Phi_{12}(2)$。
解：$\Phi_{12}(x) = x^4 - x^2 + 1$（标准公式）。$\Phi_{12}(2) = 16 - 4 + 1 = 13$。
验证：$2^{12} - 1 = 4095 = 3 \cdot 5 \cdot 7 \cdot 13 \cdot \ldots$？$4095 = 3 \cdot 1365 = 3 \cdot 3 \cdot 455 = 9 \cdot 455 = 9 \cdot 5 \cdot 91 = 9 \cdot 5 \cdot 7 \cdot 13$ ✓。$13$确实是$2^{12} - 1$的因子，且$13 \equiv 1 \pmod{12}$ ✓。
例 7：Wilson 商计算
验证 $W_5 = (4! + 1)/5 = 25/5 = 5 \equiv 0 \pmod 5$，故 $5$ 是 Wilson 素数。
$W_{13} = (12! + 1)/13$。$12! = 479001600$。$12! + 1 = 479001601 = 13 \times 36846277$。$36846277 / 13 = 2834329$，余 $0$。故 $W_{13} \equiv 0 \pmod{13}$，$13$ 是 Wilson 素数 ✓
例 8：幂次和
求 $\sum_{k=1}^{100} k^3 \bmod 100$。
解：$S_3(n) = (n(n+1)/2)^2$。$S_3(100) = (100 \cdot 101 / 2)^2 = 5050^2 = 25502500$。
$25502500 \bmod 100 = 0$。
例 9：Catalan 模 $p$
求 $C_5 \bmod 7$。
解：$C_5 = \dfrac{1}{6} \binom{10}{5} = \dfrac{252}{6} = 42 \equiv 0 \pmod 7$ ✓ 由 Kummer：$v_7(C_5) = v_7\binom{10}{5} - v_7(6) = 0 - 0 = 0$？但 $42 = 6 \cdot 7$，$v_7 = 1$。
重新计算：$\binom{10}{5} = 252 = 4 \cdot 7 \cdot 9$，$v_7 = 1$。$v_7(6) = 0$。$v_7(C_5) = 1$✓。前面的 Kummer 分析中$n + n = 5 + 5 = 10$在$7$ 进制下：$5 = (5)_7$，$5 + 5 = 10 = (13)_7$（$1$进位）。故$v_7\binom{10}{5} = 1$ ✓。
十、与竞赛的联系
10.1 一试常见
- Mersenne 素数判定（必要条件、Lucas-Lehmer）
- $n^2 + 1$素因子模$4$ 性质
- 完全数与 Mersenne 素数的关系
- Fermat 数的乘积恒等式（证素数无穷）
- 分圆多项式简单应用
10.2 二试与 TST
- Zsygmondy 定理在不定方程中的应用
- Bernoulli 数与幂次和
- Lucas 序列的 $\gcd$ 性质
- Wilson 商与 Wilson 素数
10.3 高级竞赛
- 分圆多项式与原根
- Clausitz-von Staudt 定理与 Kummer 同余
- 完全数与模形式（Ramanujan 同余的推广）
- Bell 数与组合恒等式
十一、知识链接
- 整除与同余基础 — $v_p$ 赋值、Fermat 小定理、Wilson 定理
- 数论函数与欧拉定理 — $\sigma, \varphi, \mu$ 在 Mersenne 数、完全数中的应用
- 组合数论：卢卡斯与库默尔 — Lucas 序列、Catalan 数、Stirling 数
- 素数分布与解析数论初步 — Mersenne 素数分布、特殊素数猜想
- 不定方程与丢番图方程 — Zsygmondy 定理、Catalan 猜想
- 二次剩余与阶 — 原根与 Fermat 数素因子分析
- 同余方程进阶与Hensel引理 — Wilson 商、Wieferich 素数、$p$-adic 分析
- 数列与递推方法 — Fibonacci、Lucas 数列的递推通项与不动点法
- 矩阵与线性代数初步 — Fibonacci 矩阵 $Q=\begin{pmatrix}1&1\newline1&0\end{pmatrix}$ 对角化与 Pisano 周期
- 对称多项式与牛顿恒等式深化 — Bernoulli 数与幂和 $\sum i^k$ 的对称多项式表示
十二、mermaid 图：特殊数列分类
mermaid
graph TD
A[特殊数列]
A --> B[n²+1 型]
B --> C[素因子 ≡ 1 mod 4]
B --> D[Bunyakovsky 猜想]
A --> E[Mersenne 数 M_p = 2^p - 1]
E --> F[Lucas-Lehmer 检验]
E --> G[完全数 n = 2^(p-1) M_p]
E --> H[已知 51 个素数]
A --> I[Fermat 数 F_n = 2^2^n + 1]
I --> J[素因子 ≡ 1 mod 2^(n+2)]
I --> K[乘积恒等式]
I --> L[正多边形作图]
A --> M[a^n - b^n 型]
M --> N[几何级数分解]
M --> O[Zsygmondy 定理]
M --> P[分圆多项式]
A --> Q[阶乘与超阶乘]
Q --> R[Legendre 公式 v_p n!]
Q --> S[Wilson 定理与商]
Q --> T[Bertrand 应用]
A --> U[幂次和 S_k n]
U --> V[Bernoulli 数]
U --> W[Clausitz-von Staudt]
U --> X[Kummer 同余]
A --> Y[其它]
Y --> Z[Bell 数 B_n]
Y --> AA[Euler 数 E_n]
Y --> AB[Lucas 序列复习]十三、附录：常用数列数值表
| 数列 | $n$ | $n=1$ | $n=2$ | $n=3$ | $n=4$ | $n=5$ | $n=6$ |
|---|---|---|---|---|---|---|---|
| $F_n$Fibonacci | — | $1$ | $1$ | $2$ | $3$ | $5$ | $8$ |
| $L_n$Lucas | — | $1$ | $3$ | $4$ | $7$ | $11$ | $18$ |
| $C_n$Catalan | $C_0=1$ | $1$ | $2$ | $5$ | $14$ | $42$ | $132$ |
| $B_n$Bell | $B_0=1$ | $1$ | $2$ | $5$ | $15$ | $52$ | $203$ |
| $S(n, 2)$Stirling | — | $1$ | $3$ | $7$ | $15$ | $31$ | $63$ |
| $M_p$Mersenne | $p=2$ | $3$ | $7$ | $31$ | $127$ | $8191$ | $131071$ |
| $F_n$Fermat | $F_0=3$ | $3$ | $5$ | $17$ | $257$ | $65537$ | — |
| $p_n$第$n$素 | — | $2$ | $3$ | $5$ | $7$ | $11$ | $13$ |
| $n!$ | — | $1$ | $2$ | $6$ | $24$ | $120$ | $720$ |
| $H_n$超阶乘 | — | $1$ | $2$ | $12$ | $288$ | $34560$ | $24883200$ |
% 注：Mersenne 素数 $M_2 = 3, M_3 = 7, M_5 = 31, M_7 = 127, M_{13} = 8191, M_{17} = 131071$ 等。