2025-11-10T02:57:02.611382

Carmichael Numbers in All Possible Arithmetic Progressions

Larsen
We prove that every arithmetic progression either contains infinitely many Carmichael numbers or none at all. Furthermore, there is a simple criterion for determining which category a given arithmetic progression falls into. In particular, if $m$ is any integer such that $(m,2ϕ(m))=1$ then there exist infinitely many Carmichael numbers divisible by $m$. As a consequence, we are able to prove that $\liminf_{n\text{ Carmichael}}\frac{ϕ(n)}{n}=0$, resolving a question of Alford, Granville, and Pomerance.
academic

Carmichael Numbers in All Possible Arithmetic Progressions

基本信息

  • 论文ID: 2504.09056
  • 标题: Carmichael Numbers in All Possible Arithmetic Progressions
  • 作者: Daniel Larsen
  • 分类: math.NT (数论)
  • 发表时间: 2025年4月 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2504.09056

摘要

本文证明了每个等差数列要么包含无穷多个Carmichael数，要么一个都不包含。此外，我们给出了一个简单的判别准则来确定给定等差数列属于哪一类。特别地，如果mm是任何满足(m,2ϕ(m))=1(m,2\phi(m))=1的整数，则存在无穷多个能被mm整除的Carmichael数。作为推论，我们证明了lim inf⁡n Carmichaelϕ(n)n=0\liminf_{n\text{ Carmichael}}\frac{\phi(n)}{n}=0，解决了Alford、Granville和Pomerance提出的一个问题。

研究背景与动机

问题背景

Carmichael数是一类特殊的合数，对于任何整数aa都满足an≡a(modn)a^n \equiv a \pmod{n}。根据Korselt准则，一个无平方因子的合数nn是Carmichael数当且仅当对于每个整除nn的素数pp，都有p−1p-1整除n−1n-1。

研究动机

  1. 分布问题：虽然1994年Alford、Granville和Pomerance证明了Carmichael数有无穷多个，但它们在等差数列中的分布问题仍未完全解决。
  2. 古老问题：Banks将"是否存在固定整数m>1m>1整除无穷多个Carmichael数"称为"古老问题"。
  3. 理论完善：类比素数在等差数列中分布的研究，Carmichael数的分布研究对数论理论具有重要意义。

现有方法局限性

经典的Alford-Granville-Pomerance (AGP)方法无法直接处理被固定整数整除的Carmichael数构造问题，因为直接乘以mm会破坏Korselt准则的模kk条件。

核心贡献

  1. 完全刻画：证明了每个等差数列要么包含无穷多个Carmichael数，要么完全不包含，给出了完整的二分类。
  2. 判别准则：提供了简单的"Carmichael兼容性"判别准则，包含三个易检验的条件。
  3. 存在性定理：证明了对任何满足(m,2ϕ(m))=1(m,2\phi(m))=1的整数mm，存在无穷多个被mm整除的Carmichael数。
  4. 密度下界：对于Carmichael兼容的等差数列，证明了存在至少x1/168−ϵx^{1/168-\epsilon}个小于xx的Carmichael数。
  5. 极限问题：解决了AGP提出的lim inf⁡n Carmichaelϕ(n)n=0\liminf_{n\text{ Carmichael}}\frac{\phi(n)}{n}=0问题。

方法详解

任务定义

给定等差数列r(modm)r \pmod{m}，判断其是否包含无穷多个Carmichael数，并在包含的情况下给出密度下界。

Carmichael兼容性定义

设g=(r,m)g = (r,m)，h=(λ(g),m)h = (\lambda(g),m)，等差数列r(modm)r \pmod{m}是Carmichael不兼容的当且仅当满足以下任一条件：

  • (g,2ϕ(g))>1(g, 2\phi(g)) > 1
  • h∤r−1h \nmid r - 1
  • 36∣m36 | m，r≡3(mod12)r \equiv 3 \pmod{12}，且r/g≡5r/g \equiv 5或7(mod12)7 \pmod{12}

否则称为Carmichael兼容的。

核心方法框架

双素数集构造

本文的关键创新是使用两组素数而非AGP方法的单组素数：

对于合适的整数k1,k2,L1,L2k_1, k_2, L_1, L_2，构造：

  • P1:={dk1+1:d∈D1}P_1 := \{dk_1 + 1 : d \in D_1\}
  • P2:={dk2+1:d∈D2}P_2 := \{dk_2 + 1 : d \in D_2\}

其中D1,D2D_1, D_2分别从L1,L2L_1, L_2的因子中选取。

模约束处理

寻找满足以下条件的Π1,Π2\Pi_1, \Pi_2：

  • Π1≡1(modL1)\Pi_1 \equiv 1 \pmod{L_1}且Π1≡1m(modk2L2)\Pi_1 \equiv \frac{1}{m} \pmod{k_2L_2}
  • Π2≡1(modL2)\Pi_2 \equiv 1 \pmod{L_2}且Π2≡1m(modk1L1)\Pi_2 \equiv \frac{1}{m} \pmod{k_1L_1}
  • Π1,Π2≡1(modϕ(m))\Pi_1, \Pi_2 \equiv 1 \pmod{\phi(m)}

则mΠ1Π2m\Pi_1\Pi_2满足Korselt准则。

技术创新点

1. 逃离子群方法

使用改进的大筛法处理固定阶字符，避免素数集中在真子群中：

命题6（改进大筛不等式）：设MM是rr次幂无关正整数集，QQ是有限正整数集，则 ∑q∈Q∑χ mod q,χr=χ0∗∣∑m∈Mχ(m)∣2≪Q1−1rM4+Q′∣M∣\sum_{q\in Q} \sum_{\chi \bmod q, \chi^r=\chi_0}^* \left|\sum_{m\in M} \chi(m)\right|^2 \ll Q^{1-\frac{1}{r}}M^4 + Q'|M|

2. 等分布控制

通过Property 7*确保素数集在字符作用下的等分布性： 对于至多yρy^{\rho}个QiQ_i中元素的乘积nn，任何非主字符χ mod n\chi \bmod n和实数β\beta，存在至少yθy3ι\frac{y^{\theta}}{y^{3\iota}}个q∈Q3−iq \in Q_{3-i}使得∣βq−β∣≥12yρ+ι|\beta_q - \beta| \geq \frac{1}{2y^{\rho+\iota}}。

3. 代数数论工具

使用rr次幂互反律和理想字符理论处理高阶字符的分布问题。

实验设置

参数选择

  • yy：大参数，决定Carmichael数的大小
  • ι\iota：很小的正数，决定误差项
  • δ=16\delta = \frac{1}{6}，θ=16−2ι\theta = \frac{1}{6} - 2\iota，ρ=124−2ι\rho = \frac{1}{24} - 2\iota
  • κ,T\kappa, T：大整数常数（如100）

构造流程

  1. 构造素数集Q1,Q2Q_1, Q_2满足8个性质
  2. 筛选参数k1,k2k_1, k_2满足互质性和覆盖性条件
  3. 构建辅助乘积A1,A2A_1, A_2处理模LL约束
  4. 字符方法构造满足模kk约束的乘积

实验结果

主要定理

定理1：设r(modm)r \pmod{m}是Carmichael兼容等差数列。则对每个ϵ>0\epsilon > 0和充分大的xx，存在超过x1/168−ϵx^{1/168-\epsilon}个小于xx的Carmichael数同余于r(modm)r \pmod{m}。

关键推论

定理2：lim inf⁡n Carmichaelϕ(n)n=0\liminf_{n\text{ Carmichael}}\frac{\phi(n)}{n} = 0

证明思路：利用Erdős构造的素数序列{qi}\{q_i\}，其乘积QQ满足−log⁡ϕ(Q)Q→∞-\log\frac{\phi(Q)}{Q} \to \infty，结合定理1得到被QQ整除的Carmichael数。

密度改进

对于素数rr不整除mm的情况，本文方法给出x1/168−ϵx^{1/168-\epsilon}下界，改进了：

  • 当rr是二次剩余时：Matomäki的结果
  • 当rr是二次非剩余时：Pomerance的x16log⁡log⁡log⁡xx^{\frac{1}{6\log\log\log x}}

相关工作

历史发展

  1. Šimerka (1885)：发现第一个已知Carmichael数561
  2. Korselt (1899)：给出Carmichael数的判别准则
  3. AGP (1994)：证明Carmichael数有无穷多个
  4. Wright (2013)：证明(a,q)=1(a,q)=1时等差数列a(modq)a \pmod{q}包含无穷多个Carmichael数

本文贡献

  • 完全性：处理了(a,q)>1(a,q)>1的困难情况
  • 统一性：给出了所有等差数列的完整分类
  • 技术性：发展了新的筛法和字符理论工具

结论与讨论

主要结论

  1. Carmichael数在等差数列中的分布问题得到完全解决
  2. 提供了实用的判别准则
  3. 解决了AGP提出的重要问题

局限性

  1. 常数1168\frac{1}{168}不是最优的，可通过更精细的筛法改进
  2. 方法的复杂性较高，涉及多个技术层面
  3. 对于具体应用，参数选择需要仔细平衡

未来方向

  1. 优化常数：改进密度下界的常数
  2. 推广应用：扩展到Fermat伪素数等相关对象
  3. 计算方面：发展高效的Carmichael数构造算法

深度评价

优点

  1. 理论完备性：完全解决了等差数列中Carmichael数分布的基本问题
  2. 方法创新性：双素数集方法是对AGP方法的重要发展
  3. 技术深度：综合运用了筛法、字符理论、代数数论等多个工具
  4. 结果强度：不仅证明存在性，还给出了定量的密度下界

不足

  1. 技术复杂性：证明涉及大量技术细节，理解门槛较高
  2. 常数优化：1168\frac{1}{168}的常数有改进空间
  3. 实用性：对于具体构造Carmichael数，方法的实用性有限

影响力

  1. 理论贡献：解决了数论中的一个基本问题，具有重要理论价值
  2. 方法论意义：双素数集方法可能适用于其他类似问题
  3. 后续研究：为Carmichael数和相关伪素数的研究开辟了新方向

适用场景

  1. 理论研究：Carmichael数分布理论的进一步发展
  2. 密码学：理解伪素数在密码系统中的分布
  3. 计算数论：为Carmichael数的高效生成提供理论基础

参考文献

论文引用了56篇重要文献，主要包括：

  • Alford, Granville, Pomerance的开创性工作
  • Wright在等差数列中Carmichael数方面的贡献
  • Bombieri-Vinogradov定理等解析数论经典结果
  • 筛法理论的相关文献

总结：这是一篇解决数论中重要问题的高质量理论论文，通过创新的双素数集方法完全刻画了Carmichael数在等差数列中的分布，具有重要的理论价值和方法论意义。