； 收稿日期 ： 修改日期 ： ２ ０ １ ０ ０ ４ ０ ５ ２ ０ １ ２ ０ ６ ０ ４ － － － － ， 作者简介 ： 刘耀斌 （ 男， 山东德州人 ， 硕士 ， 讲师 ， 主要从事代 １ ９ ６ ８－） ： 数学方面的研究 ． Ｅ ｍ ａ ｉ ｌ ｌ ｂ ｃ ｈ ８ ９ ８ ５＠ｓ ｏ ｈ ｕ． ｃ ｏ ｍ ｙ ｇ
利用定理 ２ 求解同余式的关键在于要求出整数 使得 ａ｜ （ 也就是要求使 ｍ ｙ， ｙ ＋ｂ）， ｍ ｍ ｏ ｄ ａ） ｙ ＋ｂ ≡ ０ （ 成立的整数 ｙ， 即求解关于 ｙ 的同余式 ， （ ） ｍ ｍ ｏ ｄ ａ） ４ ｙ ≡－ｂ （ （ ） 从而 把 求 解 同 余 式 ２ 的 问 题 转 化 为 求 解 同 余 式 （ ）的问题 ． 对于 ｍ 大于ａ 的情形 ， 这个转化是有重 ４ 要 意义的 ． 通过求 ｍ 和 － ｂ分别模ａ 的最小非负剩余 ）变为 将同余式 （ ｍ１ 和ｒ， ４ ， ｍ１ ｍ ｏ ｄ ａ） ｙ ≡ｒ （ 此时的系数 ｍ１ ＜ａ． 若模ａ 还是比较大时 ， 再重复上 述这个过程 ， 直至变为系数和模都比较小为止 ． 例 ２ 求解同余式 ） ３ ２ ５ ｘ ≡２ ０（ ｍ ｏ ｄ １ ６ １ ． ）＝ １， 解 因为 （ 故所给同余式有解 ． ３ ２ ５， １ ６ １ 又因 ） ， ３ ２ ５≡３（ ｍ ｏ ｄ １ ６ １ 故所给同余式等价于 ） ３ ｘ ≡２ ０（ ｍ ｏ ｄ １ ６ １ ． 注意模 １ 故先解同余式 ６ １ 较大 ， ） ， １ ６ １ ０（ ｍ ｏ ｄ ３ ｙ ≡－２ 也即 ） ， ２ ｍ ｏ ｄ ３ ｙ ≡１ （ 其解为
为简单的求出一次同余的解 ． 关键词 一次同余式 ； 充分必要条件 ； 模 中图分类号 Ｏ １ ５ ６． １ 文献标识码 Ａ （ ） 文章编号 １ ０ ０ ８ １ ３ ９ ９ ２ ０ １ ２ ０ ４ ０ ０ ７ ９ ０ ３ － － －
在同余 式 方 程 中 ， 一次同余式是最基本最简单 的一种 ， 高次同余式 的 求 解 最 终 也 是 归 结 为 一 次 同 因此研 究 一 次 同 余 式 的 求 解 具 有 重 要 余式的求解 ， 的意义 ．
ｘ≡
４ ２＋３×３ ３ ７ ） １（ ｍ ｏ ｄ ３ ３ ７ ． ≡８ １ ３
４ 结语
根据所 给 一 次 同 余 式 的 模 的 大 小 的 不 同 ， 可以 选择不同的求解方法 ， 使求解过程尽量简单化 ， 从而 容易求出一次同余式的解 ．
参考文献 ［ ］李复中 ． 初等数论选讲［ 长 春： 东北师范大学出版 １ Ｍ］ ． 社， １ ９ ９ １： ９ ３ ９ ８． － ［ ］闵嗣鹤 ， 严士 健． 初等数论［ 北 京： 高等教育出 ２ Ｍ］ ． ３ 版． 版社 ， ２ ０ ０ ３： ７ ４ ７ ５． －
ａ ｓ＋ ｍ ｔ ＝ １， ）＝ １， 此时必有 （ 于是得到 ｍ， ｓ ａ ｓ ≡１ （ ｍ ｏ ｄ ｍ） ．
）＝ １， 因为 （ 所以以下三式 ｍ， ｓ ， ａ ｘ ≡ｂ （ ｍ ｏ ｄ ｍ） ， ａ ｓ ｘ ≡ｂ ｓ（ ｍ ｏ ｄ ｍ） ｘ ≡ｂ ｓ（ ｍ ｏ ｄ ｍ） ）的解为 彼此等价 ， 因此同余式 （ ２
ａ ｘ ≡ｂ ｃ（ ｍ ｏ ｄ ｍ） ． １ 反复这样做 ， 总可以经有限步骤后 ， 将 ｘ 的系数变为
从而求得原同余式的解 ． １， 例 １ 求解一次同余式 ） ８ ｘ ≡９ （ ｍ ｏ ｄ １ １ ．
８ ０
高 等 数 学 研 究
２ ０ １ ２年７月
）＝ １， 解 因为（ 所以同余式有唯一解 ８， １ １ （ ） 对模 １ 依次对同余式进行等价变形 ， 得 １ 来说 ． ） ， １ ６ ｘ ≡１ ８（ ｍ ｏ ｄ １ １ ） ， ５ ｘ ≡７ （ ｍ ｏ ｄ １ １ ） ， １ ０ ｘ ≡１ ４（ ｍ ｏ ｄ １ １ ） ， ｍ ｏ ｄ １ １ －ｘ ≡ ３ （ ） ， ｘ ≡－３ （ ｍ ｏ ｄ １ １ 所以同余式 的解为 ） ｘ ≡８ （ ｍ ｏ ｄ １ １ ． 上述过程实 际 是 用 与 模 ｍ 互 质 的 整 数 乘 同 余 再取它们关于模 ｍ 的绝对最小剩余 ， 直至 ｘ 式两端 ， 的系数变为 １ 为止 ． 方法 ２ 将大系数变为小系数 ， 大模变为小模 ． 定理 ２ 设 （ 如 果 存 在 ｙ ∈ 瓕， 使 ａ， ｍ）＝ １， ，则 得 ａ｜ （ ｍ ｙ ＋ｂ）
（）
１ φｍ － （ ， ｘ ≡ｂ ａ ｍ ｏ ｄ ｍ） ）的解为 彼些等价 ， 即同余式 （ ２ １ φｍ － （ ｘ ≡ｂ ａ ｍ ｏ ｄ ｍ） ． ， 不管是利用最大公因数 还是利用欧拉定理 ， 这 （）
）的一次同余式进行讨论 ． 以下仅就形如 （ ２ ］给出了利用二元一 次 不 定 方 程 求 解 一 次 文［ ２ ）的方法 ， 同余式 （ 虽然具有普 遍 性 ， 但在具体求解 １ 时比较麻烦 ． 下面利 用 同 余 的 基 本 理 论 给 出 几 个 比 较实用的求解方法 ．
）＝ １， 且（ 故所给同余式等价于 ８ １， ３ ３ ７ ） ， ８ １ ｘ ≡－１ ７ ９×１ ≡－１ ７ ９（ ｍ ｏ ｄ ３ ３ ７ ）＝ １， 又因为 ３ 且（ 故上式 ３ ７＝８ １×４＋１ ３， １ ３， ３ ３ ７ 等价于 ） ） １ ３ ｘ ≡－ （ ７ ９ ２（ ｍ ｏ ｄ ３ ３ ７ ． －１ ×４ ≡ ４ 再利用定理 １， 先求解 ） ， ３ ３ ７ ２（ ｍ ｏ ｄ １ ３ ｙ ≡－４ 也即 ） ， １ ２ ０（ ｍ ｏ ｄ １ ３ ｙ ≡１ 由定理 １， 得到 ） ０×１ ≡ ３ （ ｍ ｏ ｄ １ ３ ． ｙ ≡－１ 于是由定理 ２ 的结论可得所给同余式有解
ｍ ａ ｘ ｂ［ ］（ ｍ ｏ ｄ ｍ） ． １ ０ ≡－ ａ
因为
ｍ ｍ ＝ ａ［ ］ ＋ａ １， ａ
也即
ｍ］ ［ ， ａ １ ＝ ｍ －ａ ａ
从而有
ｍ ） ｍ （ ， ｍ －ａ［ ］ ｘ ｂ［ ］（ ｍ ｏ ｄ ｍ） ０ ≡－ ａ ａ
所以
ｍ ｍ ｘ ｂ［ ］（ ｍ ｏ ｄ ｍ） ． －ａ［ ］ ０ ≡－ ａ ａ
） ｍ ｏ ｄ ３ ． ｙ ≡２ （ （ ） 取 ｙ ＝２ ， 可知 ３ 因此所给同余式 ６ １×２＋２ ０， ｜１ 的解为 １ ６ １×２＋２ ０ ） １ ４（ ｍ ｏ ｄ １ ６ １ ． ≡１ ３ 定 理３ 设ａ＞０， 且（ ａ， ｍ） ａ ＝１， １ 是 ｍ 关于模
ｘ≡
且（ 则同余式 ａ 的最小非负剩余 ， ａ ｍ）＝ １， １，
（ ） ３
ａ ｘ０ ≡ｂ （ ｍ ｏ ｄ ｍ） ． ， 因为 ａ 是 关于模 的最小非负剩余 即 ｍ ａ １ ｍ ｍ ＝ ａ［ ］ ＋ａ １， ａ （ ） ， ａ ｍ）＝ １ （ ０ ＜ａ １， １ ＜ａ
所以
ｍ ｂ ， ａ ｘ ≡ ａ× ｙ ＋ ≡ ｍ ｍ ｏ ｄ ｍ） ｙ ＋ｂ ≡ｂ （ ａ 故定理成立 ．
［ １］ 定义 １ 形如
ｘ ≡ｂ ｓ（ ｍ ｏ ｄ ｍ） ．
２ 利用欧拉定理求解
［ １］ （ 定理 １ Ｅ ｕ ｌ ｅ ｒ定理 ） 设 ｍ 是大于 １ 的整数 ，
（ 则 ａ， ｍ）＝ １， （ ） １
φｍ ， ａ ｍ ｏ ｄ ｍ） ≡１ （ 其中 φ（ ｍ）是正整数 ｍ 的欧拉函数值 ． 因为 （ 由最大公因数的性质可知 ａ， ｍ）＝ １， ｍ） φ（ （ ， ａ ｍ）＝ １，
第１ ５ 卷第 ４ 期 ２ ０ １ ２年７月
高 等 数 学 研 究 Ｓ ＴＵＤ Ｉ Ｅ Ｓ Ｉ Ｎ Ｃ Ｏ Ｌ Ｌ Ｅ Ｇ Ｅ ＭＡ ＴＨＥＭＡ Ｔ Ｉ Ｃ Ｓ
Ｖ ｏ ｌ ． １ ５， Ｎ ｏ ． ４ ， Ｊ ｕ ｌ ． ２ ０ １ ２
一次同余式的解法探讨
刘耀斌
（ ） 德州学院 数学系 ，山东 德州 ２ ５ ３ ０ ２ ３ 摘 要 利用同余的性质 ， 得出一次同余式的四种不同解法 ． 根据同余式中模的大小选择适当的解法 ， 能够较
Байду номын сангаас
） ， ， 对 于一次同余式 （ 若ｄ ＝ （ 且ｄ｜ 则 １ ａ， ｍ） ｂ， ， ， ， 将 ａ ｂ ｍ 同除以ｄ 总可以化为如下的一次同余式 ， ， ａ ｘ ≡ｂ （ ｍ ｏ ｄ ｍ） ａ ０ （ ｍ ｏ ｄ ｍ） （ ａ， ｍ）＝ １． （ ） ２
ａ
ｍ） φ（
， ａ ｘ ≡ｂ （ ｍ ｏ ｄ ｍ） ｍ） １ － φ（ （ ， ｘ ≡ｂ ａ ｍ ｏ ｄ ｍ）
又因为
ｍ］ （ ［ ， ｍ）＝ （ ｍ， ａ ＝ １， １） ａ
于是 ， ｘ０ ≡－ｂ （ ｍ ｏ ｄ ｍ） －ａ （ ） （ ） 也即 ｘ ≡ ｘ ｏ ｄ ｍ 是同余式 ６ 的解 ． ０ ｍ
第１ ５ 卷第 ４ 期
刘耀斌 ： 一次同余式的解法探讨
８ １
）与 （ ）等价 ． 综上所述 ， 同余式 （ ５ ６ 根据定理３， 系数为ａ 的同余式可转化为系数更 ）的同余式 ， 小一些 （ 从而易于求解 ． ０ ＜ａ １ ＜ａ 例 ３ 求解同余式 ） ６ ｘ ≡７（ ｍ ｏ ｄ ２ ３ ． 解 因为２ 故所给同余式等价于 ３＝６×３＋５， ） ， ５ ｘ ≡ －７×３ ≡ ２ （ ｍ ｏ ｄ ２ ３ ， 又因 ２ 故上式等价于 ３ ＝ ５×４＋３ ） ， ３ ｘ ≡ －２×４ ≡－８ （ ｍ ｏ ｄ ２ ３ 又因 ２ 故上式等价于 ３ ＝ ３×７＋２， ） ） ， ２ ｘ ≡ －（ ０（ ｍ ｏ ｄ ２ ３ －８ ×７ ≡ １ 又因 ２ 故上式等价于 ３ ＝ ２×１ １＋１， ） ， ｘ ≡ －１ ０×１ １≡５（ ｍ ｏ ｄ ２ ３ 因此所给同余式有解 ） ｘ ≡５（ ｍ ｏ ｄ ２ ３ ． 注 １ 定理３的条件中ａ 是 关于模ａ 的最小 ｍ １ 非负剩余 ， 且（ 若（ 则定理３ ａ ｍ）＝ １． ａ ｍ）≠ １， １， １， 是不成立的 ． 在求解同 余 式 时 ， 同时使用定理１和定理２将 使问题变得更加容易 ． 例 ４ 求解同余式 ） ２ ５ ６ ｘ ≡１ ７ ９（ ｍ ｏ ｄ ３ ３ ７ ． 解 所给同余式的系数 ２ 直接求解 ５ ６ 比较大 ， 故先将系数化小 ． 因为 ３ 不容易 ， ３ ７＝２ ５ ６×１＋８ １，