A Congruence for Sums of Integer Powers Modulo Products of Distinct Primes

基本信息

• 论文ID: 2510.10418
• 标题: A Congruence for Sums of Integer Powers Modulo Products of Distinct Primes
• 作者: Shao-Yuan Huang, Hsiu-Yu Wu (国立台北教育大学数学暨资讯教育学系)
• 分类: math.NT (数论)
• 发表时间: 2025年10月12日 (arXiv预印本)
• 论文链接: https://arxiv.org/abs/2510.10418

摘要

设$p_1, p_2, \ldots, p_n$为不同的素数，$N_n = p_1p_2 \cdots p_n$。论文证明了对于任何被$\text{lcm}(p_1-1, p_2-1, \ldots, p_n-1)$整除的正整数$L$，以及满足$\gcd(a_i, N_n) = p_i$的自然数$a_i$，存在同余关系：$a_1^L + a_2^L + \cdots + a_n^L \equiv n-1 \pmod{N_n}$。此外，论文还针对$n=2,3$的情况，给出了$a^\eta \pmod{N_n}$余数问题的完整解答。

研究背景与动机

问题的重要性

1. 余数问题的基础性：确定形如$a^\eta \equiv ? \pmod{p_1p_2 \cdots p_n}$的余数问题是数论中的经典问题，在密码学、素性测试和计算数论中有广泛应用。
2. 现有方法的局限性：
   • Fermat小定理仅适用于素数模
   • Euler定理虽然适用于合数模，但需要使用欧拉函数
   • 处理合数模时通常需要结合中国剩余定理，过程复杂
3. 统一框架的需求：现有方法缺乏统一的处理框架，论文旨在建立更直接的公式体系，使更多人能够直接应用这些公式获得相应的余数。
4. 新同余性质的发现：研究过程中发现了有趣的同余性质，即素数幂次和的同余关系。

核心贡献

1. 主要定理：证明了对于不同素数乘积作为模数的情况下，满足特定条件的整数幂次和的同余关系（定理4）
2. 余数问题的完整解答：对$n=2,3$的情况给出了$a^\eta \pmod{N_n}$的完整公式（定理3和定理5）
3. 统一的理论框架：基于Fermat小定理建立了统一的方法，扩展了几个经典余数公式
4. 具体的计算公式：提供了可直接应用的余数计算公式，避免了复杂的中国剩余定理计算过程

方法详解

核心理论基础

论文基于以下经典定理：

• Fermat小定理：若$p$为素数，$a \in \mathbb{N}$且$\gcd(a,p)=1$，则$a^{p-1} \equiv 1 \pmod{p}$
• Euler定理：若$\gcd(a,n)=1$，则$a^{\phi(n)} \equiv 1 \pmod{n}$

主要结果

定理3（$n=2$的情况）

设$p$和$q$为不同素数，$a \in \mathbb{N}$，则：

1. 若$\gcd(a,pq) = pq$，则$a^\eta \equiv 0 \pmod{pq}$
2. 若$\gcd(a,pq) = 1$，则$a^{\text{lcm}(p-1,q-1)\eta} \equiv 1 \pmod{pq}$
3. 若$\gcd(a,pq) = q$，则$a^{(p-1)\eta} \equiv qq_p \pmod{pq}$
4. 若$\gcd(a,pq) = p$，则$a^{(q-1)\eta} \equiv 1-qq_p \pmod{pq}$

其中$q_p$是$q$在$\mathbb{Z}_p$中的乘法逆元。

定理4（主要定理）

设$p_1, p_2, \ldots, p_n$为不同素数，$a_1, a_2, \ldots, a_n \in \mathbb{N}$满足$\gcd(a_i, p_1p_2 \cdots p_n) = p_i$，则对任何被$\text{lcm}(p_1-1, p_2-1, \ldots, p_n-1)$整除的正整数$L$：

$a_1^L + a_2^L + \cdots + a_n^L \equiv n-1 \pmod{p_1p_2 \cdots p_n}$

定理5（$n=3$的情况）

设$p < q < r$为素数，$L = \text{lcm}(p-1, q-1, r-1)$，假设$qr \equiv 1 \pmod{p}$，则给出了各种$\gcd(a,pqr)$情况下$a^L$的具体余数公式。

证明策略

定理3的证明思路

1. 情况分析：根据$\gcd(a,pq)$的不同取值分四种情况讨论
2. Fermat小定理应用：利用$a^{p-1} \equiv 1 \pmod{p}$和$a^{q-1} \equiv 1 \pmod{q}$
3. 乘法逆元计算：通过构造和模运算性质确定具体的余数值

定理4的证明思路

1. 数学归纳法：对素数个数$n$进行归纳
2. 基础情况：$n=1,2$的情况已由前面结果建立
3. 归纳步骤：假设对$n=k$成立，证明对$n=k+1$也成立
4. 关键观察：利用$\gcd$的性质和Fermat小定理的应用

实验设置

验证例子

例子1（$n=2$）

• 参数：$133 = 7 \times 19$，$L = 18 = \text{lcm}(6,18)$
• 验证结果：$7^{18} + 19^{18} \equiv 77 + 57 \equiv 1 \pmod{133}$

例子2（$n=3$）

• 参数：$66 = 2 \times 3 \times 11$，$L = 10 = \text{lcm}(1,2,10)$
• 验证结果：$2^{10} + 3^{10} + 11^{10} \equiv 34 + 45 + 55 \equiv 2 \pmod{66}$

例子3（$n=4$）

• 参数：$p_1=3, p_2=7, p_3=11, p_4=17$，$L = 240$
• 验证结果：$3^{240\eta} + 7^{240\eta} + 11^{240\eta} + 17^{240\eta} \equiv 3 \pmod{3927}$

计算验证

论文通过具体的数值计算验证了理论结果的正确性，展示了公式的实用性。

实验结果

主要结果验证

1. 定理4的验证：通过多个具体例子验证了主要同余关系
2. 余数公式的准确性：例子3和例子4详细展示了定理3和定理5在具体计算中的应用
3. 公式的实用性：相比传统方法，新公式提供了更直接的计算途径

计算优势

• 避免中国剩余定理：直接给出余数公式，无需复杂的CRT计算
• 统一的处理框架：不同情况下使用相同的理论基础
• 明确的条件判断：通过$\gcd$值清晰地确定适用的公式

相关工作

经典数论结果

1. Fermat小定理：论文的理论基础
2. Euler定理：处理一般合数模的经典方法
3. 中国剩余定理：传统处理合数模的工具

本文的创新点

1. 直接公式：避免了CRT的复杂计算过程
2. 新的同余性质：发现了素数幂次和的有趣同余关系
3. 完整的分类讨论：对不同$\gcd$情况给出了完整的处理方案

结论与讨论

主要结论

1. 建立了新的同余关系：证明了定理4中的核心同余关系
2. 提供了实用的计算公式：对$n=2,3$给出了完整的余数计算方法
3. 统一了理论框架：基于Fermat小定理建立了统一的处理方法

局限性

1. 条件限制：定理5需要额外条件$qr \equiv 1 \pmod{p}$
2. 复杂性增长：随着素数个数增加，公式变得复杂
3. 特殊情况：目前只对$n=2,3$给出了完整解答

未来方向

1. 扩展到更大的$n$：为$n \geq 4$的情况建立完整的余数公式
2. 条件的推广：研究是否可以放松定理5中的额外条件
3. 算法优化：开发更高效的计算算法

深度评价

优点

1. 理论创新：发现了新的数论同余性质，具有理论价值
2. 实用价值：提供了直接可用的计算公式，避免了复杂的CRT计算
3. 证明严谨：使用数学归纳法等严格的证明方法
4. 例子丰富：通过多个具体例子验证了理论结果

不足

1. 完整性有限：只对$n=2,3$给出了完整解答
2. 条件苛刻：某些结果需要额外的限制条件
3. 推广困难：方法向更大$n$的推广存在技术挑战

影响力

1. 数论贡献：为模运算理论提供了新的视角和工具
2. 应用潜力：在密码学和计算数论中有潜在应用价值
3. 教学价值：为数论教学提供了新的例子和方法

适用场景

1. 密码学应用：RSA等公钥密码系统中的模指数运算
2. 素性测试：基于Fermat测试的算法优化
3. 计算数论：需要高效模运算的数值计算场景

参考文献

论文引用了数论和密码学领域的经典文献，包括：

• Burton的《Elementary Number Theory》
• Hardy和Wright的《An Introduction to the Theory of Numbers》
• Menezes等人的《Handbook of Applied Cryptography》
• RSA算法的原始论文等

总体评价：这是一篇在数论领域具有创新性的论文，发现了新的同余性质并提供了实用的计算方法。虽然在完整性和推广性方面还有待改进，但其理论贡献和实用价值使其成为该领域的有价值研究。