- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
i 1 i 1 i 1
m
m
m
通过模m2m3mk 1的完全剩余系。
18
y = x2 m2x3 m2m3x4 m2mkxk 1
通过模m2m3mk 1的完全剩余系。 由定理4，当x1通过模m1的完全剩余系，
xi（2 i k 1）通过模mi的完全剩余系时， x1 m1y = x1 m1(x2 m2x3 m2mkxk 1)
从而
3、剩余系间的联系
定理4 设m1, m2N，AZ，(A, m1) = 1， X { x1 , x2 , , xm1 } ,Y { y1 , y2 , , ym2 } 分别是模m1与模m2的完全剩余系， 则 R = { Ax m1y：xX，yY }是模m1m2的一个 完全剩余系。 证明 由定理3只需证明：若x , x X，y , y Y，且 Ax m1y Ax m1y (mod m1m2)， 则 x ' x ", y ' y " [ R中有m1m2个元素].
13 14
定理5 设miN，AiZ（1 i n），并且满足： ① (mi, mj) = 1，1 i, j n，i j； ② (Ai, mi) = 1，1 i n； ③ miAj ，1 i, j n，i j 。 则当xi（1 i n）通过模mi的完全剩余系Xi时， y = A1x1 A2x2 Anxn 通过模m1m2mn的 完全剩余系。
检验：设{x1, x2, , xm}是模m的一个完全剩余系， 那么，{b+x1, b+x2, , b+ xm}和 {ax1, ax2, ,a xm} 是模m的一个完全剩余系吗？ m 6, b 2 m 5, b 2 m 5, a 2 m 6, a 2
定理3 设m 1，a，b是整数，(a, m) = 1，{x1, x2, , xm} 是模m的一个完全剩余系，则 {ax1 b, ax2 b, , axm b}也是模m的完全剩余系。 证明 由定理2，只需证明：若xi xj，1 i , j m 则 axi b axj b (mod m)。 假设 axi b axj b (mod m)， 则 axi axj (mod m)， 且(a, m) = 1， 由§3.1中的结论,P50第三行知： xi xj (mod m) xi x j .
2、完全剩余系的构造 定理2 整数集合A是模m的完全剩余系的充要条件是
① A中含有m个整数； ② A中任何两个整数对模m不同余。 注：由定理1及定义2易得证。 思考：1、既然完全剩余系是不唯一的，不同的剩余系 之间存在什么关系呢？ 2、一个完全剩余系的所有元素通过线性变化 后，还是完全剩余系吗？
5 6
设m Z ，则全部整数分别在模m的m个剩余类K r (m)里.
其中，K r ( m ) n : n r (mod m ) 0 r m 1,
并且
(1) 任一整数n必包含且仅包含在某个K r ( m )里；
(2)设 a , b Z，则a , b K r ( m ) a b(mod m ).
练 1.求证对任何正整数n, 都存在仅有数字0和1组成 习 的数a , 使得n a . 2.(1)写出模7的一个完全剩余系,每个数都是奇数. (2)写出模7的一个完全剩余系,每个数都是偶数. 3.任意两组模m的完全剩余系, 它们各自元素之和对
= x1 m1x2 m1m2x3 m1m2mkxk 1 通过模m1m2mk 1的完全剩余系。 即结论对于n = k 1也成立。
10
例2 设A = {x1, x2, , xm}是模m的一个完全剩余系， 以{x}表示x的小数部分，证明：若(a, m) = 1，则 m { axi b } 1 (m 1) m 2 i 1 证： 当x通过模m的完全剩余系时，ax b也通过 模m的完全剩余系， 因此对于任意的i（1 i m），axi b一定且只与 某个整数j（1 j m）同余， 即存在整数k，使得 axi b = km j，（1 j m）
K r ( m ) n : n r (mod m ) 是模m的一个剩余类，
即 余数相同的整数构成m的一个剩余类。 一个剩余类中任意一个数称为它同类的数的剩余。
1
2
证 : (1)设a是任一整数,由带余除法即得 a a1m ra ,0 ra m .
二、完全剩余系
故a在K ra内, 又ra 是由a唯一确定的,因此a只能在K ra内. (2)设a , b是两个整数 , 并且都在K r内, 则 a q1m r , b q2 m r ,
推论 若m1, m2N，(m1, m2) = 1，当x1与x2分别通过 模m1与模m2的完全剩余系时， 则 m2x1 m1x2通过模m1m2的完全剩余系。 注：即在定理4中取A m2 .
m1y m1y (mod m1m2) y y (mod m2) y = y 。
12
{
m m m 1 axi b } {k j } { j } { j } m m i 1 j 1 j 1 m j 1 m m 1 1 m ( m 1) m 1 j . 2 2(A, m1) = 1， X { x1 , x2 , , xm1 } ,Y { y1 , y2 , , ym2 } 分别是模m1与模m2的完全剩余系， 则 R = { Ax m1y：xX，yY }是模m1m2的一个 证：Ax m1y Ax m1y (mod m1m2)， Ax m1y Ax m1y (mod m1)， 由 m1 m1 y '，m1 m1 y ''，所以 Ax Ax (mod m1) x x (mod m1) x = x ， 由x = x ， Ax m1y Ax m1y (mod m1m2)，
证： 由定理3只需证明，若xi, xiXi，1 i n， A1x1 A2x2 Anxn A1x1 A2x2 Anxn (mod m1mn) 则 可以得到 xi = xi，1 i n. 事实上，由条件3假设易得， 对于任意的i，1 i n，有 Aixi Aixi (mod mi)〔证明方法同定理4〕。 再利用条件2推得 xi xi (mod mi)， 因此xi = xi.
15 16
4
例3 设m > 0是偶数，{a1, a2, , am}与{b1, b2, , bm} 都是模m的完全剩余系， 则{a1 b1, a2 b2, , am bm}不是模m的完全剩余系。 证 由{1, 2, , m}与{a1, a2, , am}都是模m的完全剩余系
m m(m 1) m m (modm) 同理， bi (mod m) 2 2 2 i 1 i 1 i 1 如果{a1 b1, a2 b2, , am bm}是模m的完全剩余系， m m
y = x2 m2x3 m2m3x4 m2mkxk 1
所以， ai i
m
m 则 (ai bi ) (mod m ) 2 i 1
不可能！
m m m m (mod m) 2 2 2 2
17
从而0 = ai bi (ai bi )
m m 1, , 1, 0, 1, , } 2 2 m m 和{ , , 1, 0, 1, , 1 } 2 2 都是模m的绝对最小完全剩余系。
{ 当 2 | m时，
{ 当 2 m时，
m 1 m 1 } , , 1, 0, 1, , 2 2 是模m的绝对最小完全剩余系。
注：① 完全剩余系不唯一； ② {0, 1, 2, , m 1}是模m的最小非负完全剩余系； ③ 若把剩余系作为一个集合，则可以把对模m的余 数相同的整数——即同一剩余类里的整数，看作同 一元素。
3
4
1
完全剩余系举例： 集合{0, 6, 7, 13, 24}是模5的一个完全剩余系， 集合{0, 1, 2, 3, 4}是模5的最小非负完全剩余系。
19
模m同余. 4. x 2 mod 3 , x 2
mod 4 x 2 mod 5 , x 2 mod 8 x 4 mod 5 , x 4 mod 8
5.设n 1, b的素因数都大于n, 证明 : 对任何正整数a , 有 n ! a a b a 2b 20 a n 1 b .
5
1解 : 考察1,11,111, ,11 1 这n 1个数 ,
n 1个
4解 : 0,1 0,1 0,1,4 0,1,4 0,1 0,1 5证 :由条件知 b, n ! 1, 故存在c , 使bc 1 mod n !
p是素数，a p ( a , p ) 1
则ax+b也通过模m的一个完全剩余系； （3）特别地，若x通过模m的一个完全剩余系， (a, m) = 1，，则ax和x+b也分别通过模m的一 个完全剩余系。
9
所以｛a，2a，3a，，(p 1)a，pa｝构成模p的 一个完全剩余系。 因此必有唯一的数b满足式b 1 (mod p)。
§3.2 剩余类与完全剩余系 一、剩余类 ——按余数的不同对整数分类 定理1
一个整数被正整数n除后，余数有n种情形：0，1，2， 3，…，n-1，它们彼此对模n不同余。这表明，每个 整数恰与这n个整数中某一个对模n同余。这样一来， 按模n是否同余对整数集进行分类，可以将整数集分 成n个两两不相交的子集。 定义1 给定m Z , 对每个r Z ,0 r m 1, 称集合
7
8
2
