完全剩余系与缩剩余系的性质及解法_何忆捷.pdf

6 中等数学 完全剩余系与箱剩余系的性质及解法 何忆捷 （华东师范大学理工学脘数学系 2012 级博士研究生，2 0 0041 ） 中图分类号 ：0 1561文献标识码 ：文章编号： 1005 6 416 （2015）0 6 0 006 0 6 （本讲适合高中）价于其均与 互素 ，且关于模两两不同余 剩余类与剩余系是初等数论中的重要概性质 2 若？ （ 1矣 1 ）构成模 的完 念 在数学竞赛中，除数论问题外，许多组合系，、，（，） 1 ，则 （ 1矣矣 ） 题、甚至代数题也与剩余类、剩余系有密切的也构成模的完系 ； 联系 在解题时 ，不仅需要熟悉剩余系（完全若？（ 1名 构成模 的缩系 ， 剩余系或缩剩余系）的性质，还经常需要借 ，（ ， ）1，则 （ 1矣忘 助整体化思想来考虑剩余系（） ）也构成模 的缩系 ！ 性质3若 ？（ 1各）构成模的完 、介系 ，则 11定义 （1） 剩余类“ 丨 2 对正整数把全体整数按模的余数 （ ） ， 为偶数 ； 分成 类 ，每 一类数的全体称为模 的一个 ，、私 剩余类（或称同余类） 、士 （ 2 ）完全剩余系性质 4 右 名 识（ ） ）均构成 在模 的每个剩余类中各取 个元素 ， 则这 个数就组成模 的 一 个完全剩余系 ） （以下简称完系 ） 质 3性质4是从整体的角度考虑完 ）系和缩系 ，这样的想法也是解决许多问题的 在 任意 一个模 的完全剩余系巾 ，仅保 巾发点以下两例是其简单应甩 留与互素的那些数 （共识（ ）个数，其中， 少（ 为欧拉函数） ，则这（）个数组成模 2应用举例 的 一个 、 缩剩余系（或称既约剩余系、简化剩例 直 设为偶数， ？ 矣）均构 ） 成模 的完系证明6 （ 1？）不构成 1 2 常用性质模 的完手 性质 1 对于个整数，其构成模的证明 由性质 3 知 完系等价于其关于模 两两不同余 ； 对于识个整数 ，其构成模的缩系等 6 （） 则】（ ；） ） 收稿日期：20 15 02 0 2 222 2015年第6期7 故； 6 ； （ 1各）不构成模的完系解 由于 ！， 2 ， ？ ，构成模 的缩 例2设整数 ， （ ，） 1？证明 ：系 ，而（ ， 2 ） 1 ，则 2 ！， 2 2， ， 2 也构成 1 （） 模 的缩系 证明设 ，？ ， ？ ，？（？）构成模 的缩系 丹 2 ， ，皇、？办 由性质2知！，2， ，也 构成 模 的缩系？ 0 ？兀 7 一 2 ？ 根据性质4得 因为0 ，所以， ？ （ ） 4 1 又 （ 2 ？ ， ） 1 ，故立 ￥ （） （ ） 【注】本题即为欧拉定理下面考虑 的符号，只需确定 接下来再看几个例子 例 3设为正偶数证明 ：在 矩阵 ， 2 ， ，中大于 的 数的个数 123 ？ 不妨设 ， 2 7 1？则 2341 2 ？ ？ 0 ， 且 ；（ ）也构成模 的缩系 ？ 、从而 ，1 ； 乂） 12 ） 中找不到 一组 ， 2 ， ， ，其两两不同行且不因此 ，？， ，、中恰有 一半大 于 同列 ？ 证明反证法 （注意每个均不为！） ？ 假设有 一组 1 ， 2 ， ， 两两不同行且不 ？ ？ 同列 ，记这组中的 ； （ ）在第 ？行故 了 （ 1 2 1 7 列 则分别构成模？的 （ ） （，（ ，） ） 另 一方面 ，根据矩阵 4的特 点知 【注】这是 一道三角公式与剩余系性质的 ； 6产 （） 综合题 ，关键思想是从整体考虑模 的缩系 故 ；、（ 1各 ？ 忘 ）也构成模 的完系 ，2， ， 与 2 ！， 22 ， “ ， 2 ，结合诱导公 注意到为偶数 ，上述结论与例 1 矛 才挣 丄作 ？ 盾因此 ，矩阵中不存在 一组 ， 2 ， ，丽 式建义 之门的关系， 不同 摘謹邝 、汝 恰能求出 的绝对值 值得注意的 【注】本题中，式刻画了矩阵的特征，将吕 组合问题转化为 一个关于完系 的常规问题 是 ，若本题中？， ？ ，？仅仅为模 的（任 例 4设奇数 1 求； ； 的值 ，意的）缩系 ，则无法判定 的符号 ： 其中，2， ，为所有不大于 且与互例5对以下两个问题 ，分别求正整数 素的正整数 的所有可能值 ： 8中等数 学 （ 1 ）存在 ， 2 ， ？ ， ，使得 （ 2 ）若存在整数 ！ ；、（1各忘 ） ，使得 （各 ）分别构 成模 的完系 ；、； （ 1矣 ）均构成模 的 （ 2 ）存在 ，？， ，使得 、？ 、完系 ，求正整数 的所有可能值 （ ）分别构成模的完系由于在相差 一个排列 的意义下，可不妨 【分析与解】（ 1 ）是例 1的再现 （ 注 意到， 设 ，故问题（ 2 ）与（ 2 ）等价 （矣 ）也是模 的完系 ） ，但有所不从问题 （ 2 ）出发，将 “ 完系 ” 改成 “ 缩 同的是，除了证明 ？不为偶数 ，还需对所有奇系 ” ，便得到： 数给出符合条件的构造 例 6若存在整数？ 、（ 1矣乂炉 （）， 令 （ ） 使得 、？、，七、 （ 1矣矣识（ ）均构 由于（2 ， ）1 ，由性质 2得 ？ 纟 2丨构成 成模 的缩系 ，求正整数 的所有 可能 值 ？ 模 的完系 ，从而，得到（ 1 ）的结论是 为奇数解 当（， 6 ） 1 时，任取模 的 一个缩 （ 2 ）比（ 1 ）多 一项 限制，上述？ 的构系 ？ 造方式已不符合这 一限制 ，故要进 一步判 别令 、 2？ 贝 哪些奇数符合要求 3 ， 6 ， 当（ ， 6 ） 1时 ，考虑到 、 2、3（矣 彡 ）根据性质 2 它们 均为模 的缩系 均为模 的完系，故可令 2 1验证知结论反之 ，若？上、？ ） ） 均为模 的缩系 ，则存在某个 1 至此 ，只剩下斤 3 （6）的情形未考 虑 （ （1 ）4 6 （ 1 ） 解决它们 中必有偶数，也必有 3 的倍数；但根 考虑完系中各数的平方和（这也是 个 综上 ，正整数满足条件当且仅当 假设、 、 （ 16在 ）均为模 6 、 【注】当（ ， 6 ） 1 时，本题的构造方式 ？与例 5 相仿，但对（ ； ， 6 ） 的情形，本题不 2？ 2 2 （ 0 2 （ ？ ； 2 宜同例 5 那样考虑整体，而需关注缩系的 ； 1 2 2 “ 局部性质 ” （ 2 丨 2 2 ）4 2 （） 例 7 求所有满足以下条件的正整数 ？2（？） （2），、存在模 的两个完系 ？、（ 各） ，使得 故 3 三0 （ ） 从（一也是模 的完系 2 易知 ，3 卞 1 【分析与解】当 1 ， 2 时，令；6 ； 因此，的结论为 （ 6 ） 1 （ ？ ）即可 ，故 ， 2 满足条件 【注】在解（ 2 ）时，整体化思想得到了充以下证明不满足条件 分的发挥：不仅考虑完系中各数之和 ，还考虑（ 1 ）奇素数不满足条件 平方和，凡是这种轮换对称的整式 ，其取值在事实上，假如？ 、6 、 人 （ 1 忘 名 ）分别 模意义下与完系的选取是无关的遍历模的完系 ，不妨设 ，则当 2幻呦 问题（ 2 ）选自文 1 这里从（ 2 ）出发，时， 提出 一个新问题 故 卞 ；，6 ， 首先将（ 2 ）改编成因此 ，、 6 ；、（ 2 ）分别遍历模 2015年第6期9 的缩系 ？素数 ， （ ， 2 ） ，无平方因子）的情形 由威尔逊定理及性质 4 知其实只要对（2 ）的方法稍作修改，便可 对为奇素数 ，为奇数 ” 这种更 一 般的情形给出否定的回答 （ ） 1 （），事头上 ，考虑 1到打 2 中与 2互素 即 的数的 ， 体 ？ 洋音到 （ 2 ）将 （ 1 ）的方法迁移到 一般 的奇数 3 ） 3 （ 2 ） 办为奇数 的一个素因子 ， 叫 ） 丨 （ 2 ）（ 4 ） （2广 仍假设分别颜模斤的完系 3 （ 2 ） 2 4 （ ） 不妨设仏 ，2 2 ， ， （ ） （） 中所有的的倍数 则当 各 ？ ， 时 ，1 故丨 （ 2 0 奚220 进而， （ 2） 1“ ， 2）1 因此 ， 在模、及 ？（ 1广 （） 下、从分别遍應的 “ ） 完 系 当为奇数时 ，由于 、 力 11不妨设 （ 10 为 （7 0 （ ） ！ 2）中所有与 互素的数 （ ） （），则 当幻时，有 （ 2 ，） （ 2 ， 6 ）1 ？ 因此 ，？ 、6 ； 、从 （ 14幻 ）在模意义 （） 下必分别遍历（2 ， ） 1 ） 而上式是矛盾的注意到式 ，知 因此 ，奇数不满足条件 ， ，1 、 换个角度看，对 有平方素因子 ，） 的情形 ，亦可得出否定的结论 而上式是矛盾的 ？ 综合（ 2 ） （ 4 ） ，知所有整数 ；13不满 事实上记 7 足条件 ？ 不妨设卜，022 ， ，为 （1九 （ 1彡矣 ）因此 ，只有 ， 2 满足条件 中所有的的倍数，则 0 ） 【注 】本题技巧性较强 ，上述解答呈现了 进而， 丨 ， 丨对本题的 一种探究过程 ，其中每个环节均构 于是 ，必有；成 一个有 意义的小问题 该解答可适当精简 ， 这样 ，（ 矣 ）均为 2 的倍数 参见文献 2 因此 ，不存在 ，使得 九 （ ） 在本文最后 ，介绍 一个与原根有关的性 故当 有平方素因子时 ，结论是否定的 质 ，并给出例 7 的 一个应用 （4）现仅剩下需要研究 2 （为奇性质 5设为奇素数 ，为模的原根 10中 等数学 （任意奇素数均有原根 ，按原根的定义，此因而， 3 为符合条件的唯 一奇素数 时，应满足， 2 ， ， ， ），练 习题 （ 1 ）对正整数 、6 ，均有1 ？设 ，2， ，为 1 ， 2 ， ， 1的 一个 6 （ ） （）；排列巳知 ， 2 ， ，1 2 ？ （ 2 ）正整数？（ 14 却 1 ）构成模 1除以 的余数两两不同求正整数 的所 的完系有可能值 （ 1 ）构成模的缩系 ？ （第 45 届加拿大数学奥林匹克） 性质5的证明（ 1 ）由 费马 小定理知提示 ：0 ， ， 以 129 9 以1 ？ （ ） （） 中任意两数模 1 不同余，特别地 ， 反之 ，若、 （ ） ），设 、 6 为 、6（） ， 、 ， ？ ） 模 1的余数 ，不妨设 00 彡6 1 2 则由费马小定理知故 孔为奇数？ （） 再对 2构造例子 ， 而（客，）1，故？ 1 （） 2 2 ， ， 6 0 6 （ ） 2 2 2（ ） （ 2 ）由（ 1 ）知 2设厂 ，2， ？ ， 、？为 一个正 边形的 ？（ 1力分 1 ）模 1 两两不同顶点的 一个排列 证明 ：每 一条封闭 的折线 （ 1各 句 1 ）模两两不同 2，2 3 ， ， 2 ，2中至少有 一对 而各广均与互素 ，故由性质 1 得（ 2 ）平行线段 成立 （ 2011 ，克罗地亚国家数学竞赛） 例8求满足如下条件的奇素数存在提示 ：将正 2 边 形的顶点依次标上 1 ， 的 一个排列 ，、， ，、，使 2 ， ，用 4表示顶点 对应的数则 得 1 ， 2 ， ，（ 1 ） ？ 1 构成模的缩系 ？ 解设奇素数满足条件 ，取的原根公 ？1（？2 ） 由于， 2 ， ，构成模的缩系，故对约定 户2 每个 1 ， 2 ， ，户 1 ，可在模的意义下将 假如巧尺 1（1忘 名 ）两两不平行，则 表示成广 ，其中，巧， 2 ， ，丨 6 ，且由 （ 1各 名2 ）构成模 2的完系 ，这将 性质 5 的 ，知， ，、构成模 1推出矛盾 的完系 【注】可进 一步思考正 1边形的情形 因此 ，问题转化为 ：若 ， 2 ， ，、构 3？证明 ：无法将正整数的集合 成模广 1 的完系 ，能否找到模 1 的另 一个 ， ， 2 ， 17 ！ 完系 2， ， 、 ，使得 ， ， ， 分成两个不相交的非空子集4 、5 ，使得 构成 模的缩羞，换言之，；（ 1 6（广 1 ） ？ 4 构成模 1 的完系？提示 ：在 ， ， ， 17 中至多有 一 由例7 ，知当且仅当 1各2 ，即 3个 19的倍数 ，假设分拆 似4 1；5 符合条件， 时 ，结论是肯定的 则 1 ， ，1 7均不能为 19的倍数从 在本题中 ，相应的例子是 2 ， 2 1而 ，构成模 19 的缩系 2 015年第6期11 设 则？（ 1 矣 11 ） 、（1七（ 1彡111 ， 1句矣1 1 ）中各有 2 18 ！ 1 （1 9 ） 吧个数不被 整除，但 1 （ 19 ）， 卜 爿卜 ， ） 7 ，矛盾 ？ 4设为大于3 的正整数，（ ， 3 ） 1 6全明星篮球赛共有27名球员参加 ，他 求 （ 2 的值 ，其中，？， ， 们各自穿着印有自己最喜欢的号码的球衣， 4111每个号码均为非负整数 比赛结束后 ，他们排 为所有不大于且与互素的正整数成 3 行 9列的队伍供球迷拍照？一位古怪的 提示：？ ，？， ？ ，与 3？ ， 3？ 2 ， ， 3、球迷 只拍这样的 照片 ：镜头所含的球员构成 均为模 71的缩系 ？ 行 6列 （ 1（忘3 ， 1（6矣9 ）的矩形（此处 利用 1200820 ，得行、列方向与原队伍的行 、列方向 一致 ），且 镜头内球员的球衣号码之和（ 1 名球员时就 是他的球衣号码 ）是 10 的倍数 结果这位球 41 “ ： 11 2迷只 拍到 ￥名球员 求的最小可能值 2 ，（根据2011 年全国高中数学联赛题改编）