简化剩余系和欧拉函数共19页

第一章 整数的可除性§1 整除的概念·带余除法 1．证明定理3定理3 若12n a a a ，，，都是m 得倍数，12n q q q ，，，是任意n 个整数，则1122n n q a q a q a +++是m 得倍数．证明：12,,n a a a 都是m 的倍数。

∴ 存在n 个整数12,,n p p p 使 1122,,,n n a p m a p m a p m ===又12,,,n q q q 是任意n 个整数1122n nq a q a q a ∴+++1122n n q p m q p m q p m =+++1122()n n p q q p q p m =+++即1122n n q a q a q a +++是m 的整数2．证明 3|(1)(21)n n n ++ 证明(1)(21)(1)(21)n n n n n n n ++=+++-(1)(2)(1)(1)n n n n n n =+++-+ 又(1)(2)n n n ++，(1)(2)n n n -+是连续的三个整数故3|(1)(2),3|(1)(1)n n n n n n ++-+3|(1)(2)(1)(1)n n n n n n ∴+++-+从而可知3|(1)(21)n n n ++3．若00ax by +是形如ax by +（x ，y 是任意整数，a ，b 是两不全为零的整数）的数中最小整数，则00()|()ax by ax by ++．证：,a b 不全为0∴在整数集合{}|,S ax by x y Z =+∈中存在正整数，因而有形如ax by +的最小整数00ax by +,x y Z ∀∈，由带余除法有0000(),0ax by ax by q r r ax by +=++≤<+则00()()r x x q a y y q b S =-+-∈，由00ax by +是S 中的最小整数知0r =00|ax by ax by ∴++00|ax by ax by ++ （,x y 为任意整数） 0000|,|ax by a ax by b ∴++ 00|(,).ax by a b ∴+ 又有(,)|a b a ，(,)|a b b00(,)|a b ax by ∴+ 故00(,)ax by a b +=4．若a ，b 是任意二整数，且0b ≠，证明：存在两个整数s ，t 使得||,||2b a bs t t =+≤成立，并且当b 是奇数时，s ，t 是唯一存在的．当b 是偶数时结果如何？ 证：作序列33,,,,0,,,,2222b b b b b b ---则a 必在此序列的某两项之间即存在一个整数q ，使122q q b a b +≤<成立 ()i 当q 为偶数时，若0.b >则令,22q qs t a bs a b ==-=-，则有 02222b q q qa bs t ab a b b t ≤-==-=-<∴<若0b < 则令,22q qs t a bs a b =-=-=+，则同样有2b t <()ii 当q 为奇数时，若0b >则令11,22q q s t a bs a b ++==-=-，则有若 0b <，则令11,22q q s t a bs a b ++=-=-=+，则同样有2b t ≤，综上所述，存在性得证．下证唯一性当b 为奇数时，设11a bs t bs t =+=+则11()t t b s s b -=-> 而111,22b bt t t t t t b ≤≤∴-≤+≤ 矛盾 故11,s s t t == 当b 为偶数时，,s t 不唯一，举例如下：此时2b为整数 11312(),,22222b b b b b b b t t ⋅=⋅+=⋅+-=≤§2 最大公因数与辗转相除法 1．证明推论4.1推论4.1 a ，b 的公因数与（a ，b ）的因数相同． 证：设d '是a ，b 的任一公因数，∴d '|a ，d '|b 由带余除法111222111111,,,,,0n n n n n n n n n n a bq r b r q r r r q r r r q r r r r b---++-=+=+=+==≤<<<<∴(,)n a b r =∴d '|1a bq -1r =， d '|122b r q r -=，┄, d '|21(,)n n n n r r q r a b --=+=,即d '是(,)a b 的因数。

欧拉定理与费马小定理
• 若(k,m)=1，则 k m 1modm 。
• 对于素数p和任意的整数a，有 a amod p
p
• 反过来若a和p满足上面的式子，则p几乎一 定是素数（可以用来做素数测试）。
其他公式
若p是一个质数，则：
0mod p (1 k p 1) C 1mod p (k 0或k p)
一元线性同余方程组 与中国剩余定理
问题： 如果m1、m2、…、mk两两互质这个条件不满 足，怎么办？
一元线性同余方程组 与中国剩余定理
如果已知一元线性同余方程组：
x a2 mod m2 ... x ak 1 mod mk 1 x a1 mod m1 x%m1 a1 x%m2 a2 ... x%mk 1 ak 1
商的模与乘法逆元
那么还剩下的问题就是(b,m)=m时的状况。 • 一种策略是想办法得到a和b包含的m因子的个数 ，当a和b都是一列数的连乘时，这个方法是可行 的：
– 首先对m做因式分解。设 若 ，则只需 s k e a ai m mi 要将每个ai包含的mi的因子个数累加一下，最后就能得 i 1 i 1 到a包含的m因子的个数了，并且还可以知道a除开这些 因子之外的部分累乘的积模m的结果。 – 于是当a包含的m的个数大于b时，(a/b)%m=0 – 否则他们包含的m因子的个数一定相等。可以设 b=b’*mk，a=a’*mk ，此时(a/b)%m=(a’/b’)%m，且 b’%m<>0，于是就可以用前几页的方法了。
回到了一元线性同余方程上面来了。 我们已经知道这个同余方程有解当且仅当 (b,m)|a成立，且当此成立时一定有无穷多个 以m/(b,m)为公差的解，且给出一个解就能够 得到所有的解，而要得到一个解只需要用扩 展欧几里德辗转相除法就行。

初 等 数 论 （16）（第二章 同余 第七节 简化剩余系（2））一、复习二、例题例2 什么样的正整数满足ϕ (2x ) = ϕ (3x )解 设x =2a 3b y ，其中ab 为非负整数，y |6/。

若b > 0，（a 、b 大于或等于0）则ϕ (2x ) =ϕ (2a +1) ϕ (3b ) ϕ (y ) =2a ×3b -1×(3-1)ϕ (y )ϕ (3x ) =ϕ (2a ) ϕ (3b +1) ϕ (y ) =2a -1×3b ×(3-1)ϕ (y )这时ϕ (2x )和ϕ (3x )不会相等。

所以在ϕ (2x ) =ϕ (3x )时，b = 0，x =2a y 。

这时，ϕ (2x ) =2a ×ϕ (y )，ϕ (3x ) =2×ϕ (2a )×ϕ (y )由ϕ (2x ) = ϕ (3x )得ϕ (2a ) =2a -1， (a > 0)故 x =2a y ，a 为正整数，y |6/。

例如 x = 215×35，则ϕ (2×215×35) =215×ϕ (35)ϕ (3×215×35) =（3 - 1）×214×ϕ (35)例3 证明：n n 41)(=ϕ不可能成立。

证明 若n n 41)(=ϕ，则n 4。

设 k p p p n αααα 21212=，其中p i 为奇质数，a ≥ 2，则k k p p p n αααα 21212241-=)1()1(2)(111211121--=----k k p p p p p n k ααααϕ，于是 )1()1)(1(22121---=k k p p p p p p上式右边为偶数，左边为奇数，矛盾。

故不存在n ，使得n n 41)(=ϕ。

例4 设m 与n 是正整数，证明：ϕ (mn )ϕ ((m ，n )) = (m ，n )ϕ (m )ϕ (n )。

完系、简系、剩余类定义1．剩余类：把关于模m同余的数归于一类，每类称为一个模m的剩余类. 即由关于模m同余的数组成的集合，每一个集合叫做关于模m的一个剩余类(又叫同余类)．共有m个剩余类.设K r是余数为r的剩余类, 则K r＝{qm＋r| m是模, r是余数, q∈Z}＝{a |a∈Z且a≡r(mod m)}.剩余类的性质：⑴Z＝K0∪K1∪K2∪…∪K m−1，当i≠j时，K i∩K j＝Ø；⑵对于∨−n∈Z，有唯一的r∈{0, 1, 2, …, m−1}，使得n∈K r；⑶对∨−a, b∈Z，a, b∈K r ⇔a≡b (mod m)定义2.完系：设K0，K1，…，K m−1是模m的m个剩余类，从K r中各取一数a r 作为代表，则这样的m个数a0，a1，…，a m−1称为模m的一个完全剩余系，简称m的完系. 例如：1, 2, 3, …, m.若一组数y1, y2, …, y s满足：对任意整数a有且仅有一个y j，使得a≡y j (mod m)，则y1, y2, …, y s是模m的完全剩余系.模m的完全剩余系有无穷多个，但最常用的是下面两个：①最小非负剩余系：0, 1, 2, 3, …, m−1；②最小绝对值剩余系：(随m的奇偶性略有区别) 当m＝2k+1时，为−k, −k+1, …, −1, 0, 1, 2, …, k−1, k；当m＝2k时，为−k+1, −k+2, …, −1, 0, 1, 2, …, k或−k, −k+1, …, −1, 0, 1, 2, …, k−2, k−1.例如，集合{0, 6, 7, 13, 24}是模5的一个完全剩余系，集合{0, 1, 2, 3, 4}是模5的最小非负完全剩余系.性质：(i) m个整数构成模m的一完全剩余系⇔两两对模m不同余；(ii) 若(a, m)＝1，则x与ax＋b同时跑遍模m的完全剩余系.完全剩余系的判断方法：定理1：a1, a2,…, a m是模m的一个完全剩余系⇔a i≡／a j (mod m), i≠j；定理2：设(a, m)＝1, b∈Z, 若x1, x2, , x m是模m的一个完全剩余系，则ax1＋b, ax2＋b, …, ax m＋b也是模m的一个完全剩余系；特别地，m个连续的整数构成模m的一个完系.设K r是模的一个剩余类, 若a, b∈K r，则a≡b(mod m), 于是(a, m)＝(b, m).因此，若(a, m)＝1，则K r中的任一数均与m互质, 这样，又可给出如下定义：定义3.简系：如果r与m互质，那么K r中每一个数均与m互质，称K r为与模m互质的剩余类．这样的剩余类共有φ(m)个，从中各取一个代表(共取φ(m)个)，它们称为模m的简化剩余系，简称简系．当m为质数p时，简系由p−1个数组成．又如：m＝6，在模6的六个剩余类中：K1＝{…, −11, −5, 1, 7, 13,…} K5＝{…, −7, −1, 5, 11, 17,…}是与模6互质的剩余类，数组1, 5；7, −7；1, −1；等等都是模6的简系.性质：①K r与模m互质⇔K r中有一个数与m互质；②与模m互质的剩余类的个数等于φ(m)；③若(a, m)＝1, 则x与ax同时跑遍模m的简化剩余系.简化剩余系的判断方法：定理3：a1，a2，…，aφ(m)是模m的简化剩余系⇔(a i, m)＝1, 且a i≡／a j(mod m) (i≠j, i, j＝1, 2, …, φ(m)).定理4：在模m的一个完全剩余系中,取出所有与m互质的数组成的数组,就是一个模m的简化剩余系.定理5：设(k, m)＝1, 若a1, a2, …, aφ(m)是模m的简系, 则ka1, ka2, …, kaφ(m)也是模m的简系.这三个定理中，定理3与定理5是简化剩余系的判别方法，定理4是它的构造方法. 显然，模m的简化剩余系有无穷多个，但常用的是“最小简化剩余系”，即由1，2，…，m －1中与m 互质的那些数组成的数组.说明：由于任何整数都属于模m 的某一剩余类，所以，在研究某些整数性质时，选取适当的(模)m ，然后在模m 的每个剩余类中取一个“代表数”(即组成一个完全剩余系)，当弄清了这些代表数的性质后，就可弄清对应的剩余类中所有数的性质，进而弄清全体整数的性质，这就是引入剩余类和完全剩余系的目的.例1、设n 为偶数，a 1, a 2,…, a n 与b 1, b 2,…, b n 均为模n 的完全剩余系，试证：a 1＋b 1, a 2＋b 2,…, a n ＋b n 不是模的完全剩余系.证明：假设a 1＋b 1, a 2＋b 2,…, a n ＋b n 是模的完全剩余系. ∴1(1)()1+2++(mod )22n i i i n n n a b n n =++≡≡≡∑ ∵a 1, a 2,…, a n 也是模的完全剩余系. ∴11(1)(mod )22n n i i i n n n a i n ==+≡=≡∑∑，同理有：1(mod )2n i i n b n =≡∑ 1()0(mod )n i i i a b n n =∴+≡≡∑，∴n |n2, 矛盾！故假设不成立，从而原命题成立.例2、设m ＞1, (a , m )＝1，b ∈Z , 求和：∑-=+⋅10}{m i mb i a , 其中{x }为x 的小数部分. 解：∵i 取遍模m 的完系，令x i ＝a ·i ＋b ，则也取遍模m 的完系.故11110000111{}{}{}(1)22m m m m i i i k k x a i b k k m m m m m m m m ----====⋅+-====⨯-=∑∑∑∑总结：若a 1, a 2,…, a m 是模m 的一个完系，则①a 1＋a 2＋…＋a m ≡1＋2＋…＋m (mod m )；②a 1·a 2·……·a m ≡1·2·…·m (mod m )； ③(a 1)n ＋(a 2)n ＋…＋(a m )n ≡1n ＋2n ＋…＋m n (mod m ).例3、已知m , n 为正整数, 且m 为奇数, (m , 2n －1)＝1. 证明：m |∑=m k n k1.证明：∵1, 2, …, m 构成模m 的完系, (m , 2)＝1，∴2, 4, …, 2m 也构成模m 的完系.∴)(mod )2(11m k k m k n m k n ∑∑==≡，即)(mod 0)12(1m k m k n n ≡-∑=. ∵(m , 2n －1)＝1，∴∑=m k n k m 1|得证. 例4、求八个整数n 1, n 2,…, n 8满足：对每个整数k (－2014＜k ＜2014)，有八个整数a 1, a 2,…, a n ∈{−1, 0, 1},使得k ＝a 1n 1＋a 2n 2＋…＋a 8n 8解：令G ＝{k | k ＝a 1＋a 2·2＋a 3·32＋…＋a n +1·3n ，a i ∈{−1, 0, 1}，i ＝1，2，…，n ＋1}.显然max G ＝1＋3＋32＋…＋3n ＝3n +1－12(记为H )，min G ＝－1－3－32＋…－3n ＝－H . 且G 中的元素个数有3n +1＝2H ＋1个， 又∵G 中任意两数之差的绝对值不超过2H ，∴G 中的数对模2H ＋1不同余，∴G 的元素恰好是模2H ＋1的一个绝对值最小的完系，于是凡满足－H ≢k ≢H 的任意整数都属于G ，且可唯一地表示为a 1＋a 2·2＋a 3·32＋…＋a n +1·3n 形式，当n ＝7时，H ＝3208＞2014，而n ＝6时，H ＝1043＜2014，故n 1＝1，n 2＝3，…，n 8＝37为所求.例5、已知p 为大于3的质数，且112＋122＋132＋…＋1(p －1)2＝a b，a ，b ∈N *. (a , b )＝1，证明：p a . 证明：对于不超过p −1的自然数k ，由于(k , p )＝1，所以存在唯一的不超过p −1的自然数x ，满足1(mod )kx p ≡而且，当k ＝1或p −1有x ＝1或p −1，当22k p ≤≤-时，有22,x p x k ≤≤-≠，故当k 取遍1，2，……，p −1时，x 也取遍1，2，……，p −1，因为(,(1)!)1,1(mod )p p kx p -=≡由可得到(1)!(1)!(1)!(mod )(1)!(mod ),p p kx p p p x p k--≡--≡或所以 2211222211((1)!)((1)!)(1)(21)((1)!)((1)!)(mod )6p p k x p a p p p p p x p p b k --==----=≡-≡-∑∑ 因为p 是大于3的素数，所以p −1不小于4，所以(p −1)!含有因数6， 从而2(1)(21)((1)!)0(mod )6p p p p p ---≡，即2((1)!)0(mod )p a p b -≡， 因为(,(1)!)1p p -=，所以2(,((1)!))1p p -=，从而0(mod )0(mod )a p a p b≡⇒≡ 例6、(2003克罗地亚奥林匹克) 对于所有奇质数p 和正整数n (n ≣p )，试证：p n C ≡[n p] (mod p)例7、(第26届IMO) 设n 为正整数，整数k 与n 互质，且0＜k ＜n . 令M ＝{1, 2, …, n −1}(n ≣3), 给M 中每个数染上黑白两种染色中的一种，染法如下：⑴对M 中的每个i ，i 与n −i 同色，⑵对M 中每个i ，i ≠k ，i 与|k −i |同色，试证：M 中所有的数必为同色.证明：∵(k , n )＝1且0，1，2，…，n −1是一个模n 的最小非负完系，∴0·k ，1·k ，2·k ，…，(n −1)·k 也是一个模n 的完全剩余系.若设r j ≡j ·k (mod n )(其中1≢r j ≢n －1，j ＝1，2，…，n －1) ，则M ＝{1，2，…，n −1}＝{121,,,-n r r r } 下面只要证明r j 与r j +1(j ＝1，2，…，n −2)同色即可. 因为若如此，当r 1颜色确定后，M 中所有的数都r 1与同色. 由于(j ＋1)k ≡r j +1(mod n )，则r j ＋k ≡r j +1(mod n )，因此若r j ＋k ＜n ，则r j +1＝r j +k ，由条件⑵知r j +1与| r j +1－k |＝r j 同色；若r j ＋k ＞n ，由r j +1＝r j +k －n ，由条件⑴知k －r j +1＝n —r j 与n －(n —r j )＝r j 同色，即k －r j +1与r j 同色， 由条件⑵知k －r j +1与|k －(k －r j +1)|＝r j +1同色，因此r j +1与r j 同色.综上：此r j +1与r j 同色. 故M 中所有的数必为同色.例8、(2001第42届IMO)设n 为奇数且大于1，k 1, k 2,…, k n 为给定的整数，对于1, 2, …, n 的n !个排列中的每一个排列a ＝(a 1, a 2,…, a n )，记S (a )＝∑=n i i ia k 1，试证：有两个排列b 和c ，使得n !| S (b )－S (c ).证明：假设对任意两个不同的b 和c ，均有S (b )≡／S (c )(mod n !)，则当a 取遍所有1，2，…，n 的n !个排列时， S (a )也取遍模n !的一个完全剩余系，且每个剩余系恰好经过一次，所以()aS a ∑≡1+2+3+…+n !(mod n !)≡12(n !+1)n !≡n !2×n !＋n !2≡n !2(mod n !) (n ＞1)其中()a S a ∑表示对取遍个排列求和(下同)，下面用另一种方法计算1()()ni i a a i S a k a ==∑∑∑：对于k 1，i ∈{1，2，…，n }，a i ＝1时，剩n －1个数，有(n －1)!个排列，a i ＝2时，有(n －1)!个排列，…∴k 1的系数为(n －1)!·(1+2+…+n )＝12(n +1)!. ∴()a S a ∑＝(1)!2n +1n i i k =∑ 但()a S a ∑＝(1)!2n +1n i i k =∑≡0(mod n !) (∵n 为奇数)，∴n !2≡0(mod n !), 矛盾. ∴n !| S (b )－S (c ).例9、设m 是给定的整数. 求证：存在整数a ，b 和k . 其中a ，b 均为奇数，k ≣0，使得2m ＝a 19＋b 99＋k ·21999.另解：设x ，y 为奇数，若x ≡／y (mod 21999)，则x 19－y 19＝(x －y )(x 18＋x 17y ＋…＋xy 17＋y 18)，∵x 18＋x 17y ＋…＋xy 17＋y 18为奇数，∴x 18＋x 17y ＋…＋xy 17＋y 18与21999互质，∴x 19≡／y 19(mod 21999)故当a 取遍模21999的简化剩余系时，a 19也取遍模21999的简化剩余系，∴一定存在a ，使得a 19≡2m －1(mod 21999)，并且有无穷多个这样的a ，故2m －1－a 19＝k ·21999令b ＝1，则2m ＝a 19＋b 99＋k ·21999. 当a 足够小时，不难知k ≣0.。

§3 简化剩余系与欧拉函数定义 欧拉函数()n ϕ是一个定义在正整数集上的函数，()n ϕ的值等于系列0,1,,1n -中与n 互质的整数的个数。

()()()()11,21,32,42,ϕϕϕϕ====当1n >时，()0.n n ϕ<<当p 为质数时，() 1.p p ϕ=-定义 如果一个模m 的剩余类里的数与m 互质（在模m 的一个剩余类中，只要有其中一个数和m 互质，则该剩余类中所有的数就都与m 互质），就把它叫做一个与m 互质的剩余类. 在与m 互质的全部剩余类中，各取一个数所组成的一组数，叫做模m 的一个简化剩余系.定理1 模m 的一个简化剩余系含有()m ϕ个数. 证 模m 的全部剩余类是011,,,m K K K -. 因为,0,1,,1r r K r m ∈=-，所以对每个()01r r m ≤≤-，r K 是一个与m 互质的剩余类的充要条件是(), 1.r m =因此，在模m 的全部剩余类011,,,m K K K -中，与m 互质的全部剩余类是满足条件()01,,1r m r m ≤≤-=的所有剩余类r K . 这样的剩余类公有()m ϕ个，故由简化剩余系的定义知，模m 的简化剩余系含有()m ϕ个数.定理2 若()1,,m a a ϕ是()m ϕ个与m 互质的整数，则()1,,m a a ϕ是模m 的一个简化剩余系的充要条件是它们两两对模m 不同余.证 必要性 设()12,,,m a a a ϕ是模m 的一个简化剩余系，则由简化剩余系的定义，这()m ϕ个数是取自模m 的不同剩余类的，故这()m ϕ个数两两对模m 不同余.充分性 设与m 互质的()m ϕ个整数()12,,,m a a a ϕ两两对模不同余. 因每个整数都与m 互质，故每个整数都属于一个与m 互质的剩余类. 因这()m ϕ个整数两两对模m 不同余，故这()m ϕ个整数分别属于不同的与m 互质的剩余类. 另一方面，与m 互质的剩余类共有()m ϕ个，故()12,,,m a a a ϕ分别属于这()m ϕ个与m 互质的剩余类，故()12,,,m a a a ϕ是模m 的一个简化剩余系.定理3 若(),1,a m x =通过模m 的简化剩余系，则ax 也通过模m 的简化剩余系。

因为n > 4，且n 1与n 1都是奇素数， 所以n是偶数，且n 1 > 3. 所以n 1与n 1都不等于3，也不能被3整除， 所以3n， 因此6n。
1 由结论4， 若6n，则(n) n 3
即可得到结论5。
例3 证明：若m, nN，则(mn) = (m, n)([m, n])； 证： 显然mn与[m, n]有相同的素因数， 设它们是pi（1 i k），则
称为模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。
定理4 设n是正整数，p1, p2, , pk是它的全部素因数，
1 1 则 ( n) n(1 )(1 ) p1 p2
i n p 证 设n的标准分解式是 i
k i 1
i
1 1 (1 ) n (1 ). pk p p|n k
( n ) ( p 由定理3推论得到 i)
定义2 对于正整数k，令函数(k)的值等于模k的所有 简化剩余类的个数，称(k)为Euler函数。 容易验证：(2) = 1，(3) = 2，(4) = 2，(7) = 6。 注：(m)就是在m的一个完全剩余系中与m互素的 整数的个数，且 1 ( m ) m . 定义3 对于正整数m，从模m的每个简化剩余类中 各取一个数xi，构成一个集合{x1, x2, ,x(m)}，

例9 求所有正整数 n, 使得 (2n) (3n)
(Lema) 不存在奇合数
n, 使得
?
(n) | (n 1)
Euler, Fermat 定理 定理6(Euler) 设 m 0, 若
(a, m) 1, 则
a
(m)
1 (mod m)
定理7(Fermat) 设
p 是素数, 则对任意整数a,
2 2 2 p 1 2
例6
证明
61!1 0(mod 71)
定理5 设
p 3 是素数, l 1, c ( p )，以及 l r1 , r2 ,, rc 是模 p 的一个简化剩余系, 则
l
令
r1r2 rc 1(mod p ) rj , 2 | rj rj l rj p , 2 | r j
r1 rc
1(mod 2 )，l 3.
l
m 1,2,4, p ,2 p (p是奇素数)，
l l
模m 的一个简化剩余系的乘积同余-1模m. 其它情形乘积同余1模m.
设
m p p ， p1 , p2 是两个互不相同的奇素数， l1 r1 , r2 ,, rc 是模 p1 的一个简化剩余系, l2 t1 , t2 ,, td 是模 p2 的一个简化剩余系,
剩余类.
给定模 m 的一个简化剩余系
a Z , (a, m) 1, 则 a 恰与其中的一数同余 (mod m).
模
m 的一个简化剩余系 可从模 m 的一个完全
剩余系中取出.
n 1, 1 到 n中与 n互素的数 的个数, 记为 (n), 称为Euler函数.
定义 设
如
(1) 1, (2) 1, (3) 2,

即 (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。
是模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不同余。
① A中含有(m)个整数；
② A中的任何两个整数对模m不同余； ③ A中的每个整数都与m互素。 说明：简化剩余系是某个完全剩余系中的部分元素 构成的集合，故满足条件2； 由定义1易知满足条件3； 由定义3易知满足条件1。
定理2 设a是整数，(a, m) = 1，B = {x1, x2, , x(m)}
因此，集合{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)，
注意：有重素因子时，上述不等式中等号不成立！
三、应用举例
i 1n(n).
例1 设整数n 2，证明： 1in 2
(i ,n)1
即在数列1, 2, , n中，与n互素的整数之和是

(q) 。
证明 因为小于n的正整数个数为pq-1个，其中与n不互素的正 整数有1·p、2·p、…、(q-1)·p和1·q、2·q、…、(p-1)·q，所以
(n)＝ pq-1-((p-1)+(q-1)) =(p-1)(q-1)。
定理1.11 (1)模m简化剩余系含(m)个数。 (2)若a1、a2、…、a(m)是(m)个与m互素的整数，则a1、

证 明 ： p 是 素 数 ， （ a,p ） =1,(b,p)=1,(a+b,p)=1, 证 明 （a+b）p≡ap+bp(mod p) 证明：由费尔马定理，ap ≡amodp,bp ≡bmodp 所以ap + bp ≡ a+bmodp 而（a+b）p ≡ a+bmodp 故得证
Computer Network
Xu Bang-Hai
bhxu@
定义1.5 设(m)为小于或等于m且与m互素的正整数个数，则
称其为欧拉(Euler)函数。（引入目的是问了讨论简化剩余系）
由定义易知，(2)＝1，(3)＝2，(5)＝4，(8)＝4。当P为 素数时，(p)＝p－1。 定理1.10 （1）若p为素数，k为正整数，则(pk)＝pk-1(p－ 1)。 证明 因为小于或等于pk且与pk不互素的正整数有1· 、 p
School of Computer Science & Technology Ludong University
Xu Bang-Hai
bhxu@
例：证明13|42n+1+3n+2(费尔马定理) 证：∵42n+1+3n+2 = 4· n+9· n 16 3 ≡ 4×16+9 ×3≡ 91(mod13) ∴ 13|42n+1+3n+2

定理1表明同余又可定义如下:若m a b, 则a ,b 对模m同余
第5页
丁 同余可以相加减 (i ) 若 a1 b1 (mo d m), a2 b2 (mo d m),
则 a1 a2 b1 b2 ( mo d m) . ( i i ) 若 a b c (mod m),则 a c-b (mod m). 证 由 定 理 1 , a1 b1 m t1, a2 b2 m t2,因 此
证 由 定 理 知 , 存 在 x0, y0,使 得 a x0 m y0 1 . 取 c x0 既 满 足 要 求 .
由 此 提 供 一 种 求 a1(mo d m)有 效 的 方 法 , 这是Euclid算法的又一重要应用.
第11页
显 然 , a 对 模 m的 逆 c不 是 惟 一 的 .当c 是 a 对 模 m 的 逆 时 , 任 一 c ' c (mod m)也 一 定 是 a 对 模 m 的 逆;以 及 由 性 质 VII知 , a 对 模 m 的 任 意 两 个 逆 c1,c2必 有 c1 c2 (mo d m).
第17页
定 义 定 理 1中 的 K0, K1, , Km1叫 做 模 m 的 剩 余 类, 一个剩余类中任一数叫做它同类的数的剩余. 若 a0, a1, , am1是 m 个 整 数,并 且 其 中 任 何 两 数 都 不 同 在 一 个 剩 余 类 里 , 则 a0, a1, , am1叫 做 模 m 的 一 个 完 全 剩 余 系.
壬 若 a b (mod m), d m, d 0,则 a b (mod d ). 癸 若 a b (mod m),则(a, m) (b, m),因 而 若 d 能 整除m 及a,b 二数之一,则d 必能整除a,b中另一个.

(224) 635 193 737 1 取a ' 513 224 (mod 737),则
635 513 1 (mod 737)
13
定理5 设(m1 , m2 ) 1, m1 0, m2 0, 若x1 , x2 分别遍历m1 , m2的简化剩余系,则m2 x1 m1 x2遍历 模m1m2的简化剩余系.
1 1 1 (mod 7), 2 4 1 (mod 7), 3 5 1 (mod 7), 4 2 1 (mod 7), 5 3 1 (mod 7), 6 6 1 (mod 7)
例8 设m 737, a 635,由广义欧几里得除法, 可得整数s 224, t 193,使
((mm22
x1 x1
m1 m1
x2 x2
, m1 , m2
) )
1 1
((mm12
x1 x2
, ,
m1 m2
) )
1 1
因(m1 , m2 ) 1
( (
x1 x2
, ,
m1 m2
) )
1 1
16
四、欧拉函数的性质及计算方法 定理6 (欧拉函数的性质) 若(m, n) 1, 则
(mn) (m) (n).
的简化剩余系.所以( p) p 1.
4
几类特殊的简化剩余系 :
例5 设m是一个正整数,则
(1) m个整数0,1, 2,L , m 1中与m互素的整数全 体组成模m的一个简化剩余系,叫做模m的最小非负 简化剩余系.
(2) m个整数1, 2,L , m 1, m中与m互素的整数全 体组成模m的一个简化剩余系,叫做模m的最小正简 化剩余系.
证 由定理5知,当x, y分别遍历模m, n的简化剩 余系时,nx my遍历模mn的简化剩余系,即nx my 遍历(mn)个整数.

(4)若a1 b1 (mod m), a2 b2 (mod m)，则 a1a2 b1b2 (mod m); 若a b(mod m), 则ak bk (mod m)
（5）若A1 则
1
k
B1 A1
k
(mod m), xi yi (mod m), i 1, 2,
从而 xn ) 3n 2 ( xn 1 xn 1 ) 3n 1 ( xn x1 x1 =x1 3 x1 =x2， ，xn =xn， 同理 x2 即此3n +1 个数中，两两互不相同；
, n 1)时，每一项3i xi 各取3个值， 3x1 x0共通过3n 1 个数；
② 在这3n 1 个数中，若有 3n 1 xn 1 3n xn x0 =3n xn 3n 1 xn 1 3x1 3x1 x0 3n ( xn xn ) 3n 1 ( xn 1 xn 1 ) 则x0 x0 x0 x0 3 x0 x0 x1 ) 3( x1
例：A=28997, B=39495, C=1145236415 AB 之积 为C， 对？
第二节
剩余类及完全剩余系
由带余数除法我们知道，对于给定的正整数m，可以
将所有的整数按照被m除的余数分成m类。本节将对此作 进一步的研究。
定理1
若m是一个给定的正整数，则全部整数可分成 , K m1 , 其中K r (r 0,1, , m 1)是
, m 1, 它们
下面例1给出模m的另外完全剩余系——绝对最小完 全剩余系.
当m是偶数时, m m m , 1, , 1, 0,1, , 1; 2 2 2 m m m 及 1, 1, , 1, 0,1, , 2 2 2 都是模m的完全剩余系.

显 然 , a 对 模 m的 逆 c 不 是 惟 一 的 . 当 c 是 a 对 模 m 的 逆 时 , 任 一 c ' c (mod m)也 一 定 是 a 对 模 m 的 逆;以 及 由 性 质 VII 知 , a 对 模 m 的 任 意 两 个 逆 c1 , c2必 有 c1 c2 (mod m). 此 外 , 显 见 ( a 1 , m ) = 1 及 ( a 1 ) 1 a (mod m)
定 理 1 整 数 a , b 对 模 m同 余 的 充 要 条 件 是 m a b , 即 a b mt , t 是 整 数 . 证 设 a q1m r1 , b q2m r2 ,0 r1 m,0 r2 m, 若 a b (mod m),则 r1 r2 , 因 此 a b (q1 q2 )m. 反 之 若 m a b ,则 m m(q1 q2 ) (r1 r2 ) , 因 此 , m r1 r2 . 但 r1 r2 m ,故 r1 r2 . 定 理 1 表 明 同 余 又 可 定 义 如 下 : 若 m a b, 则 a , b 对 模 m同 余
辛 若 a b (mod mi ), i 1,2, a b (mod [ m1 , m2 ,
, k ,则 , mk ]). , k,再 由 第 一 章
证 由 定 理 1, mi a b , i 1,2, §3 定 理 , 即 得 [ m1 , m2 ,
, mk ] a b ,故 由 定 理1 即 证 得 .
剩余类及完全剩余系
定 理 1 若 m 是 一 个 给 定 的 正 整 数, 则 全 部 整 数 可 分 成 m 个 集 合 , 记 作 K 0 , K1 , , K m1 ,其 中 K r (r 0,1,

欧拉函数的基本性质与应用一．基本原理1.定义：欧拉函数()m ϕ是一个定义在正整数集上的函数,()m ϕ的值等于1,2,,1m -中与m 互素的数的个数.2.计算公式：（1）若p 为素数，则1)(-=p p ϕ（2）若p 为素数，且1)1(1)(--=-⋅=⇒=k kk p p pp p n p n ϕ，形成了一个等比数列. 证明：即证1)(--=a a a pp p ϕ.由)(a ϕ的定义知)(ap ϕ等于从ap 减去ap ，，...1中与ap 不互质的数的个数；亦即等于从ap 减去a p ，，...1中与p 不互质的数的个数.由于p 是质数，故)(a p ϕ等于从ap 减去a p ，，...1中被p 整除的数的个数.由于a p ，，...1中被p 整除的数的个数是1-=⎥⎦⎤⎢⎣⎡a a p p p ，故1)(--=a a a p p p ϕ. （3）已知正整数n 的素因数分解式1212,s s n p p p ααα=其中素数12s p p p <<<, 1.i α≥证明：12111()(1)(1)(1).sn n p p p ϕ=---二．典例分析例1．若正整数m 、n 只有1为公约数，则称m 、n 互质.对于正整数n ，()n ϕ是小于或等于n 的正整数中与n 互质的数的个数.函数()n ϕ以其首名研究者欧拉命名，称为欧拉函数，例如：()32ϕ=，()76ϕ=，()96ϕ=，则下列说法正确的是（ ）A ．()127ϕ=B ．数列(){}3nϕ是等差数列C ．()977log 79log 6ϕ=+ D ．数列()2nnϕ⎧⎫⎪⎪⎨⎬⎪⎪⎩⎭的前n 项和为n S ，则4n S < 解析：对于A 选项，在不超过12的正整数中，与12互质的正整数有：1、5、7、11，故()412ϕ=，A 错；对于B 选项，因为()32ϕ=，()96ϕ=，()2718ϕ=，显然()3ϕ、()9ϕ、()27ϕ不成等差数列，B 错；或者用上面公式：132)311(3)3(-⋅=-⋅=n nnϕ，显然不是等差数列.对于C 选项，7为质数，在不超过97的所有正整数中，能被7整除的正整数的个数为87， 所有与97互质的正整数的个数为9877-，所以，()()9988877777167ϕ=-=-=⨯，因此，()()98777log 7log 678log 6ϕ=⨯=+，C 错；或者用上面公式：89976)711(7)7(⋅=-⋅=ϕ，因此，()()98777log 7log 678log 6ϕ=⨯=+，C 错；对于D 选项，因为2为质数，在不超过2n 的正整数中，所有偶数的个数为12n -，所以，()112222n n n n ϕ--=-=，所以，()122n nn n ϕ-=，则01211232222n n nS -++++=， 所以，121112122222n n nn nS --=++++，上述两个不等式作差可得2111111122121222222212n n n n n nn n n S --+=++++-=-=--，所以，12442n n n S -+=-<，D 对. 或者：若1)1(1)(--=-⋅=⇒=k kkp p pp p n p n ϕ，形成了一个等比数列.故选D. 例2．在数学和许多分支中都能见到很多以瑞士数学家欧拉命名的常数､公式和定理，如：欧拉函数)(n ϕ（n N *∈）的函数值等于所有不超过正整数n 且与n 互素的正整数的个数，（互素是指两个整数的公约数只有1），例如：()11ϕ=；()32ϕ=（与3互素有1､2）；()96ϕ=（与9互素有1､2､4､5､7､8）.记n S 为数列(){}3nn ϕ⋅的前n 项和，则10S =（ ）A ．10191322⨯+ B ．10211322⨯+ C ．11193344⨯+ D ．11211344⨯+ 解析：因为与3n 互素的数为1，2，4，5，7，8，10，11，，31n -，共有123n -⨯，所以()1323n n ϕ-=⨯，则()1323n n n n ϕ-⋅=⨯，于是012123436323n n S n -=⨯+⨯+⨯++⨯①，1232343n S =⨯+⨯+36323n n ⨯++⨯②，由①-②得0121132********2322313nn nn n S n n ---=⨯+⨯+⨯++⨯-⨯=⋅-⨯-，则211322n n n S -=⋅+.于是1010191322S =⨯+.故选：A ． 例3.若正整数m ，n 只有1为公约数，则称m ，n 互质，对于正整数k ，()k ϕ是不大于k 的正整数中与k 互质的数的个数，函数()k ϕ以其首名研究者欧拉命名，称为欧拉函数，例如：()21ϕ=，()32ϕ=，()62ϕ=，()84ϕ=.已知欧拉函数是积性函数，即如果m ，n 互质，那么()()()mn m n ϕϕϕ=，例如：()()()623ϕϕϕ=，则（ ） A ．()()58ϕϕ=B ．数列(){}2nϕ是等比数列C ．数列(){}6nϕ不是递增数列D ．数列()6nn ϕ⎧⎫⎪⎪⎨⎬⎪⎪⎩⎭的前n 项和小于1825 解析：()54ϕ=，()84ϕ=，∴()()58ϕϕ=，A 对；∵2为质数，∴在不超过2n 的正整数中，所有偶数的个数为12n -，∴()112222nnn n ϕ--=-=为等比数列，B 对；∵与3n 互质的数为1，2，4，5，7，8，10，11，…，32n -，31n -.共有()1131323n n ---⋅=⋅个，∴()1323n n ϕ-=⋅，又∵()()()162326n n n n ϕϕϕ-==⋅，∴(){}6n ϕ是递增数列，故C 错误；()1626nn ϕ-=⋅，()6n n ϕ⎧⎫⎪⎪⎨⎬⎪⎪⎩⎭的前n 项和为n S 设01112262626n n n S -=++⋅⋅⋅+⨯⨯⨯，则121116262626nnn S =++⋅⋅⋅+⨯⨯⨯，012215111162626262626n n nn S -=+++⋅⋅⋅+-⨯⨯⨯⨯⨯ 所以01215111162626262626n n nnS -=+++⋅⋅⋅++⨯⨯⨯⨯⨯，1115332616265562616nn n n nn nS ⎛⎫⨯- ⎪⎝⎭=-=--⨯⨯⨯-，所以1818318252565625nn n n S =--≤⨯⨯， 所以数列()6n n ϕ⎧⎫⎪⎪⎨⎬⎪⎪⎩⎭的前n 项和小于1825，故D 正确. 故选：ABD. 三．习题演练1．对于正整数(),n n ϕ是小于或等于n 的正整数中与n 互质的数的数目.函数()n ϕ以其首名研究者欧拉命名，称为欧拉函数，例如()96ϕ=，则（ ）A ．()777log 75log 6ϕ=+ B ．数列(){}3n ϕ为等比数列 C ．数列(){}n ϕ不单调 D ．数列()2nnϕ⎧⎫⎪⎪⎨⎬⎪⎪⎩⎭的前n 项和恒小于4 解析：因为7为质数，所以与77不互质的数为7，14，21，…，77，共有76777=个，所以()()776777log 7log 776log 6ϕ=-=+，故A 错误；因为与3n 互质的数为1，2，4，5，7，8，10，11，…，32n -，31n -，共有11(31)323n n ---⋅=⋅个，所以()1323n n ϕ-=⋅，则数列(){}3n ϕ为等比数列，故B 正确；因为()()62,54ϕϕ==，所以()()65ϕϕ<，故数列(){}n ϕ不单调递增，又因为()96ϕ=>2=()6ϕ,所以数列(){}n ϕ不单调递减，所以数列(){}n ϕ不单调，故C 正确； 因为()122nn ϕ-=，所以()11122222nn ni i ii i i i i iϕ=====∑∑∑. 设21122222nn i n i i n S ===+++∑，则231112122222nn n n nS +-=++++， 所以1231111111121222112222222212n n n n n n n n n S ++++-+=++++-=-=--，所以222n n n S +=-，从而数列()2nn ϕ⎧⎫⎪⎪⎨⎬⎪⎪⎩⎭的前n 项和为122442n n n S -+=-<，故D 正确.故选：BCD.2．若正整数m ，n 只有1为公约数，则称m ，n 互质，对于正整数n ，()n ϕ是小于或等于n 的正整数中与n 互质的数的个数，函数()n ϕ以其首名研究者欧拉命名，称为欧拉函数，例如：()32ϕ=，()76ϕ=，()96ϕ=，则（ ）A ．数列(){}3nϕ为等比数列B ．数列(){}2n ϕ单调递增C ．()777log 76log6ϕ=+D ．数列()2nnϕ⎧⎫⎪⎪⎨⎬⎪⎪⎩⎭的前n 项和为n S ，则n S 的最大值为4解析：与3n 互质的数为1,2,4,5,7,8,10,11,13,,32,31n n --，共有11(31)323n n ---⋅=⋅个，所以()1323nn ϕ-=⋅，因为()()113233233n n n n ϕϕ+-⋅==⋅，所以数列(){}3nϕ为等比数列，因此选项A正确；因为()()()21,42,62ϕϕϕ===，所以数列(){}2n ϕ不是单调递增的，因此选项B 不正确； 因为7是质数，所以与77不互质的数为77,14,21,28,,7，共有7667767-=⋅个，所以()76677777log 7log (67)log6log 7log 66ϕ=⋅=+=+，因此选项C 正确；同理()112222nnn n ϕ--=-=，()11()22n n n n ϕ-=⋅，2111112()3()()222n n n S -=+⋅+⋅++⋅，2311112()3()()222212n n S n =+⋅+⋅++⋅，两式相减，得231111111()()()()2222122n n n S n -=+++++-⋅， 111()122()441221212nn n n n n S n S --+=-⋅⇒=-<-⇒，因此选项D 不正确，故选：AC 3．已知欧拉函数()()*n n N ϕ∈的函数值等于所有不超过正整数n ，且与n 互素的正整数的个数.例如：()11ϕ=，()42ϕ=，设数列{}n a 中：()()*n a n n N ϕ=∈，则（ ）A ．数列{}n a 是单调递增数列B ．{}n a 的前8项中最大项为7aC ．当n 为素数时，1n a n =-D ．当n 为偶数时，2n n a =解析：由题知数列{}n a 前8项为：1,1,2,2,4,2,6,4，不是单调递增数列，故选项A 错误； 由选项A 可知，{}n a 的前8项中最大项为76a =，故选项B 正确； 当n 为素数时，n 与前n 1-个数互素，故1n a n =-，所以C 对正确； 因为62a =，故选项D 错误.附加题1．某软件研发公司计划对某软件进行升级，重要是对软件程序中的某序列{}123,,,A a a a =⋅⋅⋅重新编辑，编辑序列为*324123,,,a a a A a a a ⋅⋅⋅⎧⎫=⎨⎬⎩⎭，它的第n 项为1n na a +，若序列()**A 的所有项均为1，且216a =，312a =，则4a =_________；记数列{}n a 的前n 项之积为n S .则使n S 取得最大值的n 值为_________.（参考数据：lg 20.301≈，lg30.477≈）2．用()g n 表示自然数n 的所有正因数中最大的那个奇数，例如：9的正因数有1、3、9，()99g =，10的正因数有1、2、5、10，()105g =.记()()()()()1232n S n g g g g =++++，则（1）()4S =______.（2）()S n =______.。

定理内容在数论中，欧拉定理（也称费马-欧拉定理）是一个关于同余的性质。

欧拉定理表明，若n,a为正整数，且n,a互素，(a,n) = 1，则a^φ(n) ≡ 1 (mod n)证明首先证明下面这个命题：对于集合Zn={x1,x2,...,xφ(n)},其中xi(i=1,2,…φ(n))是不大于n 且与n互素的数，即n的一个化简剩余系，或称简系，或称缩系)，考虑集合S = {a*x1(mod n),a*x2(mod n),...,a*xφ(n)(mod n)} 则S = Zn1) 由于a,n互质，xi也与n互质，则a*xi也一定于n互质，因此任意xi，a*xi(mod n) 必然是Zn的一个元素2) 对于Zn中两个元素xi和xj，如果xi ≠ xj则a*xi(mod n) ≠ a*xj(mod n)，这个由a、n互质和消去律可以得出。

所以，很明显，S=Zn既然这样，那么（a*x1 × a*x2×...×a*xφ(n)）(mod n)= （a*x1(mod n) × a*x2(mod n) × ... × a*xφ(n)(mod n)）(mod n)= （x1 × x2 × ... × xφ(n)）(mod n)考虑上面等式左边和右边左边等于(a*（x1 × x2 × ... × xφ(n)）) (mod n)右边等于x1 × x2 × ... × xφ(n)）(mod n)而x1 × x2 × ... × xφ(n)(mod n)和n互质根据消去律，可以从等式两边约去，就得到：a^φ(n) ≡ 1 (mod n)推论：对于互质的数a、n，满足a^(φ(n)+1) ≡ a (mod n)费马定理:a是不能被质数p整除的正整数，则有a^(p-1) ≡ 1 (mod p)证明这个定理非常简单，由于φ(p) = p-1，代入欧拉定理即可证明。

欧拉函数（Euler’s Totient Function）背景欧拉函数是数论中的一个重要概念，由瑞士数学家欧拉（Leonhard Euler）于18世纪提出。

欧拉函数是与一个正整数n相关的函数，用φ(n)表示。

欧拉函数的定义是小于或等于n的正整数中与n互质的数的个数。

定义欧拉函数φ(n)的定义如下：φ(n) = 小于或等于n的正整数中与n互质的数的个数其中，互质的定义是指两个数的最大公约数为1。

例如，对于n=8，小于或等于8的正整数中与8互质的数有1、3、5、7，因此φ(8)=4。

用途欧拉函数在数论和密码学等领域具有广泛的应用。

以下是欧拉函数的几个重要用途：1. 素数判定利用欧拉函数可以判断一个数是否为素数。

对于一个正整数n，如果φ(n) = n-1，那么n是素数。

这是因为对于素数n来说，除了1和n本身，没有其他数与n互质。

例如，对于n=7，φ(7)=6，因此7是素数。

2. 快速计算幂的模在密码学中，经常需要求解形如a^b mod m的表达式，其中a、b和m都是正整数。

当b很大时，直接计算a^b可能非常耗时，而利用欧拉函数可以快速计算。

根据欧拉定理，当a和m互质时，有a^φ(m) ≡ 1 (mod m)。

因此，如果b >φ(m)，可以利用欧拉定理将指数b进行简化，即a^b ≡ a^(b mod φ(m)) (mod m)。

这样可以大大减少计算量。

3. 生成RSA公钥RSA加密算法是一种非对称加密算法，广泛应用于信息安全领域。

在RSA算法中，公钥由两个参数组成：一个是模数n，另一个是与n互质的数e，即公钥指数。

生成RSA公钥时，需要选择两个大素数p和q，并计算n=p q。

然后，根据欧拉函数的定义，φ(n) = (p-1)(q-1)。

公钥指数e可以选择与φ(n)互质的数。

4. RSA解密在RSA加密算法中，解密过程需要用到欧拉函数。

解密密文c的公式为：m ≡ c^d (mod n)，其中m是明文，d是私钥指数。

完系、简系、剩余系 知识扫描若按对某一模m 的余数进行分类，就可以引入所谓的剩余类和完全剩余类的概念。

定义2：设m N +∈，把全体整数按其对模m 的余数r （0≤r ≤m-1）归为一类，记为r k ，每一类()0,1,2,,1r k r m =-均称为模m 的剩余类（又叫同余类），同一类中任一数称为该类中另一类数的剩余。

根据定义，剩余类具有如下性质：()()()}{()()0012101=20,1,2,,13,,,mod .m i j r r Z k k k k k k i j n Z r m n k a b Z a b k a b m -⋃⋃⋃⋃⋂=∅≠∀∈∈-∈∀∈∈⇔≡，而对于，有唯一的，使得对定义3：设0121,,m k k k k -是模m 的全部剩余类，从每个r k 中任取一个数r a ，这m 个数0121,,,,m a a a a -组成的一个组称为模m 的一个完全剩余系，简称完系。

显然，模m 的完全剩余系有无穷多个，但最常用的是下面两个：()10,1,21;m -最小非负剩余系：，， ()221m m k =+最小绝对值剩余系：它随的奇偶性不同而略有不同。

当时，为-k,-k+1,,-1,0,1,2,,k-1,k当m=2k 时，为-(k-1),-(k-2),,-1,0,1,2,,k 或-k,-(k-1),,-1,0,,k-1关于完全剩余系，有以下判别法：()()()()121121121,,,,1mod ;2,1,,,,,,,,m m i j m m m m a a a a m i j m a a m b m c a a a a m ba c ba c ba c m --⇔≤<≤≡=+++个整数是模的一个完系当时，设为任意整数，若是模的一个完系，则也是模的一个完系。

特别地，任意m 个连续的整数构成模m 的一个剩余系。

设m 为一正整数，由于在0,1,2，…，m-1中与m 互质的数的个数是由m 唯一确定的一个正整数，因此可以给出以下定义：定义4：m 为一正整数，把0,1,2，…，m-1中与m 互质的数的个数叫做m 的欧拉函数，记为()m 。