剩余系与欧拉函数 课件 (1)

课件19张PPT。剩余系与欧拉函数 一、基本概念定义1 设R是模m的一个剩余类，若有a?R，使得(a, m)= 1，则称R是模m的一个简化剩余类。即与模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函数。容易验证：?(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, 3, 5, 7}称为最小非负简化剩余系。 二、主要性质 定理1 整数集合A是模m的简化剩余系的充要条件是：① A中含有?(m)个整数；② A中的任何两个整数对模m不同余；③ A中的每个整数都与m互素。说明：简化剩余系是某个完全剩余系中的部分元素构成的集合，故满足条件2； 由定义1易知满足条件3；由定义3易知满足条件1。定理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)），xi?B， 有(axi, m) = (xi, m) = 1。 故A中的每一个数都与m互素。 而且，A中的任何两个不同的整数对模m不同余。 因为，若有x ?, x ???B，使得 a x ? ? ax ?? (mod m)，那么， 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}。但｛2，4｝不是模4的简化剩余系。定理3 设m1, m2?N，(m1, m2) = 1，又设分别是模m1与m2的简化剩余系， 则 A = { m1y ? m2x；x?X，y?Y }是模m1m2的简化剩余系。证明 由第二节定理3推论可知， 若以X ?与Y ?分别表示 模m1与m2的完全剩余系，使得X ? X ?，Y ? Y ?， 则A ? = { m1y ? m2x；x?X ?，y?Y ? }是模m1m2的完全
剩余系。 因此只需证明A ?中所有与m1m2互素的整数的集合R 即模m1m2的简化剩余系是集合A。 若m1y ? m2x?R，则(m1y ? m2x, m1m2) = 1， 所以(m1y ? m2x, m1) = 1， 于是 (m2x, m1) = 1，(x, m1) = 1，x?X。同理可得到y?Y，因此m1y ? m2x?A。 这说明R ? A。 另一方面，若m1y ? m2x?A，则x?X，y?Y， 即 (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 ? m1y?R。因此A ? R。 从而A = R。 推论 设m, n?N，(m, n) = 1，则?(mn) = ?(m)?(n)。证 由定理3知，若x,y分别通过m , n的简化剩余系， 则my ? nx通过mn的简化剩余系， 即有 my ? nx通过?(mn)个整数。 另一方面，x〔nx〕通过?(m)个整数， y〔my〕通过?(n)个整数, 从而my ? nx通过?(m) ?(n)个整数。故有 ?(mn) = ?(m)?(n)。注：可以推广到多个两两互质数的情形。定理4 设n是正整数，p1, p2, ?, pk是它的全部素因数， 证 设n的标准分解式是 由定理3推论得到 对任意的素数p， ?(p?)等于数列1, 2, ?, p?中与p?互素的整数的个数， 从而定理得证。注：由定理4可知，?(n) = 1的充要条件是n = 1或2。考虑有重素因子和没有重素因子的情形。 三、应用举例注意：有重素因子时，上述不等式中等号不成立！例1 设整数n ? 2，证明： 即在数列1, 2, ?, 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)}故 a1 ? a2 ? ? ? a?(n) = (n ? a1) ? (n ? a2) ? ? ? (n ? a?(n))，从而，2(a1 ? a2 ? ? ? a?(n)) = n?(n)，因此 a1 ? a2 ? ? ? a?(n) 与集合{n ? a1, n ? a2, ?, n ? a?(n)}是相同的，例2 设n?N，证明：1) 若n是奇数，则?(4n) = 2?(n)；1) 若n是奇数，则?(4n) = 2?(n)；?(4n) = ?(22n)= ?(22)?(n)= 2?(n)〔TH4〕若n = 2k， 由 ?(n) = ?(2kn1) = ?(2k)?(n1) =2k ? 1?(n1) 所以n1 = 1，即n = 2k；所以n1 = 1，即n = 2k3l；若 n = 2k3l，则 ?(n) = ?(2k)?(3l)则 ?(n) = ?(2k)?(3l)?(n1) 因为n > 4，且n ? 1与n ? 1都是奇素数， 所以n是偶数，且n ? 1 > 3.所以n ? 1与n ? 1都不等于3，所以3?n，由结论4，也不能被3整除，因此6?n。即可得到结论5。例3 证明：若m, n?N，则?(mn) = (m, n)?([m, n])；证： 显然mn与[m, n]有相同的素因数， 设它们是pi（1 ? i ? k），则由此两式及mn = (m, n)[m, n]即可得证。课件19张PPT。剩余系与欧拉函数 一、基本概念定义1 设R是模m的一个剩余类，若有a?R，使得(a, m)= 1，则称R是模m的一个简化剩余类。即与模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函数。容易验证：?(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, 3, 5, 7}称为最小非负简化剩余系。 二、主要性质 定理1 整数集合A是模m的简化剩余系的充要条件是：① A中含有?(m)个整数；② A中的任何两个整数对模m不同余；③ A中的每个整数都与m互素。说明：简化剩余系是某个完全剩余系中的部分元素构成的集合，故满足条件2； 由定义1易知满足条件3；由定义3易知满足条件1。定理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)），xi?B， 有(axi, m) = (xi, m) = 1。 故A中的每一个数都与m互素。 而且，A中的任何两个不同的整数对模m不同余。 因为，若有x ?, x ???B，使得 a x ? ? ax ?? (mod m)，那么， 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}。但｛2，4｝不是模4的简化剩余系。定理3 设m1, m2?N，(m1, m2) = 1，又设分别是模m1与m2的简化剩余系， 则 A = { m1y ? m2x；x?X，y?Y }是模m1m2的简化剩余系。证明 由第二节定理3推论可知， 若以X ?与Y ?分别表示 模m1与m2的完全剩余系，使得X ? X ?，Y ? Y ?， 则A ? = { m1y ? m2x；x?X ?，y?Y ? }是模m1m2的完全
剩余系。 因此只需证明A ?中所有与m1m2互素的整数的集合R 即模m1m2的简化剩余系是集合A。 若m1y ? m2x?R，则(m1y ? m2x, m1m2) = 1， 所以(m1y ? m2x, m1) = 1， 于是 (m2x, m1) = 1，(x, m1) = 1，x?X。同理可得到y?Y，因此m1y ? m2x?A。 这说明R ? A。 另一方面，若m1y ? m2x?A，则x?X，y?Y， 即 (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 ? m1y?R。因此A ? R。 从而A = R。 推论 设m, n?N，(m, n) = 1，则?(mn) = ?(m)?(n)。证 由定理3知，若x,y分别通过m , n的简化剩余系， 则my ? nx通过mn的简化剩余系， 即有 my ? nx通过?(mn)个整数。 另一方面，x〔nx〕通过?(m)个整数， y〔my〕通过?(n)个整数, 从而my ? nx通过?(m) ?(n)个整数。故有 ?(mn) = ?(m)?(n)。注：可以推广到多个两两互质数的情形。定理4 设n是正整数，p1, p2, ?, pk是它的全部素因数， 证 设n的标准分解式是 由定理3推论得到 对任意的素数p， ?(p?)等于数列1, 2, ?, p?中与p?互素的整数的个数， 从而定理得证。注：由定理4可知，?(n) = 1的充要条件是n = 1或2。考虑有重素因子和没有重素因子的情形。 三、应用举例注意：有重素因子时，上述不等式中等号不成立！例1 设整数n ? 2，证明： 即在数列1, 2, ?, 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)}故 a1 ? a2 ? ? ? a?(n) = (n ? a1) ? (n ? a2) ? ? ? (n ? a?(n))，从而，2(a1 ? a2 ? ? ? a?(n)) = n?(n)，因此 a1 ? a2 ? ? ? a?(n) 与集合{n ? a1, n ? a2, ?, n ? a?(n)}是相同的，例2 设n?N，证明：1) 若n是奇数，则?(4n) = 2?(n)；1) 若n是奇数，则?(4n) = 2?(n)；?(4n) = ?(22n)= ?(22)?(n)= 2?(n)〔TH4〕若n = 2k， 由 ?(n) = ?(2kn1) = ?(2k)?(n1) =2k ? 1?(n1) 所以n1 = 1，即n = 2k；所以n1 = 1，即n = 2k3l；若 n = 2k3l，则 ?(n) = ?(2k)?(3l)则 ?(n) = ?(2k)?(3l)?(n1) 因为n > 4，且n ? 1与n ? 1都是奇素数， 所以n是偶数，且n ? 1 > 3.所以n ? 1与n ? 1都不等于3，所以3?n，由结论4，也不能被3整除，因此6?n。即可得到结论5。例3 证明：若m, n?N，则?(mn) = (m, n)?([m, n])；证： 显然mn与[m, n]有相同的素因数， 设它们是pi（1 ? i ? k），则由此两式及mn = (m, n)[m, n]即可得证。