初中数学竞赛教程《同余2》.pdf

橙子奥数工作室 教学档案 非卖品 同 余 续 1 定义五 如果一个模 m 的剩余类 kr中任一数与 m 互质 则称 kr是与模 m 互质的剩余类 在与模 m 互质的每个剩余类中任取一个数 共 m 个 所组成的数组 称为模 m 的一个简 化剩余系 例如 取 m 6 在模 6 的六个剩余类中 13 7 1 5 11 1 k 17 11 5 1 7 5 k是与模 6 互质的剩余类 数组 1 5 7 7 1 1 等等 都是模 6 的简化剩余类 由此定义 不难得到 定理三 12 m a aa 是模 m 的简化剩余系 1 ii a ma 且 mod 1 2 j am ij i jm 定理四 在模 m 的一个完全剩余系中 取出所有与 m 互质的数组成的数组 就是一个 模 m 的简化剩余系 这两个定理 前者是简化剩余系的判别方法 后者是它的构造方法 显然 模 m 的简化 剩余系有无穷多个 但常用的是 最小简化剩余系 即由 1 2 m 1 中与 m 互质的 那些数组成的数组 由定理不难证得简化剩余系的如下性质定理 定理五 设 12 m a aa 是模 m 的简化剩余系 若 k m 1 则 21 m kakaka 也是 模 m 的简化剩余系 下面介绍两个有关欧拉函数的重要结论 其证明略 定理六 欧拉定理 若 a m 1 则 mod1 ma m 特别地 费马小定理 若 m p 为质数 pa 则 mod1 1 pa p 定理七 威尔逊定理 设 p 素数 则 p 1 mod1p 定理八 欧拉函数值计算公式 令 m 的标准分解式为 k k pppm 21 21 则 k i i p mm 1 1 1 例如 30 2 3 5 则 8 5 1 1 3 1 1 2 1 1 30 30 读者应认识到 由于任何整数都属于模 m 的某一剩余类 所以 在研究某些整数性质时 选取适当的 模 m 然后在模 m 的每个剩余类中取一个 代表数 即组成一个完全剩余 系 当弄清了这些代表数的性质后 就可弄清对应的剩余类中所有数的性质 进而弄清全 体整数的性质 这就是引入剩余类和完全剩余系的目的 同余方程 设xaxaxaxaxf n n n n 为 01 1 1 的整系数多项式 类似于多项式和代数方 程式的有关定义 我们有 定义六 同余式 0 mod n f xm a 0 mod m叫做一元 n 次同余方程 例如 3 mod03539 257 xxx是七次同余方程 定义七 若 c 使得 mod mod0 mcxmcf 则成立叫做同余方程 mod0 mxf 的一个解 显然 同余方程的解是一些剩余类 而不仅是一个或 n 个类 例如 5 mod1 x 5 mod4 x都是二次同余方程 5 mod1 2 x的解 1 一次同余方程 modmbax 其中 ma 称为一次同余方程 关于它的解 有如下共知的结论 定理九 若 a m 1 则 modmbax 有一个解 定理十 若 a m d 1 db 则 modmbax 无解 其中a 0 mod m 定理十一 若 a m d 1 d b 则 modmbax 有 d 个解 并且 若 mod 1 mx 的一个解为 mod 1 mrx 则 d 个解为 1 1 0 mod 1 dkmkmrx 其中 1 d m m d b d a 下面介绍一次同余方程 1 mod mambax 的解法 解法 1 因 a m 1 则存在二数 s t 使得 as mt 1 即 mod1mas 由此有 mod modmbsxmbsasx 于是为 的解 解法 2 先把 变形成 a b m a b x mod 仅只是形式上的记号 然后用与 m 互质 的数陆续乘右端的分子分母 直至把分母绝对值变成 1 通过分子分母各对模 m 取余数 而 得到解 解法 3 得用欧拉定理 因 mod mod mod1 1 mabxambaxma mmm 可得由 从而有解 mod 1 mabx m 2 一次同余方程组 定义八 若数 r 同时满足 n 个同余方程 rnkmxf kk 则 2 1 mod0 叫做这 n 个同余方程组成的同余方程组的解 定理十二 对同余方程组 mod mod 22 11 mcx mcx 记 2121 Mmmdmm 若 12 dcc 则此同余方程组无解 若 21 ccd 则此同余方程组有对模 M 的一类剩余解 模 m 的阶和中国剩余定理 1 模 m 的阶 定义九 设 m 1 是一个固定的整数 a 是与 m 互素的整数 则存在整数 k 1 k m 使得 mod1ma k 我们将具有这一性质的最小正整数 仍记为 k 称为 a 模 m 的阶 a 模 m 的阶具有如下性质 设 makma模是 1 的阶 u是任意整数 则 modmaa vu 的充要条件是 modku 特别地 mod1mau 的充分必要条件是 k u 简证 充分性显然 必要性 设u 记lu 则由 mod u aam 及 1a m 易知1 mod l am 用 带余除法 lkqr 这里0rk 故1 mod kqr aam 即1 mod r am 由 0rk 及 k 的定义知 必须 r 0 所以 modkru 设ama 2 模 m 的阶为 k 则数列 32 aaa模 m 是周期的 且最小正周期是 k 而 k 个数 k aaa 2 模 m 互不同余 设ama则 1 模 m 的阶整除欧拉函数 m 特别地 若 m 是素数 p 则 a 模 p 的 阶整除 p 1 2 中国剩余定理 即孙子定理 设 n mmmn 2 21 是两两互质的正整数 记 M n i i ii ni m M Mm 1 2 1 则 同余方程组 2 1 modnimcx ii 有且只有解 n i iii McMx 1 mod 其中 2 1 mod1nimM iii 证明 由 1 jimm ji 知 1 ji mM 因此每一个同余方程 mod1 iiy mM i 1 2 n 都 有 解 于 是 必 存 在 i 使 得1 mod ii Mm 又 因 iiii Mm M mM ij 所以对模 1 2 i m in 有 1