关于作者（微信号 cdmath-pku）：北京大学数学科学学院博士，高中阶段获得中国数学奥林匹克（CMO）金牌，入选国家集训队，培养过各水平阶段的竞赛选手。
温馨提示：如果你发现某个式子很奇怪，很可能是因为显示不全，向左滑动即可完整查看。
写在前面
先给出探索分析的过程, 再给出基于分析而自然引出的完整解答. 其书写大致与官方解析相同, 细节略有调整.
2024 CMO P5
对素数, 设 为 到自身的一个双射, 满足: 对任意, 若, 则. 求证: 存在无穷多个素数, 使得这样的映射 存在; 也存在无穷多个素数, 使得这样的映射 不存在.
分析
笔者本题的探索过程略有曲折, 在成功做出之前, 有过下面的尝试: 对 "存在" 的情况, 考虑过 取成特殊双射. (1) 最简单的是 取成线性函数模, 显然无用. (2) 其次是考虑取, 其中 是大于 的奇数, 刷过《数论: 概念和问题》(Number Theory: Concepts and Problems) 的同学可能知道题 4.29 (伊朗 TST 2012), 该题有一个特例是: 当 时, 构成模 的完系, 这样看来可以取, 但是发现 很可能不成立. 即使让 的选择变得更宽松, 即允许考虑 到自身的任意双射, 并通过模 意义下的插值公式找到 所对应的多项式, 仍然在处理 时无从下手. (3) 甚至天马行空考虑, 仍然无法处理这个绝对值不等式.
转而思考, 所存在的 大概不具有通用解析式, 而是需要逐值定义的, 为此需要对 (其中) 的关系进行研究和刻画. 虽然与二次剩余有关, 但在此没有特别现成的二次剩余结论可以拿来即用, 只是感觉隐约感觉 型和 型的素数的所有剩余之间的关系图结构不太一样. 因此只好针对较小的, 具象地画出所有这样的 关系, 即凡是有 的关系的, 都在 之间连一条边, 进行观察.
由此容易发现,有向图的每个连通分支中, 从任意点出发沿有向边走, 最终必进入圈 (圈的存在性易由抽屉原理及数论简单推导保证), 而且在进入圈之前, 结构是一个二叉树. 并且容易发现,当 含 的幂很大时, 会存在比较深的二叉树.
由这样的同余关系特点, 再去思考 的要求, 会发现在较深的二叉树上存在问题, 例如以 为基准, 由 的要求可知, 的 值须与 的 值很近, 间接地, 又要与 的 值比较近, 再间接地, 又要与 的 值比较近... 这样 附近存在了太多的不同整数, 根本挤不下, 产生矛盾.
因此能够预见, 使 存在的素数, 应使 含 的幂较小, 最简单的是让 是 型, 即. 使 不存在的素数, 应使 含 的幂较大, 这样的素数的无穷性虽然可以用狄利克雷大定理直接得到, 但显然没有必要, 只须利用费马数素因子的熟知性质即可.
为方便起见, 可以只考虑 所在的连通分支, 这时的圈长是, 二叉树结构最典型, 也足够深. 例如 的情况下, 所在的连通分支中的每个点 (即使是叶子) 都满足. 一般地, 要考虑的同余方程会是, 其中 模 余; 方程的解数, 利用原根即可进行分析.
更一般地, 我们指出: 对一个, 若 离 (圈长大于 的) 圈还有 步, 则当 时, 意味着存在 使得
从而, 这表明 (反之, 此不等式不成立时, 存在, 其存在性可由阶的理论推出); 而当 时, 意味着 在圈中, 但 还未在圈中, 即 但, 说明 (这也说明必有, 即 所在二叉树深度为).
至于 (即) 时的构造, 我们发现此时每个连通分支主要是一个圈, 圈上每点还连了一个 "尾巴" (这些 "尾巴" 到圈上的步数只有), 由此易逐点构造,重点安排圈上点的取值, 让这些取值也做到相邻两者的差较小, 圈上的点安排好以后再安排那些尾巴的取值, 此处尽量利用奇偶性, 将其取值设定在它所指向的圈上的点的取值旁边.
解析
称素数 为好素数, 如果这样的映射 存在, 否则称素数 为坏素数.
第一步, 先证明模 余 的素数都是好素数 (熟知有无穷多个).
设 的所有二次剩余为. 若, 则从 向 引一条边 (若, 则视为向自己引边), 于是 的出度皆为. 此外, 对任意, 设, 则 与 中必恰有一个是模 的二次剩余, 故 的入度也为. 因此, 所生成的有向图是若干个有向圈的无交并.
对任意一个有向圈, 若圈长, 令
若圈长, 则令
这里 是某个待定的整数 (且不同的有向圈, 其对应的 也不一样). 注意每个圈的 值所使用的都是连续一串偶数, 因此可以对每个有向圈适当选取所对应的整数, 使得 (也就是所有圈的所有顶点) 的 值恰好将 这所有的 个连续偶数各使用了一遍. 注意此时只使用了偶数. 若 是非二次剩余, 设, 则令. 最后, 取. 这样的 保证是双射, 且若, 则. 故模 余 的素数都是好素数.
第二步, 取正整数 充分大使得 (勘误: 不等号应改为大于) , 例如. 只须再证明, 模 余 的素数都是坏素数 (有无穷多个, 因为熟知费马数 两两互素, 其素因子各不相同, 且每个素因子 模 余; 考虑所有, 即可取出无穷多个模 余 的素数).
事实上, 满足同余方程
的 在模 的意义下恰有 个解, 原因是可将 写成 的形式, 其中 为模 的一个原根, 此时同余方程变为
结合 模 的阶为 知要求, 即要求 是 的倍数, 这样的 恰有 个. 若存在满足要求的双射, 则对同余方程的每个解, 由绝对值不等式知
其中 作周期延拓理解, 即, 延拓后的 仍满足题中关键的不等式性质. 因 是单射, 从而满足 的不同的 有 个, 表明, 矛盾! 故满足条件的双射 不存在, 是坏素数.
综上得证.
欢迎交流
