🔢 mathematics

On the sequence $\mathrm{gcd}(a^n-1,b^n-1)$

本文通过证明序列 $g_n = \gcd(a^n-1, b^n-1)$ 当且仅当 $a$ 与 $b$ 乘法相关时满足线性递推关系，研究了该序列，从而确立了独立基底下公共整除序列的周期性，推导了其局部结构的精确公式，并为向整数 Ailon–Rudnick 猜想的结构化归约提供了研究方向。

原作者： Khai-Hoan Nguyen-Dang

发布于 2026-06-09

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Khai-Hoan Nguyen-Dang

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你拥有两台巨大的魔法机器。我们把它们分别称为机器 A 和机器 B。

机器 A 输入一个数字 $n$ ，然后吐出一个巨大的数字： $a^n - 1$ 。
机器 B 输入同一个数字 $n$ ，然后吐出另一个巨大的数字： $b^n - 1$ 。

现在，想象你有一个“最大公约数”（GCD）探测器。这个探测器观察这两台机器刚刚产生的两个数字，并找出能同时整除这两个数的最大数字。我们把这个共享的数字称为 $g_n$ 。

Khai-Hoan Nguyen-Dang 的论文是对这一共享数字序列（ $g_1, g_2, g_3, \dots$ ）行为的深入研究。作者提出了一个问题：这些共享数字是否存在一种简单、可预测的模式？

以下是该论文研究结果的拆解，使用了简单的类比：

1. 两种类型的机器

作者发现，这些机器的行为完全取决于它们的初始设置 $a$ 和 $b$ 之间的关系。

“相关型”机器（可预测）：
如果 $a$ 和 $b$ 是“乘法相关”的，这意味着其中一个只是另一个的幂（例如 4 和 8，因为 $4=2^2$ 且 $8=2^3$ ）。
- 结果： 当机器是相关联时，共享数字序列（ $g_n$ ）遵循一个非常严格、简单的规则，称为线性递推。
- 类比： 这就像一支正在演奏乐曲的行进乐队。如果鼓手和喇叭手完美同步（相关），他们结合在一起的节奏就会遵循一个简单的、重复的节拍，你可以永远预测它。论文证明，如果一个序列遵循这种简单的节拍，那么这些机器一定是对相关的。
“独立型”机器（混沌）：
如果 $a$ 和 $b$ 是“乘法独立”的（例如 2 和 3，其中一个不是另一个的幂），它们就像是在演奏完全不同乐曲的两名音乐家。
- 结果： 在这种情况下，共享数字序列（ $g_n$ ）无法通过任何简单的、恒定的规则来预测。它是过于混沌的。
- 类比： 如果你试图强迫行进乐队在两名音乐家演奏独立乐曲时遵循一个简单的节拍，这种尝试就会失败。论文证明，无论你如何尝试去拟合一个简单的规则，它最终都会失效。

2. “幽灵”模式

作者还提出了一个更深层的问题：即使整个序列是混沌的，是否其中存在一个部分是可预测的？具体来说，是否存在一个较小的序列，它既能整除两台机器的输出，又遵循一个简单的规则？

研究结果： 如果机器是独立的，答案是不成立，除非那个较小的序列仅仅是一个枯燥的、循环往复的周期序列（periodic）。
类比： 想象试图从两名音乐家产生的混沌噪音中寻找隐藏的节奏。论文证明，你所能找到的唯一“节奏”只是那些不断重复的简单、短小的循环。不存在任何隐藏的、复杂的、长期的模式。

3. 绘制“坏点”图谱

随后，作者将目光转向精确观察究竟在何时共享数字 $g_n$ 大于 1（即两台机器何时产生共同因子）。

“坏集”： 作者创建了一个精确的地图，记录了所有机器产生共同因子的数字 $n$ 。
类比： 想象一个日历。大多数日子里，两台机器产生的数字之间没有任何共同点。但在某些特定的日子，它们会共享一个秘密。论文提供了一个公式，可以在日历上画出“箭头”，精准指向这些秘密发生的日子。
- 研究表明，这些“秘密之日”仅仅是一系列特定的重复日程（算术级数）。
- 如果我们对机器进行归一化处理，使其在第 1 天不共享秘密，那么论文显示，“坏日子”恰好是落在特定质数日程上的日子。

4. “Ailon–Rudnick”之谜

最后，论文探讨了一个著名的未解之谜，即 Ailon–Rudrick 猜想。

谜题： 如果机器是独立的且在第 1 天不共享秘密，那么它们是否会在无穷多个日子里产生没有任何共同因子的数字（即 $g_n = 1$ ）？
论文的贡献： 作者并没有解决整个谜题，但他们将其分解成了更小、更易处理的部分。他们表明，要解决这个谜题，只需要检查特定类型的“坏日子”（如质数）以及寻找特定的代数“指纹”（结式/resultants）。
类比： 与其试图证明整个日历大部分时间都是空白的，作者说：“让我们只看周二。如果我们能证明周二没有秘密，我们就取得了巨大的进展。”他们提供了一份清单，如果满足这些条件，就能解决这个谜团。

总结

简而言之，这是一篇对两个指数序列之间共享因子节奏的严谨研究。

如果基数相关： 节奏是简单且可预测的。
如果基数无关： 节奏是混沌的，且不存在任何隐藏的简单模式（除了枯燥的循环）。
“坏”日子： 作者绘制了这些共享因子出现的精确时刻，将一个模糊的谜团变成了一份精确的重复日程清单。
大猜想： 论文提供了一套更锐利的工具，帮助数学家最终证明这些机器是否会停止分享秘密。

技术摘要：关于序列 $\gcd(a^n - 1, b^n - 1)$

问题陈述

本文研究了由整数 $a, b \ge 2$ 定义的序列 $(g_n)_{n \ge 1}$ 的算术结构，其中 $g_n := \gcd(a^n - 1, b^n - 1)$ 。该序列自然地处于两个经典领域：指数序列的最大公约数理论与线性整除序列理论的交汇点。

其核心动机源于整数环境下的 Ailon–Rudnick 猜想。虽然 Ailon 和 Rudnick 已证明了一个关于函数域的强结论，即若 $f, g \in \mathbb{C}[T]$ 是乘法独立的，则 $\gcd(f^n - 1, g^n - 1)$ 被多项式界定；但在整数情况下的研究仍处于开放状态。该猜想假设，如果 $a$ 和 $b$ 是乘法独立的且 $\gcd(a-1, b-1)=1$ ，那么对于无穷多个 $n$ ，都有 $\gcd(a^n - 1, b^n - 1) = 1$ 。

本文旨在明确通过 常系数线性递推关系 和 线性整除序列 (LDS) 框架可以解释以及无法解释 $(g_n)$ 的哪些部分。

研究方法

作者结合了代数数论、解析界限和结构分类定理：

线性递推的刚性： 本文利用了经典的原理，即所有共轭都在闭单位圆盘内的代数整数必为单位根（Kronecker 引理）。这一原理被应用于线性递推的生成函数，用以证明具有亚指数增长的序列在算术级数上最终必然是多项式的。
亚指数界限： 基础性的定量输入是 Bugeaud, Corvaja, 和 Zannier 的定理，该定理确立了对于乘法独立的 $a, b$ ，有 $\log \gcd(a^n - 1, b^n - 1) \le \epsilon n + O_\epsilon(1)$ 。
LDS 的分类： 本工作高度依赖于 Granville 最近对整数线性整除序列的分类，该分类将此类序列分解为周期性、幂次项和多项式生成项。
局部算术 (LTE)： 本文使用升幂引理 (Lifting The Exponent, LTE) 来推导 $g_n$ 的 $p$ 进估值（ $p$ -adic valuations）的精确公式。
分圆结式： 为了处理素数指数下的 Ailon–Rudnick 猜想，本文利用分圆多项式和结式（resultants）的性质，将问题简化为有限证书和局部覆盖问题。

核心贡献与结果

1. 将 GCD 序列分类为线性递推

本文建立了一个关于 $(g_n)$ 是否满足常系数线性递推关系的严格刚性定理。

定理 1.1： 序列 $(g_n)$ $(g_{n})$ 满足常系数线性递推关系，当且仅当 $a$ $a$ 和 $b$ $b$ 是 乘法相关（multiplicatively dependent） 的。
- 若相关，则存在整数 $c \ge 2$ 以及 $r, s \ge 1$ ，使得 $a=c^r, b=c^s$ 。在这种情况下， $g_n = c^{\gcd(r,s)n} - 1$ ，这是一个简单的线性递推。
- 若独立，则该序列的尾部不满足任何线性递推。
推论 3.4： 因此， $(g_n)$ 是一个 线性整除序列 (LDS)，当且仅当 $a$ 和 $b$ 是乘法相关的。

2. 共同 LDS 因子的刚性

本文探讨了在独立情况下，是否存在任何非平凡的线性整除序列能同时整除 $a^n - 1$ 和 $b^n - 1$ 。

定理 1.2 / 定理 4.3： 如果 $a$ $a$ 和 $b$ $b$ 是乘法独立的，那么 每一个 满足 $W_n \mid a^n - 1$ $W_{n} ∣ a^{n} - 1$ 且 $W_n \mid b^n - 1$ $W_{n} ∣ b^{n} - 1$ 的整数线性整除序列 $(W_n)$ $(W_{n})$ 都是 周期性 的。
- 该结果结合了 Bugeaud–Corvaja–Zannier 界限（亚指数增长）与 Granville 的 LDS 分类。这意味着“线性递推”机制无法解释独立情况下的非平凡公因子；任何此类公因子必须是周期的。

3. 局部结构与支撑公式

本文提供了关于 $g_n$ 的支撑集（support）和估值的精确公式，并识别了“坏集” $\{n : g_n > 1\}$ 。

支撑公式 (命题 5.1)： 对于素数 $p \nmid ab$ ，令 $L_p = \text{lcm}(\text{ord}_p(a), \text{ord}_p(b))$ 。则 $p \mid g_n \iff L_p \mid n$ 。
估值公式 (命题 5.2)： 对于奇素数 $p \nmid ab$ ，若 $L_p \mid n$ ，则 $v_p(g_n) = c_p + v_p(n)$ ，其中 $c_p = \min(v_p(a^{L_p}-1), v_p(b^{L_p}-1))$ 。
坏集特征 (推论 5.4)： 在归一化条件 $\gcd(a-1, b-1)=1$ 下，集合 $\{n : g_n > 1\}$ 正好是算术级数的并集：
$\{n \ge 1 : g_n > 1\} = \bigcup_{p \nmid ab} L_p \mathbb{N}$
Ailon–Rudnick 猜想因此等价于该并集的补集是无穷的。

4. 向 Ailon–Rudrick 猜想的归约

本文推导出了若干结构性归约，将猜想的难度隔离到局部覆盖问题上，从而排除了线性递推机制。

原初支撑准则 (命题 5.6)： 坏集可以压缩为由最小周期 $L_p$ 生成的原初集合 $B$ 的算术级数并集。若 $\sum_{d \in B} 1/d < \infty$ ，则好集具有正的下渐近密度。
素数指数归约 (定理 6.2)： 对于位于有限例外集 $\Sigma(a,b)$ 之外的素数 $\ell$ ， $g_\ell > 1$ 当且仅当 $A_\ell = \frac{a^\ell-1}{a-1}$ 和 $B_\ell = \frac{b^\ell-1}{b-1}$ 共享一个原初因子（即存在素数 $p$ 使得 $\text{ord}_p(a) = \text{ord}_p(b) = \ell$ ）。
有限证书 (定理 6.4)： 若 $g_\ell > 1$ ，则存在整数 $1 \le u, v \le \lceil \sqrt{\ell} \rceil$ 以及素数 $p \equiv 1 \pmod \ell$ ，使得 $p \mid a^u - b^v$ 或 $p \mid a^u b^v - 1$ 。
结式压缩 (推论 6.6)： 条件 $g_\ell > 1$ 意味着存在素数 $p \equiv 1 \pmod \ell$ 整除分圆结式 $R_\ell(b-a) = \text{Res}_X(\Phi_\ell(X), \Phi_\ell(X + b-a))$ 。

重要性与主张

本文声称在涉及线性递推和整除序列的背景下，对序列 $(g_n)$ 提供了决定性的结构分析。

消除线性机制： 其主要意义在于证明了序列 $(g_n)$ 本身不是一个线性整除序列（除非 $a, b$ 相关），并且在独立情况下，没有任何非周期性的线性整除序列可以作为公因子。这表明不能通过将 $(g_n)$ 建模为线性递推来解决 Ailon–Rudnick 猜想。
难度的局部化： 通过建立精确的局部公式和归约，本文认为该猜想的剩余难度是一个由乘法阶和素数指数障碍控制的 局部覆盖问题，而非全局线性递推现象。
精确刻画： 本文提供了通用情况下首次精确的支撑集和估值公式，将坏集确定为由局部周期 $L_p$ 决定的显式算术级数并集。

作者总结道，“线性递推机制”已被充分理解并排除；现在问题归结为分析局部周期集合 $\{L_p\}$ 的密度和覆盖性质。