资源描述：
《初一寒假第4讲同余.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第四讲同余定义：给定正整数m，如果整数a与b之差被m整除，则称a与b对于模m同余，或称a与b同余，模m，记为aºb(modm)此时也称b是a对模m的同余。如果整数a与b之差不能被m整除，则称a与b对于模m不同余，或称a与b不同余，模m，记为ab(modm)。同余与整除的等价性。以下两个说法等价：(ⅰ)aºb(modm)；(ⅱ)存在整数q，使得a=b+qm；关于同余的基本事实：aºa(modm)；aºb(modm)Þbºa(modm)；aºb，bºc(modm)Þaºc(modm)。同余式中可以使用的变形：若aºb(modm)，c
2、ºd(modm)，则a+cºb+d(modm)；（可加，和性）acºbd(modm)。（可乘，积性）这两个变形方法经常用于同余式的化简，使很大的数变得很小。例题中多次使用。更高级的变形：针对模的变换(1)aºb(modm)，d½m，d>0Þaºb(modd)；(2)aºb(modm)，k>0，kÎNÞakºbk(modmk)；(3)aºb(modmi)，1£i£kÞaºb(mod[m1,m2,L,mk])；(4)aºb(modm)Þ(a,m)=(b,m)；设a=km+b即可证明(5)acºbc(modm)，(c,m)=1Þaºb
3、(modm)。利用整除和同余的等价性证明。数论倒数：（a,m）=1,m>1如果b是1到m-1之间的整数，并且ab=1(modm)，那么b就是a的倒数。倒数要针对某个固定的模。比如1,2,3,4,5,6,7,8,9,10关于模11的数论倒数依次是1,6,4,3,9,2,8,7,5,10。倒数在（a,m）=1情况下,a的模m的数论倒数存在且唯一（同余意义下）。【例1】我们用奇位上的数字和减去偶位上的数字和是不是11的倍数去考察原数是不是11的倍数，这是为什么？【解析】100º1，101º-1，102º1，103º-1，L(mod11
4、)【例2】5467231545能否被7整除。【解析】7×11×13=1001100º1，103º-1，106º1，109º-1，L(mod7)5467231545=545+231×103+467×106+5×109根据同余的可乘与可加性，545-231+467-5=776是除以7余6的。这样原数是除以7余6的。【补充】我们要求某数除以37的余数，只需从右到左把原数分成若干个3位数，再把这些3位数加起来求余数，请简述理由。【解析】37×27=999所以这个同余式说明任意整数，可以把它的任意位置上的数字平移3位（当然要用0占位，新位
5、还有可能进位），得到一个与原数同余的数（模37）。把分离出来的3位数平移到小数点左侧，得到的新数与原数同余。平移看似麻烦，其实可以解决很多比较复杂的问题。【例3】是不是质数，数学家用了90年才知道。求证它有个约数是641。.【解析】依次验算同余式22º4，24º16，28º256，216º154，232º-1(mod641)。因此º0(mod641)，即641½。【例4】求(25733+46)26被50除的余数。【解析】(25733+46)26º(733-4)26º[7×(72)16-4]26º[7×(-1)16-4]26º(7
6、-4)26º326º3×(35)5º3×(-7)5=-3×7×(72)2º-21º29(mod50)，余数是29。【总结】一般而言，知道一个整数的多少次幂关于模同余于是非常有用的。我们证明以下命题(欧拉定理)：两个正整数(a,b)=1则存在正整数r满足【证明】考察除以b的余数根据抽屉原理，必有其中m>n。令r=m-n即得所证。【补充】求证存在某数是2011的倍数，数字和是2011。【解析】根据欧拉定理，必有正整数r满足这3组数互不相等。分别从这3组选出a,b,c个求和。只要满足就能满足题目的两个条件。一组解是（a,b,c,）=(
7、1820,9,182)【例5】求81234被13除的余数。【解析】只要注意到8×8=64是余-1的。所以答案是-1。【例6】27个国家各派两名代表参加会议，54人坐成一圈。求证：不可能同国的代表都是隔着9个人。【解析】按照顺时针顺序报数，不妨设1与11同国，那么21与31同国，41与51同国，61与71同国…也就是说报20k+1的与20k+11的同国。报1的报的数是54m+1，我们令20k+11=54m+1，随便解出一个正整数解m=5,k=13。这说明报1的与从他的位置逆时针数第10个同国。得到矛盾。【总结】这里没有列同余式，用
8、了同余的思想：任意给定一个奇数，适当选取k，20k+11总会与这个奇数同余，模54。.【例7】求证【解析】经检验，以下同余式成立在下一讲会交代为什么有这个巧合。所以整除成立。【补充】p是大于3的质数，求证【解析】我们还是找余数是1或-1的情形。大于3的质数，除以
