- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
若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得到
故a1a2a(n)= (na1)(na2) (na(n))，
从而，2(a1a2a(n))=n(n)，
因此a1
a2a(n)
1 n(n).
2
课后练习
练习1 求(30的值。
解：(30)=(2×3×5) =(2) (3) (5) =1×2×4=8，所以(30) =8。我们可以
i 1
(p)等于数列1，2，，p中与p互素的整数的个数，
[ ] ( ) 因此，( p ) p p p p1 p 1 1
p
p
ห้องสมุดไป่ตู้
从而定理得证。
TH 4即为：(n)
n(1
1 ),
p
p为n的质因数.
注：由定理4可知，(n) = 1的充要条件是n = 1或2。
定理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，
注：在定理2的条件下，若b是整数，集合
{ax1 b，ax2 b，，ax(m) b} 不一定是模m的简化剩余系。 例如，取m = 4，a = 1，b = 1， 以及模4的简化剩余系{1, 3}。 但｛2，4｝不是模4的简化剩余系。
定理3 证明
设m1, m2N，(m1, m2) = 1，又设 X { x1, x2 , , x (m1 ) } 与 Y { y1, y2 , , y(m2 ) } 分别是模m1与m2的简化剩余系，
证 由定理3知，若x，y分别通过m，n的简化剩余系， 则my nx通过mn的简化剩余系，
即有 my nx通过(mn)个整数。 另一方面，x〔nx〕通过(m)个整数，
y〔my〕通过(n)个整数, 从而my nx通过(m) (n)个整数。 故有 (mn) = (m)(n)。
注：可以推广到多个两两互质数的情形。
a1, a2, , a(n), (ai, n) = 1, 1 ai n 1, 1 i (n)，
则 (nai，n) =1，1 nai n1，1 i (n)，
因此，集合{a1，a2，，a(n)}
与集合{n a1，n a2， ，n a(n)}是相同的，
k
因为n pi i 1
( ) ( ) ( ) k
(n) n
1 1
i 1
pi
k
k
1
pi
i1 i1
1 pi
k
i 1
pi 1
考虑有重素因子和没有重素因子的情形。
注意：有重素因子时，上述不等式中等号不成立！
例题讲解
例1 求(10)， (12) 的值。
解：在1-9中，与10互素的数有1，3，7，9，所
有(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的一个简化系。
剩余系和欧拉函数
要点提炼 几个定义的理解
欧拉函数：函数(k)表示1，2，…， k-1中与k互素 的数的个数，其中(1)=1。 容易验证：(2) = 1，(3) = 2，(4) = 2，(7) = 6。
简化剩余类：设R是模m的一个剩余类，若有aR， 使得 (a, m)= 1，则称R是模m的一个简化剩余类。 即与模m互质的剩余类。 注：若R是模的简化剩余类，则R中的数都与m互素。 例如，模4的简化剩余类有两个：
R1(4) = { , 7 , 3, 1 , 5 , 9 , }， R3(4) = { , 5 , 1 , 3 , 7 , 11 , }。
简化剩余系：对于正整数m，从模m的每个简化
剩余类中各取一个数xi，构成一个集合{x1，x2， ，x(m)}，称为模m的一个简化剩余系（或简称 为简化系）。
p1
p2
pk
([m,n]) [m,n](1 1 )(1 1 ) (1 1 ).
p1
p2
pk
由此两式及mn = (m, n)[m, n]即可得证。
谢 谢！
验证一下：在1-29中与30互素的数有： 1，7，11，13，17，19，23，29。
练习2 证明：若m, nN，则(mn) = (m, n)([m, n])。
证： 显然mn与[m, n]有相同的素因数，
设它们是pi（1 i k），则
(mn) mn(1 1 )(1 1 ) (1 1 )，
以(10)=4，在 1-11，与12互素的数有1，5，7， 11， 所以(12) =4。
例2
设整数n 2，证明： 1 i n
i
1n (n).
2
(i ,n)1
即在数列1, 2, , n中，与n互素的整数之和是 1 n(n).
2
证 设在1, 2, , n中与n互素的个数是(n)，
值等于模k的所有。
简化剩余类的个数，称(k)为欧拉（Euler）函数。 注：(m)就是在m的一个完全剩余系中与m互素的
整数的个数，且 1 (m) m.
理解定理
定理1 整数集合A是模m的简化剩余系的充要条件是：
① A中含有(m)个整数；
② A中的任何两个整数对模m不同余； ③ A中的每个整数都与m互素。 说明：简化剩余系是某个完全剩余系中的部分元素 构成的集合，故满足条件2； 由定义1易知满足条件3； 由定义3易知满足条件1。
定理4 设n是正整数，p1，p2，，pk是它的全部素因数，
( ) 则 (n) n(1 1 )(1 1 ) (1 1 ) n 1 1 .
p1
p2
pk
p|n
p
k
证 设n的标准分解式是 n
p i i
i 1 k
由定理3推论得到 (n)
(
pi i
)
对任意的素数p，
则 A = { m1y m2x；xX，yY }
是模m1m2的简化剩余系。 由第二节定理3推论可知，若以X 与Y 分别表示
模m1与m2的完全剩余系，使得X X ，Y Y ， 则A = { m1y m2x；xX ，yY }是模m1m2的完全
剩余系。
因此只需证明A 中所有与m1m2互素的整数的集合R 即模m1m2的简化剩余系是集合A。
(m2x m1y, m1) = (m2x, m1) = 1
(m2x m1y, m2) = (m1y, m2) = 1。
因为m1与m2互素，所以(m2x m1y, m1m2) = 1， 于是m2x m1yR。因此A R。从而A = R。
推论 设m，nN，(m, n) = 1，则(mn) = (m)(n)。
注：由于选取方式的任意性，模m的简化剩余系 有无穷多个。
例如，集合{9, 5, 3, 1}是模8的简化剩余系； 集合{1,3,5,7}也是模8的简化剩余系。 集合{1,3,5,7}称为最小非负简化剩余系。
在学习了简化剩余类的定义之后，我们还可以这
样来理解欧拉函数：对于正整数k，令函数(k)的
