02同余(编辑修改稿)内容摘要：
mi ii mba1 2)( (mod m)。 联合上式与式 (7)和式 (8)，得到 0 222 mmm (mod m)， 这是不可能的，所以 {a1 b1, a2 b2, , am bm}不能是模 m的完全剩余系。 习 题 二 1. 证明定理 1。 2. 证明：若 2p 1是奇素数，则 (p!)2 (1)p 0 (mod 2p 1)。 3. 证明：若 p是奇素数， N = 1 2 ( p 1)，则 (p 1)! p 1 (mod N)。 4. 证明 Wilson定理的逆定理：若 n 1，并且 (n 1)! 1 (mod n)， 则 n是素数。 5. 设 m是整数， 4m， {a1, a2, , am}与 {b1, b2, , bm}是模 m的两个完全剩余系，证明： {a1b1, a2b2, , ambm}不是模 m的完全剩余系。 6. 设 m1, m2, ,mn是两两互素的正整数， i（ 1 i n）是整数，并且 i 1 (mod mi)， 1 i n， i 0 (mod mj)， i j， 1 i, j n。 证明：当 bi通过模 mi（ 1 i n）的完全剩余系时， b11 b22 bnn 通过模 m = m1m2 mn的完全剩余系。 50 第三节 简化剩余系 在模 m的完全剩余系中，与 m互素的整数所成的集合有一些特殊的性质，我们要在这一节中对它们做些研究。 定义 1 设 R是模 m的一个剩余类，若有 aR，使得 (a, m) = 1，则称 R是模 m的一个简化剩余类。 显然，若 R是模的简化剩余类，则 R中的每个整数都与 m互素。 例如，模 4的简化剩余类有两个： R1(4) = { , 7 , 3, 1 , 5 , 9 , }， R3(4) = { , 5 , 1 , 3 , 7 , 11 , }。 定义 2 对于正整数 k，令函数 (k)的值等于模 k 的所有简化剩余类的个数，称 (k)为 Euler函数，或 Euler— 函数。 例如，容易验证 (2) = 1， (3) = 2， (4) = 2， (7) = 6。 显然， (m)就是在 m的一个完全剩余系中与 m互素的整数的个数。 定义 3 对于正整数 m，从模 m的每个简化剩余类中各取一个数xi，构成一个集合 {x1, x2, ,x(m)}，称为模 m的一个简化剩余系（或简称为简化系）。 显然，由于选取方式的任意性，模 m的简化剩余系有无穷多个。 例如，集合 {9, 5, 3, 1}是模 8的简化剩余系，集合 {1, 3, 5, 7}也是模 8的简化剩余系，通常称最小非负简化剩余系。 定理 1 整数集合 A是模 m的简化剩余系的充要条件是 (ⅰ ) A中含有 (m)个整数； (ⅱ ) A中的 任何两个整数对模 m不同余； (ⅲ ) A中的每个整数都与 m互素。 证明 留作习题。 定理 2 设 a是整数， (a, m) = 1， B = {x1, x2, , x(m)}是模 m的简化剩余系，则集合 A = {ax1, ax2, , ax(m)}也是模 m的简化剩余系。 证明 显然，集合 A中有 (m)个整数。 其次，由于 (a, m) = 1，所以，对于任意的 xi（ 1 i (m)）， xiB，有 (axi, m) = (xi, m) = 1。 因此，A 中的每一个数都与 m互素。 最后，我们指出， A 中的任何 两个不同的整数对模 m不同余。 事实上，若有 x , x B，使得 a x ax (mod m)， 51 那么，因为 (a, m) = 1，所以 x x (mod m)，于是 x = x 。 由以上结论及定理 1可知集合 A是模 m的一个简化系。 证毕。 注 ：在定理 2的条件下，若 b是整数，集合 {ax1 b, ax2 b, , ax(m) b} 不一定是模 m的简化剩余系。 例如，取 m = 4， a = 1， b = 1，以及模 4的简化剩余系 {1, 3}。 定理 3 设 m1, m2N， (m1, m2) = 1，又设 },{},{ )(21)(21 21 mm yyyYxxxX 与 分别是模 m1与 m2的简化剩余系，则 A = { m1y m2x； xX， yY } 是模 m1m2的简化剩余系。 证明 由第二节定理 3推论可知，若以 X 与 Y 分别表示模 m1与m2的完全剩余系，使得 X X ， Y Y ，则 A = { m1y m2x； xX ， yY } 是模 m1m2的完全剩余系。 因此只需证明 A 中所有与 m1m2互素的整数的集合 R是集合 A。 显然， A A’。 若 m1y m2xR，则 (m1y m2x, m1m2) = 1，所以 (m1y m2x, m1) = 1，于是 (m2x, m1) = 1， (x, m1) = 1， xX。 同理可得到 yY，因此 m1y m2xA。 这说明 R A。 另一方面，若 m1y m2xA，则 xX， yY，即 (x, m1) = 1， (y, m2) = 1。 由此及 (m1, m2) = 1得到 (m2x m1y, m1) = (m2x, m1) = 1 以及 (m2x m1y, m2) = (m1y, m2) = 1。 因为 m1与 m2互素，所以 (m2x m1y, m1m2) = 1，于是 m2x m1yR。 因此 A R。 综合以上，得到 A = R。 证毕。 定理 4 设 m, nN， (m, n) = 1，则 (mn) = (m)(n)。 证明 这是定理 3的直接推论。 证毕。 定理 5 设 n是正整数， p1, p2, , pk是它的全部素因数，则 52 (n) = npk pnpppn |21 )()())((11111111 。 证明 设 n的标准分解式是 n =ki i ip1 ，由定理 4得到 (n) =ki i ip1 )(。 (1) 对任意的素数 p， (p)等于数列 1, 2, , p中与 p（也就是与 p）互素的整数的个数，因此 (p) = p )(][ 111pppppp ， 将上式与式 (1)联合，证明了定理。 证毕。 由定理 5可知， (n) = 1的充要条件是 n = 1或 2。 例 1 设整数 n 2，证明： 1),(1 21ni niin(n)， 即在数列 1, 2, , n中，与 n互素的整数之和是 21 n(n)。 解 设在 1, 2, , n中与 n互素的 (n)个数是 a1, a2, , a(n)， (ai, n) = 1， 1 ai n 1， 1 i (n)， 则 (n ai, n) = 1， 1 n ai n 1， 1 i (n)， 因此，集合 {a1, a2, , a(n)}与集合 {n a1, n a2, , n a(n)}是相同的，于是 a1 a2 a(n) = (n a1) (n a2) (n a(n))， 2(a1 a2 a(n)) = n(n)， 因此 a1 a2 a(n) =21 n(n)。 例 2 设 n是正整数，则 nd d| )( = n， 53 此处 nd|是对 n的所有正约数求和。 解 将正整数 1, 2, , n按它们与整数 n的最大的公约数分类，则 n = ni ndnidni nddndidndi nd ndddn1 |1),( |11),( | |)()(111 。 例 3 设 nN，证明： (ⅰ ) 若 n是奇数，则 (4n) = 2(n)； (ⅱ ) (n) = n21 的充要条件是 n = 2k， kN； (ⅲ ) (n) = n31 的充要条件是 n = 2k3l， k, lN； (ⅳ ) 若 6n，则 (n) n31 ； (ⅴ ) 若 n 1与 n 1都是素数， n 4，则 (n) n31。 解 (ⅰ ) 我们有 (4n) = (22n) = (22)(n) = 2(n)； (ⅱ ) 若 n = 2k，则 (2k) = nkk 2122112 1)( ， 若 (n) = n21 ，设 n = 2kn1， 2| n1，则由 n21 = (n) = (2kn1) = (2k)(n1) =2k 1(n1) =11111 )(21)(221 nnnnnnk 推出 (n1) = n1，所以 n1 = 1，即 n = 2k； (ⅲ ) 若 n = 2k3l，则 (n) = (2k)(3l) = nlk 3131132112 )()( 。 54 若 (n) = n31，设 n = 2k3ln1， 6| n1，则由 1111 )(31)()3()2()32()(31 n nnnnnn lklk 推出 (n1) = n1，所以 n1 = 1，即 n = 2k3l； (ⅳ ) 设 n = 2k3ln1， 6| n1，则 (n) = (2k)(3l)(n1) = nnn lklk 313231)(323111 ； (ⅴ ) 因为 n 4，所以 n 1与 n。阅读剩余 0%
本站所有文章资讯、展示的图片素材等内容均为注册用户上传(部分报媒/平媒内容转载自网络合作媒体)，仅供学习参考。
用户通过本站上传、发布的任何内容的知识产权归属用户或原始著作权人所有。如有侵犯您的版权，请联系我们反馈本站将在三个工作日内改正。