完全剩余系与缩剩余系的性质及解法

《完全剩余系与缩剩余系的性质及解法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、6中等数学完全剩余系与缩剩余系的性质及解法何忆捷(华东师范大学理工学院数学系2012级博士研究生，200041)中图分类号：0156．1文献标识码：A文章编号：1005—6416(2015)06-0006—06(本讲适合高中)价于其均与n互素，且关于模凡两两不同余．剩余类与剩余系是初等数论中的重要概性质2若a(1≤i≤12)构成模n的完念．在数学竞赛中，除数论问题外，许多组合系，、m∈Z，(m，12)=1，则k+(1≤≤n)题、甚至代数题也与剩余类、剩余系有密切的也构成模的完系；联系．在解题时，不仅需要熟悉剩余系(完全若a(1≤i≤(n))构成模的缩系，剩余系或缩

2、剩余系)的性质，还经常需要借、m∈Z，(m，n)=1，贝0n+mn(1≤i≤助整体化思想来考虑剩余系．(n))也构成模的缩系．性质3若a(1≤i≤n)构成模凡的完1知识介绍系，则1．1定义一(±!2(1)剩余类对正整数n，把全体整数按模12的余数『詈(modn)，凡为偶数；三分成／2类，每一类数的全体称为模12的一个【0(modn)，n为奇数．剩余类(或称同余类)．性质4若a、b(1≤i≤(n))均构成(2)完全剩余系模n的缩系，则在模12的每个剩余类中各取一个元素，则这n个数就组成模n的一个完全剩余系酊6(m。d凡)．(以下简称完系)．性质3与性质4是从整体的角

3、度考虑完(3)缩剩余系系和缩系，这样的想法也是解决许多问题的在任意一个模n的完全剩余系中，仅保出发点．以下两例是其简单应用．留与n互素的那些数(共(凡)个数，其中，2应用举例(n)为欧拉函数)，则这(12)个数组成模12的一个缩剩余系(或称既约剩余系、简化剩例1设儿为偶数，0i、bi(1≤i≤n)均构余系，以下简称缩系)．成模n的完系．证明la+b(1≤i<~／2)不构成1．2常用性质模凡的完系．性质1对于／2个整数，其构成模n的证明由性质3知完系等价于其关于模n两两不同余；对于(n)个整数，其构成模的缩系等∑ai三∑b三詈(mod／2)．收稿13期：2015—0

4、2—02则∑i=1(。+bi)三号+2~2(m。d)．2015年第6期7故a+bi(1≤≤n)不构成模n的完系．解由于a。，a：，⋯，a构成模n的缩例2设整数n>1，(a，n)=1．证明：系，而(n，2)=1，则2a，2a，⋯，2a也构成a‘三1(modn)．模n的缩系．证明设a1，a2，⋯，()构成模17,的缩系．由性质2知aal，aa2，⋯，aa)也构成模故Ink=lsinaZnkl_I靠k=lsinIn的缩系．ain】j[cos根据性质4得k=lk=lZnk1．口l02⋯a()兰(aa1)(aa2)⋯(aa())因为立Sin≠o'所以，=a纵ak=lIa2⋯

5、a∞()(modn)．又(aIa2~o．a)，n)=1，故Il~COSanSkl=1．口‘兰1(modn)．【注】本题即为欧拉定理．下面考虑nc。s的符号，只需确定k=l接下来再看几个例子．例3设n为正偶数．证明：在n×n矩阵0。，0：，⋯，口中大于詈的数的个数．l2n不妨设0n—al>n—a2>⋯>n—am>0，A=342且n—a(1≤≤m)也构成模n的缩系．：：：●●●从而，a+1一=n—a(1≤≤m)．凡1n一1中找不到一组1，2，⋯，n，其两两不同行且不因此，0。，0，⋯，0中恰有一半大于詈同列．(注意每个口均不为)．

6、证明反证法．假设有一组1，2，⋯，两两不同行且不同列，记这组中的k(1≤k≤n)在第a行故亘cos，号I蕻cosnl第6列．则a、b(1≤i≤n)分别构成模n的=(一1)丁(m=(n)为偶数)．兀为·另一方面，根据矩阵A的特点知【注】这是一道三角公式与剩余系性质的af+bf兰+1(modn)．)综合题，关键思想是从整体考虑模n的缩系故a+b(1≤≤凡)也构成模n的完系．al，a2，⋯，a与20l，2口2，⋯，20，结合诱导公注意到，17,为偶数，上述结论与例1矛式建立耳msin与sin之间的关系，盾．因此，矩阵中不存在一组1，2，⋯，n两两=1，=1，不同行且不同

7、列．恰能求出nCOS的绝对值．值得注意的【注】本题中，式①刻画了矩阵的特征，将组合问题转化为一个关于完系的常规问题．是，若本题中a，，a，⋯，a仅仅为模n的(任例4设奇数凡>1．求nc。s竽的值，意的)缩系，则无法判定立k：1c。sl／,的符号．其中，a。，a，⋯，a为所有不大于n且与n互例5对以下两个问题，分别求正整数n素的正整数．的所有可能值：8中等数学(1)存在口1，02，⋯，n，使得0、0l+i(2)若存在整数0、b(1≤i≤n)，使得(1≤i≤)分别构成模n的完系；0、6、口+6、口一6(1≤i≤n)均构成模n的(2)存在口1，02，⋯，0，使得口、0+

8、i、完系，