完系、简系

简单系纱巾方法教程引言纱巾是一种潮流时尚的配饰，可以为你的造型增添亮点。

而且，系纱巾是一个非常简单且灵活的过程，只需几步就能完成。

本文将介绍一些简单的系纱巾方法，帮助你轻松打造不同风格的造型。

方法一：经典三角巾步骤1：将纱巾折叠成三角形将纱巾展开，将两角对折成对角线，然后将纱巾再次对折成一个更小的三角形。

确保纱巾的三角形边缘是齐平的。

步骤2：将纱巾围绕脖子将纱巾的长边放在你的脖子后面，让三角形的尖端指向你的身体。

然后将两边折叠到胸前，将尖端藏在折叠处。

步骤3：调整形状根据个人喜好和造型需要，微调纱巾的位置和形状。

你可以让它紧贴脖子，也可以让它稍微松散。

使用纱巾的边缘来覆盖折叠处，使造型更加完美。

方法二：蝴蝶结系法步骤1：将纱巾折叠成长条形将纱巾展开，将两角对折成对角线，然后将纱巾再次对折成一个更长的矩形。

确保纱巾的边缘是齐平的。

步骤2：将纱巾绕过脖子将纱巾的一端在脖子后面交叉，然后将两侧的纱巾带到脖子前面。

步骤3：扎蝴蝶结将两侧的纱巾交叉，然后把下方的纱巾折叠上去，形成一个蝴蝶结。

再使用纱巾的两侧来调整蝴蝶结的大小和形状。

方法三：围巾式系法步骤1：将纱巾折叠成长条形同方法二。

步骤2：将纱巾绕过脖子将纱巾的一端绕过脖子，将两边的纱巾侧带到脖子前面。

步骤3：交叉绑扎将两边的纱巾交叉，然后将下方的纱巾折叠上去，形成一个结。

步骤4：扎紧扎紧纱巾，然后使用纱巾的两侧来调整结的大小和形状。

方法四：头巾式系法步骤1：将纱巾折叠成长方形将纱巾展开，将两角对折成对角线，然后将纱巾再次对折成一个长方形。

步骤2：将纱巾围在头上将纱巾的中间部分放在头顶上，然后将两侧的纱巾带到头后方。

步骤3：扎结将两侧的纱巾扎个结，然后根据个人喜好和造型需要调整纱巾的位置和形状。

结论以上介绍了四种简单的系纱巾方法，其中经典三角巾是最简单的。

根据不同的场合和个人喜好，你可以选择适合的系法来打造不同风格的造型。

尝试这些方法，让你的搭配更加时尚。

高中数学竞赛 数论剩余类与剩余系(1)定义1 设m 为正整数，把全体整数按对模m 的余数分成m 类，相应m 个集合记为：K 0,K 1,…,K m-1,其中K r ={qm+r|q ∈Z,0≤余数r ≤m-1}称为模m 的一个剩余类(也叫同余类)。

K 0,K 1,…,K m-1为模m 的全部剩余类.(2)性质(ⅰ)i m i K Z 10-≤≤= 且K i ∩K j =φ(i ≠j). (ⅱ)每一整数仅在K 0,K 1,…,K m-1一个里.(ⅲ)对任意a 、b ∈Z ，则a 、b ∈K r ⇔a ≡b(modm).(1)定义2 设K 0,K 1,…,K m-1为模m 的全部剩余类，从每个K r 里任取一个a r ，得m 个数a 0,a 1,…,a m-1组成的数组，叫做模m 的一个完全剩余系,简称完系.特别地,0,1,2,…,m -1叫做模m 的最小非负完全剩余系.下述数组叫做模m 的绝对最小完全剩余系:当m 为奇数时,21,,1,0,1,,121,21--+----m m m ;当m 为偶数时,12,,1,0,1,,12,2--+--m m m 或2,,1,0,1,,12m m -+-. (2)性质(ⅰ)m 个整数构成模m 的一完全剩余系⇔两两对模m 不同余. (ⅱ)若(a,m)=1，则x 与ax+b 同时遍历模m 的完全剩余系.证明:即证a 0,a 1,…,a m-1与aa 0+b, aa 1+b,…,aa m-1+b 同为模m 的完全剩余系, 因a 0,a 1,…,a m-1为模m 的完系时,若aa i +b ≡aa j +b(modm),则a i ≡a j (modm), 矛盾!反之,当aa 0+b, aa 1+b,…,aa m-1+b 为模m 的完系时,若a i ≡a j (modm),则有aa i+b≡aa j+b(modm),也矛盾!(ⅲ)设m1,m2是两个互质的正整数,而x,y分别遍历模m1,m2的完系,则m2x+m1y历遍模m1m2的完系.证明:因x,y分别历遍m1,m2个整数,所以,m2x+m1y历遍m1m2个整数.假定m2x/+m1y/≡m2x//+m1y//(modm1m2),其中x/,x//是x经历的完系中的数,而y/,y//是y经历的完系中的数.因(m1,m2)=1,所以,m2x/≡m2x//(modm1),m1y/≡m1y//(modm2),从而x/≡x//(modm1),y/≡y//(modm2),矛盾!(1)定义3如果剩余类K r里的每一个数都与m互质，则K r叫与m互质的剩余类.在与模m互质的全部剩余类中，从每一类中任取一个数所做成的数组，叫做模m的一个既约(简化)剩余系.如:模5的简系1,2,3,4;模12的简系1,5,7,11.(2)性质(ⅰ)K r与模m互质⇔K r中有一个数与m互质；证明:设a∈K r,(m,a)=1,则对任意b∈K r,因a≡b≡r(modm),所以,(m,a)=(m,r)=(m,b)=1,即K r与模m互质.(ⅱ)与模m互质的剩余类的个数等于)m(ϕ,即模m的一个既约剩余系由)m(ϕ个整数组成()m(ϕ为欧拉函数);(ⅲ)若(a,m)=1,则x与ax同时遍历模m的既约剩余系.证明:因(a,m)=1,(x,m)=1,所以,(ax,m)=1.若ax1≡ax2(modm),则有x1≡x2(modm),矛盾!(ⅳ)若a1,a2,…,aφ(m)是)m(ϕ个与m互质的整数,并且两两对模m不同余,则a 1,a 2,…,a φ(m)是模m 的一个既约剩余系.证明:因a 1,a 2,…,a φ(m)是)m (ϕ个与m 互质的整数,并且两两对模m 不同余, 所以,a 1,a 2,…,a φ(m)属于)m (ϕ个剩余类,且每个剩余类都与m 互质,故a 1,a 2,…,a φ(m)是模m 的一个既约剩余系.(ⅴ)设m 1,m 2是两个互质的正整数,而x,y 分别历遍模m 1,m 2的既约剩余系,则m 2x+m 1y 历遍模m 1m 2的既约剩余系.证明:显然,既约剩余系是完系中所有与模互质的整数做成的.因x,y 分别历遍模m 1,m 2的完系时,m 2x+m 1y 历遍模m 1m 2的完系.由(m 1,x )=(m 2,y )=1, (m 1,m 2)=1得(m 2x,m 1)=(m 1y,m 2)=1,所以,(m 2x+m 1y,m 1)=1,(m 2x+m 1y,m 2)=1,故(m 2x+m 1y, m 1m 2)=1.反之若(m 2x+m 1y, m 1m 2)=1,则(m 2x+m 1y,m 1)=(m 2x+m 1y,m 2)=1,所以,(m 2x,m 1)=(m 1y,m 2)=1,因(m 1,m 2)=1,所以,(m 1,x )=(m 2,y )=1.证毕.推论1若m 1,m 2是两个互质的正整数,则)()()(2121m m m m ϕϕϕ=.证明:因当x,y 分别历遍模m 1,m 2的既约剩余系时,m 2x+m 1y 也历遍模m 1m 2的既约剩余系,即m 2x+m 1y 取遍)(21m m ϕ个整数,又x 取遍)(1m ϕ个整数,y 取遍 )(2m ϕ个整数,所以, m 2x+m 1y 取遍)()(21m m ϕϕ个整数,故)()()(2121m m m m ϕϕϕ=.推论2 设整数n 的标准分解式为k kp p p n ααα 2121=(k p p ,,1 为互异素数,*1,,N k ∈αα ),则有)11()11)(11()(21k p p p n n ---= ϕ.证明:由推论1得)()()()(2121k k p p p n αααϕϕϕϕ =,而1)(--=αααϕp p p ,(即从1到αp 这αp 个数中,减去能被p 整除的数的个数),所以,)())(()(11221112211------=kk k k p p p p p p n ααααααϕ )11()11)(11(21kp p p n ---= . 4.欧拉(Euler)与费尔马(Fermat)定理欧拉(Euler)定理 设m 是大于1的整数,(a ,m)=1,则)(m od 1)(m a m ≡ϕ. 证明:设r 1,r 2,…,r )(m ϕ是模m 的既约剩余系,则由性质3知a r 1,a r 2,…,a r )(m ϕ也是模m 的既约剩余系,所以, a r 1a r 2…a r )(m ϕ≡r 1r 2…r )(m ϕ(modm),即≡)(21)(m m r r r a ϕϕ)(21m r r r ϕ ,因()(21m r r r ϕ ,m)=1,所以,)(m od 1)(m a m ≡ϕ.推论(Fermat 定理) 设p 为素数,则对任意整数a 都有)(m od p a a p ≡.证明:若(a , p )=1,由1)(-=p p ϕ及Euler 定理得)(m od 11p a p ≡-即)(m od p a a p ≡;若(a , p )≠1,则p |a ,显然有)(m od p a a p ≡.例1设m>0,证明必有一个仅由0或1构成的自然数a 是m 的倍数.证明:考虑数字全为1的数:因1,11,111,1111,…中必有两个在modm 的同一剩余类中,它们的差即为所求的a .例2证明从任意m 个整数a 1,a 2,…,a m 中,必可选出若干个数,它们的和(包括只一个加数)能被m 整除.证明:考虑m 个数a 1,a 1+a 2,a 1+a 2+a 3,…,a 1+a 2+…+a m ,如果其中有一个数能被m 整除,则结论成立,否则,必有两个数属于modm 的同一剩余类,这两个数的差即满足要求.例3设f(x)=5x+2=f 1(x), f n+1(x)=f[f n (x)].求证:对任意正整数n,存在正整数m,使得2011|f n (m).证明:因f 2(x)=f[f(x)]=5(5x+2)+2=52x+5×2+2,f 3(x)=f[f 2(x)]=53x+52×2+5×2+2,..., f n (x)=5n x+5n-1×2+5n-2×2+ (2)因(5n ,2011)=1,所以,x 与f n (x)同时历遍mod2011的完系,1≤x ≤2011,所以,存在正整数m(1≤m ≤2011)使得f n (m)≡0(mod2011),即2011|f n (m).例4设123,,,a a a 是整数序列,其中有无穷多项为正整数,也有无穷多项为 n ,数123,,,,n a a a a 被n 除的余数都各不相同.证明:在数列123,,,a a a 中,每个整数都刚好出现一次.证明:数列各项同时减去一个整数不改变本题的条件和结论,故不妨设a 1=0.此时对每个正整数k 必有∣a k ∣<k:若∣a k ∣≥k,则取n=∣a k ∣,则a 1≡a k ≡0(mod n),矛盾.现在对k 归纳证明a 1,a 2,…,a k 适当重排后是绝对值小于k 的k 个相邻整数.k=1显然.设a 1,a 2,…,a k 适当重排后为-(k -1-i),…,0,…,i (0≤i ≤k -1),由于a 1,a 2,…,a k ,a k+1是(mod k+1)的一个完全剩余系,故必a k+1≡i+1(mod k+1), 但∣a k+1∣<k+1,因此a k+1只能是i+1或-(k -i),从而a 1,a 2,…,a k ,a k+1适当重排后是绝对值小于k+1的k+1个相邻整数.由此得到:1).任一整数在数列中最多出现一次;2).若整数u 和v (u<v) 都出现在数列中,则u 与v 之间的所有整数也出现在数列中.最后由正负项均无穷多个（即数列含有任意大的正整数及任意小的负整数）就得到:每个整数在数列中出现且只出现一次.例5偶数个人围着一张圆桌讨论，休息后，他们依不同次序重新围着圆桌坐下,证明至少有两个人，他们中间的人数在休息前与休息后是相等的。

小丝巾最简单的三种系法小丝巾最简单的三种系法，小丝巾可以说是女生的必备单品，丝巾是我们四季都可以使用的，丝巾搭配方法非常多的，下面分享小丝巾最简单的三种系法。

小丝巾最简单的三种系法11.小方巾后系法把准备好的方巾一个角向前挂在脖子上，另外两个角系在脖子后面，后面系的时候系一个偏松的死扣即可，不要过紧哦，不然不好解开了。

2.项链式系法项链式系法是比较显气质一种系法特别是黄黑相间的方巾，系上后特别美。

系法非常简单，首先把小方巾对折形成两个三角形状，然后把丝巾卷成长圆状，中间打上一个结，把方巾的头穿过结，拉出方巾的头，做点缀之用。

3.双结系法把方巾挂到脖子上，在适当的'位小丝巾最简单的三种系法21、系脖子上风格特点：优雅、成熟丝巾的一种最为简单常见的方式就是直接系在脖子上，在早秋的时候还有一定的御寒效果，点缀效果也非常的不错，能够让造型的丰富度有所提升。

如果比较喜欢小方巾，直接按照对角线折起来，然后向内折，直接绕着脖子打一圈就可以了。

而且这种方式相对是较为简单的，几乎一看就会能够让整体的造型更有亮点。

而且这种方式更容易打造出优雅又成熟的造型。

2、系在头发上风格：活泼、复古还有一种比较简单的方式是直接将丝巾系在头发上，无论是低马尾还是高马尾，都有一定的减龄效果，而且这种搭配方式会特别的复古，想要打造出一种更加完美的造型，可以选择将头发先用发绳固定好，然后再将丝巾绑上去，这样会更加的稳定，不会有一种危险的感觉，建议以小一点的丝巾搭配进行打造，高马尾看上去还有一种法式的风格。

尤其是采用低马尾搭配丝巾的方式，再早秋的时候，配上一些复古的裙装，更能够将上个世纪八九十年代的一种风格演绎得淋漓尽致，选择基础款式进行搭配就可以了，或者马尾上的丝巾与衣服的'颜色形成呼应的效果。

3、裹在胸上风格：个性、特点除了扎马尾的时候，可以与头发有一定的关联之外，还有一种较为经典的方式，就是将丝巾直接包裹在头发上。

这种方式是奥黛丽赫本经常出现的一种造型，特别有女神的`气质，而且演变到现在的时尚圈儿之中，会更有个性，也更加的有特点。

同余理论及其应用东北育才学校 费振鹏基础知识一、定义定义1：整数集Z 根据模正整数()1m m >来分类：若a 、b 被m 除的余数相同，则a 与b 属于同一类，否则不属于同一类．这样得到m 个类，即{}|Z,0,1,2,1i M i km k i m =+∈=- ．称之为模m 的剩余类（同余类）．定义2：若整数a 、b 之差被正整数m 整除，称a 、b 关于模m 同余，记作()mod a b m ≡．即()()m o d a b m m a b ≡⇔-．从字面上理解，所属模m的同一个剩余类的两个整数模m 同余．定义3：在模m 的m 个剩余类中各取一个整数作为代表，这些代表的集合称为模m 的完全剩余系．简称完系．定义4：绝对值不超过2m ⎡⎤⎢⎥⎣⎦的模m 的完系称为模m 的绝对最小完系．将0,1,2,,1m - 称为模m的最小非负完系．定义5：当模m 的某一剩余类i M 中某一整数与m 互质，由欧氏除法（辗转相除法）知i M 中每个数与m 均互质，则称此剩余类是模m 的缩剩余类（亦称简化剩余类）．定义6：设m 为正整数，从1到m 的整数中与m 互质的整数的个数用()m ϕ表示，称()m ϕ为欧拉函数．模m 的缩剩余类（简化剩余类）也是()m ϕ个．定义7：在模m 的()m ϕ个缩剩余类（简化剩余类）中各取一个整数作为代表，这些代表的集合称为模m 的缩剩余系（简化剩余系），简称缩系（简系）．定义8：满足()1mod k a m ≡的最小正整数k 称为整数a 模m 的指数（阶）． 二、定理定理1：同余的基本性质： ⑴()mod a a m ≡；⑵若()mod a b m ≡，则()mod b a m ≡；⑶若()mod a b m ≡，()mod b c m ≡，则()mod a c m ≡；⑷若()mod a b m ≡，m qn =，N n ∈，则()mod a b n ≡． 定理2：若()11mod a b m ≡，()22mod a b m ≡，则⑴()1212mod a a b b m +≡+；⑵()1212mod a a b b m -≡-；⑶()1212mod a a b b m ≡． 推论：⑴若()()mod 1,2,,i i a b m i n ≡= ，则()11m od nn i ii i a b m ==≡∑∑；()11mod nniii i ab m ==≡∏∏．⑵若()mod a b m ≡，n 为任意正整数，则()mod na nb m ≡；()mod n n a b m ≡． 定理3：若()mod ac bc m ≡，则()m od,m a b c m ⎛⎫≡ ⎪⎝⎭． 推论：若(),1c m =，()mod ac bc m ≡，则()mod a b m ≡． 定理4：若()mod a b m ≡，则()(),,a m b m =．定理5：若()mod i a b m ≡，1,2,,i k = ，则[]()12mod ,,,k a b m m m ≡ ．定理6：设f 是()N m +∈的正约数，在模f 的属于c 的剩余类中取整数,,,1mc c f c f f ⎛⎫++- ⎪⎝⎭，则它们是模m 的mf个剩余类．定理7：m 个整数12,,,m a a a 是模m 的完系的充要条件是12,,,m a a a 关于模m 两两不同余． 定理8：若(),1k m =，其中*Z k ∈（*Z 表示非零整数集），Z b ∈，+N m ∈，1m >且12,,,m x x x 是模m 的完系，则12,,,m kx b kx b kx b +++ 也是模m 的完系．定理9：（裴蜀定理）设a ，b ，d 是整数，则(),a b d =的充要条件是d a ，d b ，且存在整数u ，v 使得ua vb d +=．推论：⑴(),1a b =的充要条件是存在整数u ，v 使得1ua vb +=．⑵a ，b 均为正整数，(),1a b =的充要条件是存在正整数u ，v 使得1ua vb -=． 定理10：（费马小定理）若a 是整数，p 是质数且(),1a p =，则()11mod p a p -≡． 推论：若p 是质数，则()mod p a a p ≡．这里不要求a 、p 互质．定理11：()m ϕ个整数是模m 的简系的充要条件是它们均与m 互质且模m 两两互不同余． 定理12：设()12,,,m a a a ϕ 是模m 的简系，且(),1c m =，则()12,,,m ca ca ca ϕ 也是模m 的简系．定理13：（欧拉定理）若a 是整数，正整数1m >且(),1a m =，则()()1mod m a m ϕ≡． 定理14：欧拉函数的性质： ⑴若整数2m >，则()m ϕ是偶数．⑵设1iki i m p α==∏是m 的标准分解式，则()111kii m m pϕ=⎛⎫=⋅- ⎪⎝⎭∏．⑶若正整数m 、n 满足(),1m n =，则()()()mn m n ϕϕϕ=． ⑷()d md m ϕ=∑，其中d m∑表示d 遍历m 的所有正约数．定理15：（威尔逊定理）若p 是质数，则()()1!1mod p p -≡-．典型例题一、选取适当的模例1.求最大的正整数n ，使得方程组()()()()222222221212k nx y x y x k y x n y ++=++==++==++有整数解()12,,,,n x y y y ． （2003年越南数学奥林匹克）分析：我们利用平方数的性质处理问题． 解：所求最大正整数3n =．当3n =时，()()()222222123123x y x y x y ++=++=++．进而得2212222323,2 5.y y x y y x ⎧-=+⎪⎨-=+⎪⎩ 易得所给方程组有整数解()()123,,,2,0,1,0x y y y =-．当4=n 时，22122223223423,25,27.y y x y y x y y x ⎧-=+⎪-=+⎨⎪-=+⎩则1y ，2y ，3y ，4y 奇偶交替出现．从而()()22221322*y y y -+=且()()22232422**y y y -+=．若1y ，3y 为奇数，则由2y 是偶数得()2220mod 8y ≡，而由()222213224mod 8y y y =++≡． 即得出式()*矛盾．若1y ，3y 为偶数，则2y ，4y 为奇数．同理可得出式()**矛盾．所以4=n 无解．而当4n ≥时显然无解． 综上可得所求最大正整数3n =． 例2.已知11a =，22a =，{12153,,n n n n n a a a a a +++-=-11n n n n a a a a ++⋅⋅,.若为偶数若为奇数证明：对一切正整数n ，0n a ≠． （1988年全国高中数学联赛二试）分析：我们只要证明n a 模某一常数不为0即可．证明：若某一个0k a =，则对任意正整数m 有()0mod k a m ≡，因此，我们只要找到一个m ，对任何一个n 均有()0mod k a m ≡/即可．先通过计算前几项：11a =，22a =，37a =，429a =，522a =，623a =，…模3的余数分别为1，2，1，2，1，2，…于是猜想奇数项模3余1，偶数项模3余2． 即()211mod 3n a -≡，()22mod 3n a ≡，其中*n ∈ ．下面用数学归纳法证明这一猜想： 当1n =时，()111mod 3a =≡，()222mod 3a =≡，结论成立； 假设当n k =时，结论成立，即()211mod 3k a -≡，()22mod 3k a ≡．则不管()21221253241mod 3k k k k a a a a +-=-≡≡≡，还是()21221211mod 3k k k a a a +-=-≡-≡，均有()211mod 3k a +≡．进而不管()22212215322m o d 3k k k k a a a a +++=-≡≡，还是()22212122m o d 3k k k a a a ++=-≡-≡，均有()222mod 3k a +≡． 综上所述，猜想结论成立． 因此，原命题结论成立． 注：本题有如下加强命题：⑴此数列所有项都不是3的倍数；（根据上面的证明，容易得出这个结论） ⑵此数列所有项都不是4的倍数；⑶此数列为模3的模周期数列；（根据上面的证明，容易得出这个结论）⑷此数列为模4的模周期数列（模4的结果为1，2，3，…，据此也可证明加强命题⑵）．()11mod 4a ≡，()22mod 4a ≡，()33mod 4a ≡．设n k =时，()321mod 4k a -≡，()312mod 4k a -≡，()33mod 4k a ≡．则1n k =+时，()31331531mod 4k k k a a a +-=-≡，()323132mod 4k k k a a a ++=-≡，()333231533mod 4k k k a a a +++=-≡． 因此对一切n 均有()0m od 4k a ≡/，从而原命题成立．评注：选择适当的模结合相关知识，如平方数性质、模周斯数列是解决同余问题的技巧之一． 二、不定方程例3.证明：方程243y x x =+没有正整数解． （2004年韩国数学奥林匹克）分析：我们选择适当的模对x 进行分类处理问题． 证明：⑴当()1m od 3x ≡时，设()31N x a a =+∈，()42mod 3x x +≡． 而方程左边()230mod 3y ≡，矛盾． 所以此时无解． ⑵当()0mod 3x ≡时，设()*3N x a a =∈，()()()()4222113319313x x x x x x a a a a y +=+-+=+-+=． ∴()()2231931a a a a y +-+=．而(),311a a +=，()2,9311a a a -+=，()()231,93131,31a a a a +-+=+=， ∴a ，31a +，2931a a -+均为完全平方数．但由()()222319313a a a a -<-+<知2931a a -+不可能是完全平方数． 所以此时无解． ⑶当()1mod 3x ≡-时，设()*31N x a a =-∈时，()()()()4222119313313x x x x x x a a a a y +=+-+=--+=． ∴23|3|y y ⇒．令()*3N y c c =∈，则()()22313313a a a a c --+=． ∴3|a ．令()*3N a b b =∈，则()()22912791b b b b c --+=． 与⑵类似，b ，91b -，22791b b -+均为完全平方数．其中()912mod 3b -≡不可能是完全平方数，矛盾．所以此时无解．综上所述，原方程无正整数解．评注：方程右边可因式分解，而左边系数为3，因而选择模3对x 进行分类处理． 例4.x 、y 是质数，解方程219y x x y xy -=-． （2004年巴尔干地区数学奥林匹克） 分析：我们要充分利用x 、y 是质数的条件． 解：（Ⅰ）若x y =，则219xy =．显然不可能． （Ⅱ）若x y ≠，则219x y y x xy -+=．而x 、y 是质数，由费马小定理，得()mod y x x y ≡．∴2(m od )x y y x xy x y -+≡-．即19(mod )x y ≡-．∴|19y x +① 由费马小定理，得(m od )x y y x ≡．∴2(m od )x y y x xy y x -+≡．即19(mod )y x ≡．∴|19x y -②．⑴若19y >，则由①知19y x ≤+，由②知19x y ≤-即19y x ≥+．∴19y x =+．又y 是质数且2y >，故y 是奇质数．从而2x =，21y =不是质数．矛盾．所以此时无解． ⑵若19y =，则由①知19|x ．故19y x ==．这与（Ⅰ）矛盾．⑶若19y <，则由①、②，得{|19,|19.y x x x +- 当17y =时，由|19x y -，得质数2x =．不满足|19y x +． 当13y =时，由|19x y -，得质数2x =或3．不满足|19y x +． 当11y =时，由|19x y -，得质数2x =．不满足|19y x +．当7y =时，由|19x y -，得质数2x =或3．仅有()(),2,7x y =满足|19y x +，且满足原方程． 当5y =时，由|19x y -，得质数2x =或7．不满足|19y x +．当3y =时，由|19x y -，得质数2x =．()(),2,3x y =满足|19y x +，且满足原方程． 综上，()()(),2,7,2,3x y =为所求方程的解．评注：在处理有关质数幂的问题中，费马小定理常发挥重要作用．例5.设n 是整数，求证：若2+（2007年英国数学奥林匹克）证明：由2Z +，Z n ∈，得2112n +是完全平方数． 设()22112N n m m ++=∈，则()()21112m m n +-=． 又1m +、1m -奇偶性相同，故1m +、1m -均为偶数． 则211322m m n +-⋅=．记12m t +=，则112m t -=-，其中N t +∈．故()()213*t t n -=．要证222m +=+是完全平方数，只需证t 是完全平方数． 根据()*知，3t 或31t -，而()gcd ,11t t -=．若3t ，则由()gcd ,113t t -=，且()213t t n ⋅-=，知3t 与1t -都是完全平方数．设23t k =，则23t k =，()21311mod 3t k -=-≡-不可能是完全平方数．矛盾．因此，31t -．从而由()1gcd ,13t t -=，213t t n -⋅=，知t 与13t -都是完全平方数．综上，原结论成立．注：还可利用佩尔方程理论解决这个问题． 三、完系、费马小定理及其它相关定理例6.证明：对每个正整数n 存在一个各位数字均为奇数的n 位数能被5n 整除． （2003年第32届美国数学奥林匹克）证明：用数学归纳法．当1n =时，结论显然成立．假设12n N a a a = 能被5n 整除且各位数字都是奇数．考虑下列数：()11211105512nnnnn N a a a M M==⋅+=⋅+ ； ()21233105532nnnnn N a a a M M ==⋅+=⋅+ ； ()31255105552nnn nn N a a a M M ==⋅+=⋅+ ； ()41277105572nnnnn N a a a M M ==⋅+=⋅+ ； ()51299105592nnn nn N a a a M M==⋅+=⋅+ ．而数12,32,52,72,92n n n n n M M M M M ⋅+⋅+⋅+⋅+⋅+是模5的完系， 所以12345,,,,N N N N N 中之一能被55n ⋅整除．归纳推理完成． 注：由此引申一个问题：证明：对任意奇数，都可以找到它的一个倍数，使得该倍数的各位数字都是奇数． 这个问题利用例3的结论，再通过构造一个例子来证明这个命题．例7.设p 是奇质数，证明：()()121211m od 2p p k p p k p --=+≡∑．（2004年加拿大数学奥林匹克）证明：因为1p -是偶数，故()11221212111p p p p p k k k k p k -----==⎡⎤=+-⎣⎦∑∑．由二项式定理，得()()21212121p p iip ip i p k Cpk -----=-=⋅⋅-∑．模2p ，得()()()()()2122211222122121mod p p p p p p p k C p k k p p kkp -------≡⋅⋅-+-≡-⋅⋅-．故()()()()212122222222212mod p p p p p k p k p p kp p kpkp -----+-≡-⋅⋅≡-≡-．对11k p ≤≤-，必有()gcd ,1k p =．由费马小定理，得()11mod p k p -≡．故()221mod p k p -≡．即221p p k --．从而()()222221mod p p pk p k p p p ---≡---≡-．因此()()122122111m od 222p p k p p p p p kp p p --=+--≡-⋅≡+≡∑． 例8.求证：方程组6331573329147147157x x x y y x x y y y z ⎧+++=⎨++++=⎩没有整数解．（2005年第34届美国数学奥林匹克）证明：1++①②，得329157147(1)1471571x y z +++=++③． 考虑[2,9]18=，联系费马小定理，证明上式两边模19不同余． 由费马小定理，知()gcd ,191a =时，()181mod19a ≡； 否则()gcd ,191a ≠即19|a 时，()180mod19a ≡． 因此()29180zz=≡或()1m od19．从而()91,0,1mod19z ≡-④．对Z n ∀∈，有()0,1,2,,9mod19n ≡±±± ，所以()28,3,2,0,1,4,5,6,7,9mod19n ≡---⑤． 由④、⑤，得()()23915,6m od19x y z +++≡--/⑥． 由费马小定理，得1571471571471881318831471571(5)51551⨯+⨯+++≡-++≡-++13334134551551(8)581⨯+≡-++≡-++≡--⨯-+()27581115815mod19≡-⨯-+≡-⨯-+≡-⑦由⑥、⑦得()()23915714711471571m od19x y z +++≡++/．故()23915714711471571x y z +++≠++． 因此，原方程组无整数解．例9.证明序列{}232,3,n n -= 至少含有一个无穷子序列，且其中的项两两互质． （1971年第13届国际数学奥林匹克）证明：⑴2231-=，，3235-=，423-两两互质；⑵假设正整数1n ，2n ，…，k n 使序列()i 123n -，223n -， (23)n -两两互质，则只要证明存在1k n +使123k n +-与序列()i 中的每个数都互质，即得这1k +个数两两互质．由归纳法，原命题得证．证明123k n +-不含序列()i 中的所有数的质因子即可．设{}12,,,r p p p 是由序列()i 中的所有数的质因子组成的集合，显然12,,,r p p p 都是奇质数，即()gcd 2,1i p =．则由费马小定理，得()121mod i p i p -≡．因此()()1121mod ri i p i p =-∏≡，其中1,2,,i r ∀= ．进而()()1123132mod ri i p i p =-∏-≡-≡-．而()3i p ≥都是奇质数，故()11gcd 23,1ri i p i p =-⎛⎫∏ ⎪-= ⎪⎝⎭． 因此取()111rk i i n p +==-∏，则()1112323ri k i p n +=-∏-=-与23i n-都互质，其中1,2,,i k ∀= ．例10.求所有的质数p 、q ，使得()()5252p p q q pq --． （1996年保加利亚数学奥林匹克）解：显然质数p 、q 都不为2，则(),11p q -=．如果52p p p -，由费马小定理，得()55mod p p ≡，()22mod p p ≡．从而52p -，所以3p =． 假设,3p q ≠，则52q q p -，52p p q -．不妨设p q >，由裴蜀定理，存在正整数u 、v ，使()11u q vp --=．显然质数p 、q 都不为5，由费马小定理，得()151mod q q -≡，()121mod q q -≡．故1152q q q ---． 所以()()()1111525255232u q u q vp vp vp vp vp q --++-=-=-+⋅，又52p p q -，所以32vp q ⋅，矛盾． 所以p 、q 之一为3．若3p q ==，满足题意，则()(),3,3p q =．若3p =，()33q >≠，则3352913q -=⋅，所以13q =． 因此，所求的解为(,)(3,3),(3,13),(13,3)p q =．评注：完系、费马小定理结合二项式定理等是处理整除、同余问题的重要工具．练习及参考答案练习1.设质数p 满足()7mod 8p ≡，证明p 不能表示成三个平方数之和． 分析：我们利用平方数模8的性质进行处理．证明：设存在三个整数a ，b ，c 使222p a b c =++．而对Z x ∀∈，有()20,1,4mod 4x ≡． 所以()2220,1,2,3,4,5,6mod 8a b c ++≡，而得不到()2227mod 8a b c ++≡． 因此形如()7mod 8p =的质数不能表作三个平方数之和．练习 2.一会议厅有n 张椅子围绕着一张圆桌．n 位代表在开会．第一位代表任意选择他（或她）的座位．此后第()1k +位代表坐在第k 位代表的右边的（按逆时针方向）第k 个座位，这里11k n ≤≤-．（特别地，第两位代表坐在第一位的下一个座位．）每张椅子不能坐多于一位代表．求能得到如此安置代表座位的n 值． （2002年英国数学奥林匹克第2轮） 解：2m n =，其中m 是任一非负整数．记这些座位的编号分别为0,1,2,,1n - ．第k 位代表坐在座位()12k k -，其中1,2,,k n = ．于是如果这n 个数()12k k -对模n 不同余，这里1,2,,k n = ，那么这个安置座位方案是可能的． 首先，假设2m n =，其中m 是非负整数．特别地，当0m =时，显然安置座位方案是可能的．当0m ≠时，我们有()()()()111222h h k k h k h k ---+--=．若h 和k 不相等，则h k -和1h k +-都是非零数，但它们具有相异奇偶性，并且都小于2n ． 于是其中一个是奇数，另一个不能被比2m 的指数更高的2的幂整除．这样()()12h k h k -+-不能被2m 整除，即()12h h -与()12k k -对模n 不同余．因此安置座位方案在n 是一个2的幂时可操作．反之，假设()221m n a =+，其中a 是正整数，m 是非负整数． 若2m a <，取21m h a =++，2m k a =-． 则21h k a -=+，112m h k ++-=，()()()1122122mh h k k a ---=+．故()12h h -和()12k k -对模n 同余．若2m a ≥，取21m h a =++，21m k a =-+． 则12m h k +-=，121h k a +-=+，()()()1122122mh h k k a ---=+．故也得到()12h h -和()12k k -对模n 同余．上述h 、k 的取值都是1~n 范围内的整数．因此若n 不是一个2的幂就没有可能的安置座位方案． 练习3.求数200120022003的末三位数字．（2003年加拿大数学奥林匹克）解：因为()20033mod 1000≡，所以()200120012002200220033mod 1000≡．为解决这个问题，我们首先确定一个正整数n 使()31mod 1000n ≡． 由二项式定理，得()()()()()1222131011101101102mmm m m mm m m ---=-=-+⋅⋅-+⋅⋅-++ ．上式中前三项后的各项之和能被1000整除．于是设2m q =，则()()4312010021mod 1000q q q q ≡-+-≡．①由()1201002110001q q q k -+-=+，253250q q k --=，由十字相乘法易得25q =满足． 从而()10031mod 1000≡．而()20022mod 100≡，故()()200120012199920022mod 10022mod 425≡≡⋅⋅． 因为()10210241mod 25=≡-，所以()()()199199199910922215121213m od 25=⋅≡-⋅≡-≡．于是()200120012002241352mod 100≡≡⋅=，再由①，得()20012001200220021005252200333312013130025241mod 1000k +≡≡≡≡-⋅+⋅≡．因此数200120022003的末三位数字是241．练习4.设三角形的三边长分别是整数l ，m ，n ，且l m n >>．已知{}{}{}444333101010lmn==，其中{}[]x x x =-，而[]x 表示不超过x 的最大整数．求这种三角形周长的最小值． （2003年全国高中数学联赛加试）解：由题意，知()4333m od 10l m n ≡≡，即3l 、3m 、3n 的末四位数字相同． 又当且仅当l m n <+时，以l ，m ，n （l m n >>）为边才能构成三角形． 由二项式定理，得()()()()24210002122310112010021103pp pp p p p p p --=-=-+--++ ．⑴由此容易得到，()431mod 10p ≡．即1i =时，44h p =≥，()431mod 10≡； ⑵若20100p k -=，则()4231m od 10p ≡，当5p q =时，()20231m od 10q ≡． 即2i =时，2020h q =≥，()20231m od 10≡；⑶若()20100211000p p p k -+-=，则()20331m od 10q ≡． 由225350q q k --=，得5q r =，()100331m od 10r ≡． 即3i =时，100100h r =≥，()100331m od 10≡． ⑷若()()()100021222010021100003p p p p p p k---+--=，则()100431m od 10r ≡，3262500412559300r r r k -++=，得5r s =，()500431m od 10s ≡． 即4i =时，500500h s =≥，()500431mod 10≡． 设500m n x =+，500l n y =+，其中x y <， 则500500n y n x n +<++，()500500n y x >-≥． 故()3500350150033003l m n n x y ++=++≥⨯+⨯=．即当三角形的三边长分别为1501l =，1001m =，501n =时，其周长l m n ++取得最小值，且最小值为3003．练习5.求证：存在无穷多个这样的正整数，它们不能表示成少于十个奇数的平方和． 分析：对于否定性问题，我们常利用同余．解：设正整数n 能够表示成22212...,s n x x x =+++① 其中i x 为奇数，1,2,...,,19.i s s =≤≤若2(mod 8)n ≡，则由①及21(m od 8),1,2,...,i x i s ≡=知2(mod 8)s ≡，即 2.s = 若2,3|s n =，则由①及20,1(m o d 3),1,2i x i ≡=知120(m od 3)x x ≡≡，从而9|.n 这说明若3(m o d 9)n ≡，则 2.s ≠综上所述，被8除余2，被9除余3，即具有形式7266,0,1,2,...k k +=的正整数便不能表示成①，故命题得证．评注：对于某些问题，常常需要多次选择不同的模进行同余处理． 练习6.证明：132730n n -． 分析：由原式联想到费马小定理． 证明：2730235713=⨯⨯⨯⨯．由费马小定理，()13mod 13n n ≡，()7mod 7n n ≡，()5mod 5n n ≡，()3mod 3n n ≡，()2mod 2n n ≡．而由()13121n n n n -=-易得713|n n n n --，513|n n n n --，313|n n n n --，213|n n n n --． 所以13|k n n -，2,3,5,7,13k =．且2，3，5，7，13两两互质，因此原结论成立． 练习7.求出大于1的整数n 的个数，使得对任意的整数a ，都有25|n a a -． 分析：联想例4，猜想n 的最大值为2730．解：设满足条件的正整数组成集合S ，若25|n a a -，25|m a a -，则25[,]|m n a a -，因此S 中全部数的最小公倍数也属于S ，即S 中的最大数是其余每个数的倍数．25|m a a -，则m 的约数也整除25a a -，于是只需确定最大数m ，其一切大于1的约数组成集合S ．2525|22,|33m m -- ，并且2525(22,33)235713--=⨯⨯⨯⨯，由例4，由费马小定理，易证235713⨯⨯⨯⨯25|a a -，所以235713m =⨯⨯⨯⨯，集合S 共有31个元素．评注：利用特殊值法确定最大值，再进行证明是处理竞赛问题的典型技巧．练习8.34021(m od 341)≡但3411113=⨯为合数，则称341是伪质数，证明：伪质数有无穷多个． 分析：我们想办法构造出具体的表达或递推关系．证明：已知341为伪质数，假设m 是伪质数，下面证明21m -是伪质数．首先，设m pq =，其中,p q 为大于1的整数，则2121(2)1m pq p q -=-=-，含有因子21p -，并且12121p m <-<-，所以21m -为合数．其次，由于1|21m m --，设121m ms --=，其中s 为大于1的正整数，11(21)12221212121(21)(21)mmm m --------=-=-+，而1212121(2)1m msms---=-=-，可被21m -整除，因而(21)121(mod(21))mm --≡-，所以21m-是伪质数，并且21m m ->．由此可知伪质数有无穷多个．评注：利用递推关系构造是解决无穷解问题的重要构造方法．练习9.求最小的正整数n ，使得333200212 (2002)n x x x +++=有整数解． （第43届IMO 预选题）分析：我们先估计出n 的值，在构造出一组解． 解：20024(mod 9)≡，341(m od 9)≡，200266731=⨯+， 所以20022002200244(m od 9)≡≡．又30,1(m od 9)x ≡±，其中x Z ∈．于是333333112123,,4(m od 9)x x x x x x +++≡/．由于332002101011=+++，则2002667320022002(2002)=⨯=6673(102002)⨯+6673(102002)⨯+6673(2002)+6673(2002)． 所以4n =．评注：选择适当的模，利用同余进行估计是重要的方法之一．练习10.正整数n 不能被2，3整除，且不存在非负整数a ，b ，使得23a b n -=．求n 的最小值．（2003年中国集训队测试）分析：我们先通过具体赋值猜出n 值，再进行证明．解：1n =时，11231-=；5n =时，22235-=；7n =时，12237-=；11n =时，432311-=|；13n =时，412313-=；17n =时，642317-=； 19n =时，332319-=；23n =时，522323-=；25n =时，132325-=；29n =时，512329-=；31n =时，502331-=；下证35n =满足要求，用反证法，若不然，存在非负整数a ，b ，使得2335a b -=． ⑴若2335a b -=，显然0a ≠，1，2，故3a ≥．模8，得()33m od 8b -≡，即()35mod 8b ≡，但()31,3mod 8b ≡，不可能．⑵若3235b a -=，易知0b ≠，1，模9，得()21mod 9a ≡， ∵(){}2mod 9:2,4,8,7,5,1,2,4,k∴621k ≡，6122k +≡，6224k +≡，6328k +≡，6427k +≡，()6525mod 9k +≡． 于是6n k =，其中k 为非负整数，所以23835b k -=．再模7，得()31mod 7b ≡． ∵(){}3mod 7:3,2,6,4,5,1,3,2,k ，故6b k '=，k '为正整数， ∴663235k k'-=，()()3333323235k kk k''-+=．∴{3333321,3235;k kk k''⋅=+=或{3333325,327.k kk k ''⋅=+= 于是，3318k '=或6，不可能．综上可知，min 35n =． 评注：对于不定方程无解的问题常用同余处理． 练习11.证明：对于任意正整数n ，2(1)!n n n -⎡⎤⎢⎥+⎣⎦是偶数． （2004年亚太地区数学奥林匹克）分析：当n 和1n +是合数时，容易处理，我们只要处理n 和1n +之一是质数的情况． 证明：对于1,2,3,4,5n =，我们有2(1)!0n n n -⎡⎤=⎢⎥+⎣⎦，显然为偶数．我们考虑6n ≥．如果n 和1n +是合数，则它们一定整除()1!n -，并且互质．所以它们的乘积整除()1!n -．由于n 和1n +中只有一个是偶数，对于6m ≥，()2!m -所含的2的幂指数大于m 所含的幂指数，所以2(1)!n n n -⎡⎤⎢⎥+⎣⎦是偶数． 我们最后考虑1n p +=为一个质数，和n p =为一个质数． 如果1n p +=，则1p -是一个合数，所以1p -整除()2!p -．令()2!1p k p -=-，由威尔逊定理()()2!1mod p p -≡，所以()()11mod k p p -≡，因此()1mod kp ≡-．所以1k p+是一个整数．但k 是偶数，所以1k +是奇数，因此1k p+是奇数．又11k k p p⎡⎤+=-⎢⎥⎣⎦，所以()21!n k p n n -⎡⎤⎡⎤=⎢⎥⎢⎥+⎣⎦⎣⎦是偶数．如果n p =，则()1!1p k p -=+是偶数，所以1k +是奇数．由威尔逊定理()()11mod k p p +≡-，所以1k p +是一个奇数，所以()21!11n k k k p p p n n -⎡⎤⎡⎤⎡⎤+===-⎢⎥⎢⎥⎢⎥+⎣⎦⎣⎦⎣⎦是偶数． 综上，原命题成立．评注：当n 和1n +之一是质数时，由()1!n -我们联想到威尔逊定理． 练习12.设{}n a ，{}n b 定义如下：01a =，11a =，112n n n a a a +-=+，01b =，17b =，()11231,2,n n n b b b n +-=+= ．证明：除“1”以外这两个数列没有其它相同的项．证明：012351,1,3,5,11...a a a a a =====，012341,7,17,55,161...b b b b b =====下面证明：21225(m od 8),3(m od 8)n n a a ++≡≡；21227(m od 8),1(m od 8)n n b b ++≡≡，其中n 为正整数．初值易验证，假设21225(m od 8),3(m od 8)k k a a ++≡≡，则23222123255(m o d 8)k k k a a a +++=+≡+⨯≡，24232225233(m od 8)k k k a a a +++=+≡+⨯≡，可知1n k =+时结论成立．同理可证{}n b ．因而原命题成立．练习13.求所有的正整数对(),a n 使得()1nna an+-是整数．证明：若a 为任意正整数，则(),1a 显然是原问题的解，下面我们证明原问题没有其他解．若2n ≥，易知()(),,11a n a n =+=，不妨设p 为n 的最小质因子，则()1nnp a a +-，又由费马小定理()111p p p a a--+-，而()1,1p n -=，由裴蜀定理存在正整数u ，v ，使()11u p vn --=． 则()()()()()()()11111111u p vn vnu p vn vnvnp a aa aa a aa-+-++-=+-=++-+，所以vn p a ，与(),1a n =矛盾．所以没有其他的正整数解．练习14.试求与无穷数列()23611,2,n n n n a n =++-= 的一切项均互素的所有正整数． （2005年第46届国际数学奥林匹克） 解：满足条件的正整数只有一个：1．为此只要证明对任一素数p ，存在正整数n 使得n p a ．由于248a =，故2,3p =时结论为真．设3p >，则p 与2、3、6均互素，由费马小定理，()1112361mod p p p p ---≡≡≡． 于是22236p p --≡⨯，()22326mod p p p --≡⨯．()()222223632161mod p p p p p ----++≡++⨯≡．2p p a -．证毕．练习15.设k 是一个大于1的固定的整数，245m k =-． 证明：存在正整数a 、b ，使得如下定义的数列{}0121:,,n n n n x x a x b x x x ++===+，0,1,n =其所有项均与m 互质． （第45届IMO 预选题）证：取1a =，222b k k =+-．因为()245mod k m ≡，所以()2242421mod b k k k m =+-≡+． 从而()2244414644mod b k k k b m ≡+-≡+≡+．又因为m 是奇数，故()21m od b b m ≡+． 由于()()()()222gcd ,gcd 22,45gcd 22,212,211b m k k k k k k k =+--=+-+=+=， 故()gcd ,1n b m =，其中n 是任意正整数．下面用数学归纳法证明：当0n ≥时，有()mod n n x b m ≡． 当0,1n =时，显然结论成立．假设对于小于n 的非负整数，结论都成立，其中2n ≥，则有()()12222121mod n n n n n n n n x x x b b b b b b b m ------=+≡+≡+≡≡． 因此，对于所有的非负整数n ，有()()gcd ,gcd ,1n n x m b m ==．练习16.设,a b +∈ ，且对,n +∀∈ 都有()()n n a n b n ++．证明：a b =． （第46届IMO 预选题）证明：假设a b ≠，则b a >．取素数p b >，则()(),,1a p b p ==． 由费马小定理，得()111mod p p a b p --≡≡．取()11n k p =-+，则()mod n a a p ≡，()mod n b b p ≡．从而()mod n a n a n p +≡+． 现在我们想让()0mod n a n a n p +≡+≡，只要()()1110mod na n a n a k p a k p +≡+≡+-+≡+-≡．因此仅须取1k a =+，即()()111n a p =+-+即可． 此时p 是n a a +的质因子，故也是n b b +的质因子．进而()0mod n b n b n b a p +≡+≡-≡，即p b a -．但0b a b p <-<<，矛盾． 因此，原命题成立．练习17.设p 为质数．证明：存在一个质数q ，使得对任意整数n ，数p n p -不能被q 整除． （2003年第44届国际数学奥林匹克）解：由于()212111mod 1pp p p p p p p p --=++++≡+- ， 则11pp p --中至少有一个质因子q ，满足()21mod q p ≡/．下面证明q 为所求．假设存在整数n ，使得()mod p n p q ≡．则由q 的选取，有()21mod p p n p q ≡≡． 另一方面，由费马小定理，()11mod q n q -≡（由于q 为质数且(),1n q =）． 由于()2|1p q -/，有()2,1|p q p -，则()1m od p n q ≡．因此，()1mod p q ≡． 从而，导出()11mod p p p p q -+++≡ ． 由q 的选取，有()0mod p q ≡．矛盾．。

完系、简系、剩余系 知识扫描若按对某一模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 j 。

成都七中高一竞赛数论专题 6.欧拉函数与Möbius 函数欧拉函数()m ϕ是一个定义在正整数集上的函数,()m ϕ的值等于1,2,,1m -中与m 互素的数的个数.也等于模m 的一个简系的元素个数.Möbius 函数()n μ定义为12121, 1 ()(1), ,0, 1 s s s p p p n n n p p p n μ<<<=⎧⎪=-=⎨⎪⎩素其他即有大于的平方因数数1.若12(,)1,m m =1x 跑遍模1m 的简系, 2x 跑遍模2m 的简系.证明：2112m x m x +跑遍模12m m 的简系.2.若12(,)1,m m =证明：1212()()().m m m m ϕϕϕ=3.设n 是正整数, (1)证明：|1().d nd n μ⎡⎤=⎢⎥⎣⎦∑ (2)证明：||()()().d n d nn n n d d d d ϕμμ==∑∑ (3)证明：22|()().d nd n μμ=∑4.已知正整数n 的素因数分解式1212,s s n p p p ααα=其中素数12s p p p <<<, 1.i α≥证明：12111()(1)(1)(1).sn n p p p ϕ=---5.设()n τ表示正整数n 的所有正因数的个数,()n ϕ表示模n 的一个简系的元素个数证明：()().n n n ϕτ≥6.证明：对任意的正整数m 都有|().d md m ϕ=∑7.设n 是正整数,证明：2i11|1()(1e).jk nd d j k d nn d πϕ===-∑∑∏8.给定整数9.a ≥证明：至多存在有限个正整数,n 同时满足下列条件：(1)()n a τ=；(2)|()().n n n ϕσ+高一竞赛数论专题 6.欧拉函数与Möbius 函数解答欧拉函数()m ϕ是一个定义在正整数集上的函数,()m ϕ的值等于1,2,,1m -中与m 互素的数的个数.也等于模m 的一个简系的元素个数.Möbius 函数()n μ定义为12121, 1 ()(1), ,0, 1 s s s p p p n n n p p p n μ<<<=⎧⎪=-=⎨⎪⎩素其他即有大于的平方因数数1.若12(,)1,m m =1x 跑遍模1m 的简系, 2x 跑遍模2m 的简系.证明：2112m x m x +跑遍模12m m 的简系.证明：我们知道1x 跑遍模1m 的完系,则1x 跑过1m 个数,2x 跑遍模2m 的完系,则2x 跑过2m 个数, 于是2112m x m x +跑过12m m 个数.假设2112211212(mod )m x m x m x m x m m ''''''+≡+,其中11,x x '''是模1m 的完系中的数,22,x x '''是模2m 的完系中的数.于是21211(mod )m x m x m '''≡,12122(mod ).m x m x m '''≡ 因为12(,)1,m m =所以111222(mod ),(mod ).x x m x x m ''''''≡≡所以1122,.x x x x ''''''== 这表明2112m x m x +跑遍模12m m 的完系.若1122(,)(,)1,x m x m ==则由12(,)1m m =得211122(,)(,)1,m x m m x m == 于是2112121122(,)(,) 1.m x m x m m x m x m +=+= 所以211212(,) 1.m x m x m m +=反之,若211212(,) 1.m x m x m m +=则2112121122(,)1,(,) 1.m x m x m m x m x m +=+= 于是211122(,)1,(,) 1.m x m m x m ==所以1122(,)1,(,) 1.x m x m == 这就证明了所要的结论.2.若12(,)1,m m =证明：1212()()().m m m m ϕϕϕ=证明：因为12(,)1,m m =1x 跑遍模1m 的简系, 2x 跑遍模2m 的简系.则2112m x m x +跑遍模12m m 的简系. 所以模12m m 的简系个数12()m m ϕ等于2112m x m x +跑过的个数,1x 跑过的个数为模1m 的简系个数1()m ϕ,2x 跑过的个数为模2m 的简系个数2()m ϕ.于是2112m x m x +跑过的个数为12()().m m ϕϕ即1212()()().m m m m ϕϕϕ=3.设n 是正整数, (1)证明：|1().d nd n μ⎡⎤=⎢⎥⎣⎦∑ (2)证明：||()()().d n d nn n n d d d d ϕμμ==∑∑ (3)证明：22|()().d nd n μμ=∑证明(1)当1n =时|()(1) 1.d nd μμ==∑结论成立.当1n >时,设n 的素因数分解式1212, 1.ss i n p p p αααα=≥121122||()()1(1)(1)(1)(11)0.ss s s s s s d nd p p p d d C C C μμ==+-+-++-=-=∑∑结论成立.(2) 11|(,)|(,)1|1|(,)1|()1()(()1)(()1)().nnnnk k d k n d k n k d n k d nk n d knn d d d d d ϕμμμμ==========∑∑∑∑∑∑∑∑ 显然()().n nd d d dμμ=所以得证.(3)当1n =时,显然成立. 当12,s n p p p =素数12s p p p <<<,2|()1,d nd μ=∑22()((1)) 1.s n μ=-=所以结论成立.当2n m q =,q 为不含平方因数的整数,若2|,d n 则|.d m 则2||()()0d md nd d μμ==∑∑,2()0n μ=,结论成立.所以22|()().d nd n μμ=∑ 4.已知正整数n 的素因数分解式1212,ss n p p p ααα=其中素数12s p p p <<<, 1.i α≥证明：12111()(1)(1)(1).sn n p p p ϕ=---法1证明：12121212()()()()()s ss s n p p p p p p ααααααϕϕϕϕϕ==121211111221212111(1)(1)(1)(1)(1)(1)s ss s s sp p p p p p p p p p p p αααααα---=---=---12111(1)(1)(1).sn p p p =---法2 12121212||1|()()(1)()()(1)s ssk ksd n d p p p k d p p p i i i nd d n d n nn d ddp p p αααμμϕμ=-====+∑∑∑∑12111(1)(1)(1)sn p p p =---5.设()n τ表示正整数n 的所有正因数的个数,()n ϕ表示模n 的一个简系的元素个数证明：()().n n n ϕτ≥证明：当1n =时,显然成立.当1n >时,设正整数n 的素因数分解式1212,s s n p p p ααα=其中素数12s p p p <<<, 1.i α≥则12111()(1)(1)(1).sn n p p p ϕ=---12()(1)(1)(1).s n τααα=+++因为122s p p p ≤<<<,所以12111111()(1)(1)(1)(1)(1)(1).2222s s nn n n p p p ϕ=---≥---=12()(1)(1)(1)2.s s n τααα=+++≥所以()()2.2ss n n n n ϕτ≥⋅= 6.证明：对任意的正整数m 都有|().d md m ϕ=∑证明：方法1 当1m =时显然成立当1m >时设正整数m 的素因数分解式1212,s s m p p p ααα=其中素数12s p p p <<<,0.i α≥|d m ,所以1212,s s d p p p βββ=,.i i βα≤于是1212121212121212|000()()()()()sssss s s s d md pp p p p p ααααααββββββββββββϕϕϕϕϕ========∑∑∑∑∑∑∑121212120()()()sss sp p p αααββββββϕϕϕ====∑∑∑. 注意到10()().ssii i i i i ii i i p p p p ααβββαββϕ-===-=∑∑所以121212121212|00()()()().ssss ss d md p pp p p p m αααβαββααβββϕϕϕϕ======∑∑∑∑方法2 我们把正整数1,2,,.m 按与m 的最大公约数分类.即与m 有相同的最大公约数的作为一类.这样,m 的正约数d 与这样的分类正整数之间建立了一个一一对应关系. 记{|(,),1}d M j j m d j m ==≤≤.首先每一个m 的正约数都对应一个d M ,其次不同的m 的正约数对应不同的d M . 所以这些分类d M 就是1,2,,m 的一个划分.因为(,)j m d =,所以,j dq =于是(,) 1.m q d =因为1,j m ≤≤所以1.m q d≤≤ 这样满足上式的q 就是模m d 的简系,所以q 的个数为().mdϕ 这就是说满足d M 的元素个数为().md ϕ所以|().d mm m d ϕ=∑注意到||()()d md mmd dϕϕ=∑∑.所以|().d md m ϕ=∑7.设n 是正整数,证明：2i11|1()(1e).jk nd d j k d nn d πϕ===-∑∑∏证明：令2ie .j dj πε=则2i 11e().jk ddk dj k k πε===∑∑若(,)1j n =,则(,)1j d =,则 1.j ε≠于是1()0.dkjk ε==∑从而2i 1e0.jk ddk π==∑所以2i1|1(1e) 1.jk d d k d nd π=-=∑∏ 若(,)1j n >,则存在|.d n 使得|.d j 于是此时2ie1.j dj πε==所以2i 11e().jk ddk dj k k d πε====∑∑2i 1|1(1e )0.jk d d k d nd π=-=∑∏ 也就是说若(,)1j n =时, 2i 1|1(1e) 1.jk d d k d n d π=-=∑∏若(,)1j n >时,2i1|1(1e )0.jk d d k d nd π=-=∑∏2i 11|1(1e )jk nd d j k d n d π==-∑∑∏计算得恰好就是与n 互素的j 的个数. 故2i11|1()(1e).jk nd d j k d nn d πϕ===-∑∑∏8.给定整数9.a ≥证明：至多存在有限个正整数,n 同时满足下列条件：(1)()n a τ=；(2)|()().n n n ϕσ+证明：设*()(),.n n ns s N ϕσ+=∈ 因为|||()(),().d nd nd nn n n d n d d dϕμσ===∑∑∑所以|()1.d nd s dμ+=∑注意到(){1,0,1},d μ∈-所以()1{0,1,2}.d μ+∈ 设12m d d d <<<是n 的所有正约数中满足()1d μ≠-的那些.先证明引理 ()0.n μ=引理的证明(反证法) 假设()0,n μ≠即n 无平方因子.则1212,.k k n p p p p p p =<<< 于是121212()()(1)(1)(1)(1)(1)(1)k k k n n p p p p p p p p p s ϕσ+=---++++=.因为()29,kn a τ==>所以 4.k ≥ 若n 是奇数,所以12,,,k p p p 都是奇素数, 于是12122|(1)(1)(1)(1)(1)(1),kk k p p p p p p ---++++从而2|,2.k k s s ≥ 但12121111114(1)(1)(1)(1)(1)(1)1()2,3k k k k s p p p p p p =---++++<+<矛盾. 若n 是偶数,所以12,p =2,,k p p 都是奇素数, 于是112122|(1)(1)(1)(1)(1)(1),k k k p p p p p p ----++++从而222|,2.k k s s --≥但22222111311134616(1)(1)(1)(1)()2()2,22223525k k k k k s p p p p ---=--+++<+⋅=+<矛盾. 于是假设不成立,所以()0.n μ= 由引理知道.m d n = 回到原题,|1()1()1.mi d ni id d s dd μμ=++==∑∑下面我们证明12(2),1,2,,.i i d m i m -≤=11()121mi i id s md d μ=+≤=≤∑,所以12.d m ≤这就证明了1i =时结论成立. 假设1,m i ≥>且对1j i ≤<,均有12(2).j j d m -≤11()1()12.i mj j j j ijjid d ms d d d μμ-==++-=≤∑∑11()1i j j jd s d μ-=+-∑为正有理数,通分约分后分母至多为121i d d d -,分子至少为1,所以11121()11.i j j ji d s d d d d μ-=-+-≥∑从而12121,i i m d d d d -≥于是0121122221212(2)(2)i i i i d md d d m m --++++-≤≤=.这就证明了12(2),1,2,,.i i d m i m -≤=特别地1122(2)(2)m a m n d m a --=≤≤.这就证明满足要求的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.。