《第二节完全剩余系精选》由会员分享，可在线阅读，更多相关《第二节完全剩余系精选（6页珍藏版）》请在金锄头文库上搜索。
1、初等数论第二章同余第二节完全剩余系由带余数除法我们知道，对于给定的正整数m,可以将所有的整数按照被m除的余数分成m类。本节将对此作进一步的研究。一、知识与方法定义1给定正整数m，对于每个整数i，0 i m 1,称集合Ri(m) = n|n i (mod m)， n Z 是模m的一个剩余类。显然，每个整数必定属于且仅属于某一个Ri(m)(0 i m 1)，而且，属于同一剩余类的任何两个整数对模 m是同余的，不同剩余类中的任何两个整数对模m是不同余的。例如，模5的五个剩余类是R0(5)= , 10,5, 0,5, 10,R1(5)=,9 ,4,1 , 6,11,R2(5)= , 8 ,3,2,7,
2、12,R3(5)=, 7 ,2,3,8,13,R4(5)= , 6 ,1 , 4,9,14,。定义2设m是正整数，从模m的每一个剩余类中任取一个数Xi (0 im 1),称集合xo, xi, ,xm 1是模m的一个完全剩余系(或简称为完全系)。由于Xi的选取是任意的，所以模m的完全剩余系有无穷多个，通常称(i )0, 1,2, m 1是模m的最小非负完全剩余系；(11) ? , “1 爭(当 2口)或1,0,1,心(当2|m),是模m的绝对最小完全剩余系。2例如，集合0, 6, 7, 13, 24是模5的一个完全剩余系，集合0, 1,2, 3, 4是模5的最小非 负完全剩余系。定理1整数集合A
3、是模m的完全剩余系的充要条件是(i ) A中含有m个整数；(1) A中任何两个整数对模 m不同余。I. A是棋僭的完全軻余慕*乩热成立*反Z.満足(i)当ii 【证明】 術 创數必莎别来自卜榄w的毎 个半同的剌余类脚足悅卿的完全幕余鼠定理2设m 1, a, b是整数，(a, m) = 1 , X1, X2, , xm是模m的一个完全剩余系， 则ax1 b, ax2 b, , axm b也是模m的一个完全剩余系。【证明】 由定理1,只需证明：若Xi xj，则axi b axj b (mod m)。(1)事实上，若 axi b axj b (mod m),贝V axi axj (mod m),由此
4、及第一节定理 5得到Xi xj (mod m),因此xi = xj。所以式(1)必定成立。证毕。定理 3 设 m1, m2 N , A Z, (A, m” = 1，又设X Xi，X2，,Xmi , Y %,丫2，, ym2,分别是模mi与模m2的完全剩余系，贝yR = Ax miy; x X, y Y 是模mim2的一个完全剩余系。【证明】由定理1只需证明：若x , x X, y , y Y,并且Ax miy Ax miy (mod mim2)，(2)贝 Ux = x ， y = y事实上，由第一节定理5及式(2)，有Ax Ax (mod mi)x x (mod mi)x = x ,再由式(2
5、),又推出miy miy (mod mim2)y y (mod m2)y = y 。证毕。推论 若mi, m2 N, (mi, m2) = i ,则当xi与X2分别通过模 mi与模m2的完全剩余系时， m2xi mi x2通过模mi m2的完全剩余系。定理4 设mi N (i i n),则当Xi通过模mi (i i n)的完全剩余系时，mim2mnixnk i)分别通过模 mi的完全剩余系时,x = xi mix2 mim2X3通过模mim2 mn的完全剩余系。【证明】 对n施行归纳法。当n = 2时，由定理3知定理结论成立。假设定理结论当n = k时成立，即当Xi( 2 iy = X2 m2
6、X3 m2m3X4m2 mkXk i通过模m2m3 mk i的完全剩余系。由定理3,当xi通过模mi的完全剩余系，x (2 i k i) 通过模mi的完全剩余系时，xi miy = xi mi(x2 m2X3m2 mkXk i)=xi miX2 mim2X3mim2 mkXk i通过模mim2 mk i的完全剩余系。即定理结论对于n = k i也成立。定理由归纳法得证。证毕。定理5 设miN,AiZ (i in),并且满足下面的条件(i )(mi, mj)=i ,ii, j n,i j ；(i)(Ai, mi)=i ,ii n;(iii)mi Aj ,ii, jn, i j。则当Xi( iin
7、)通过模mi的完全剩余系Xi时，y = AixiA2X2AnXn通过模mi m2mn的完全剩余系。【证明】由定理i只需证明：若Xi , XiXi,i i n,则由AixiA2X2AnXnAixiA2X2Anxn (mod mi mn) (3)可以得到Xi =xi , i i n。事实上，由条件(ii)及式(3)易得，对于任意的i, i i n,有Aixi Aixi (mod mi)。由此并利用条件(ii)和第一节定理5推得Xi Xi (mod mi),因此 Xi = Xi。证毕。、例题讲解i设A = xi, X2, , xm是模m的一个完全剩余系，以x表示X的小数部分m ax b i证明：若(
8、a, m) = 1，贝U i - (m 1)i i m 2【证明】当x通过模m的完全剩余系时，ax b也通过模m的完全剩余系，因此对于任意的i (1 i m), axi b 一定与且只与某个整数 j (1 j m)同余，即 存在整数k,使得从而axi b = km j， (1 j m)maxi b1mmkj 1mm j川m 1 j1mm 1丄1m(m 1)m 1j 1 mm222设p 5是素数，a 2, 3,p 2 ，则在数列 a，2a，3a，(p 1)a，pa 中有且仅有一个数b，满足 b 1 (mod p)，p 2。aii 1m i m(m 1)i 12(mod m)。同理如果a1mbi(
9、mod m)。(8)b1, a2b2,am bm是模m的完全剩余系，那么也有m(aib)(mod m)。此外，若 b = ka，则 k a，k 2, 3,【解答】设b = ka，那么(i ) ka，否则,b =a21 (mod p)，即 p (a1)(a1)，因此p a 1或p a 1，这与2 a p2矛盾；(丘)k1,否则，b =1 a 1 (mod p)，这与 2a p2矛盾；(iii) k1,否则，b=a 1 (mod p)，这与 2a p2矛盾。若又有k，2 k p2，使得 b k a (mod p)，则k aka (mod p)因(a, p)=：1，所以k k(mod p)，从而 p
10、 k k，这是不可能的。这证明了唯一性。因为(a, p) = 1，所以由定理2，式中的数构成模p的一个完全剩余系，因此必有数满足式(5)3.(Wilson定理)设p是素数，则(p 1)!1 (mod p)。【解答】不妨设p 5。由例2容易推出对于2, 3, , p 2，中的每个整数a，都存在唯一的整数k，2 k p 2，使得ka 1 (mod p)。(6)因此，整数2, 3, p 2可以两两配对使得式(6)成立。所以23 (p 2)1 (mod p)，从而 1 2 3 (p 2)(p1) p 11 (mod p)。4.设m 0是偶数，a1, a2, , am与 b1, b2, , bm都是模m的完全剩余系，证明：a1 b1, a2 b2, , am bm不是模m的完全剩余系【解答】因为1,2, , m与a1, a2, , am都是模m的完全剩余系，所以联合上式与式(7)和式(8)，得到c m m m , x0(mod m),2 22这是不可能的，所以ai bi, a2 b2, , am bm不能是模m的完全剩余系。最新文件仅供参考已改成word文本。方便更改
