初一寒假第4讲同余.doc

第四讲 同 余 定义 ：给定正整数m，如果整数a与b之差被m整除，则称a与b对于模m同余，或称a与b同余，模m，记为a b (mod m)此时也称b是a对模m的同余。如果整数a与b之差不能被m整除，则称a与b对于模m不同余，或称a与b不同余，模m，记为ab (mod m)。同余与整除的等价性。以下两个说法等价：() a b (mod m)；() 存在整数q，使得a = b + qm；关于同余的基本事实 ：a a (mod m)；a b (mod m) b a (mod m)；a b，b c (mod m) a c (mod m)。同余式中可以使用的变形：若a b (mod m)，c d (mod m)， 则 a + c b + d (mod m)；（可加，和性）ac bd (mod m)。（可乘，积性）这两个变形方法经常用于同余式的化简，使很大的数变得很小。例题中多次使用。更高级的变形：针对模的变换(1) a b (mod m)，dm，d 0 a b (mod d)；(2) a b (mod m)，k 0，kN ak bk (mod mk)；(3) a b (mod mi )，1 i k a b (mod m1, m2, L, mk)；(4) a b (mod m) (a, m) = (b, m)；设a=km+b即可证明(5) ac bc (mod m)，(c, m) = 1 a b (mod m)。利用整除和同余的等价性证明。数论倒数：（a,m）=1,m1 如果b是1到m-1之间的整数，并且ab=1(mod m)，那么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 (mod 11)【例2】 5467231545能否被7整除。【解析】71113=1001100 1，103 -1，106 1，109 -1，L (mod 7)5467231545=545+231103+467106 +5109根据同余的可乘与可加性，545-231+467-5=776是除以7余6的。这样原数是除以7余6的。【补充】我们要求某数除以37的余数，只需从右到左把原数分成若干个3位数，再把这些3位数加起来求余数，请简述理由。【解析】3727=999 所以这个同余式说明任意整数，可以把它的任意位置上的数字平移3位（当然要用0占位，新位还有可能进位），得到一个与原数同余的数（模37）。把分离出来的3位数平移到小数点左侧，得到的新数与原数同余。平移看似麻烦，其实可以解决很多比较复杂的问题。【例3】 是不是质数，数学家用了90年才知道。求证它有个约数是641。.【解析】依次验算同余式22 4，24 16，28 256，216 154，232 -1 (mod 641)。因此 0 (mod 641)，即641。【例4】 求(25733 + 46)26被50除的余数。【解析】 (25733 + 46)26 (733 - 4)26 7(72)16 - 426 7( -1)16 - 426 (7 - 4)26 326 3(35)5 3(-7)5 = -37(72)2 -21 29 (mod 50)，余数是29。【总结】一般而言，知道一个整数的多少次幂关于模同余于是非常有用的。我们证明以下命题(欧拉定理)：两个正整数(a,b)=1 则存在正整数r满足【证明】考察除以b的余数根据抽屉原理，必有其中mn。令r=m-n即得所证。【补充】求证存在某数是2011的倍数，数字和是2011。【解析】根据欧拉定理，必有正整数r满足这3组数互不相等。分别从这3组选出a,b,c个求和。只要满足就能满足题目的两个条件。一组解是（a,b,c,）=(1820,9,182)【例5】求81234被13除的余数。【解析】只要注意到88=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个同国。得到矛盾。【总结】这里没有列同余式，用了同余的思想：任意给定一个奇数，适当选取k，20k+11总会与这个奇数同余，模54。.【例7】求证【解析】经检验，以下同余式成立 在下一讲会交代为什么有这个巧合。所以整除成立。【补充】p是大于3的质数，求证【解析】我们还是找余数是1或-1的情形。 大于3的质数，除以6只能余1或5。分两种情况讨论。p是除以6余1的，p是除以6余5的，【例8】把11111,11112,99999按照任意顺序写成一串，求证得到的数不是2的幂。【解析】只要证明除了2之外必有其它质因子，采用平移思想。由于都是5位数，我们应找到某个特殊模，使得在这个特殊模之下，原数任何数字可以平移5位，所得到的新数对该模余数不变。明显成立。原数这是因为把所有出现的5位数平移到小数点左边，余数不变。求和得到原数这样原数必有约数11111，所以不是2的幂。【例9】，求n。证明总不是7的倍数。【解析】通过找规律发现2的幂除以7的余数是循环的：所以满足的自然数n是3的倍数0,3,6根据上面列出的同余式，2的幂除以7得到的余数不会是6，所以总不是7的倍数。【例10】，求自然数n。【解析】自然数列除以3的余数周期是3,2的幂除以3的余数周期是2.所以对n除以6（最小公倍数）的余数分类讨论。答案是：除以6余1,2的数。 【例11】沿圆周写下2010个数码，从某一位开始，顺时针读出一个2010位数，这个数能被27整除。证明：无论从哪一位开始顺时针读出的2010位数，都被27整除。【解析】假设这个能被27整除的数是10A+a，a是个位。只要证明把a挪到首位依然能被27整除。也就是能被27整除。进一步归结为能被27整除。【例12】s=1920212223242526272829307677787980能否被1980整除？【解析】1980=9920 （99,20）=1该数明显被20整除，只需检查是否被99整除。注意到可以凑对99=19+80=20+79=所以整除。【例13】被7除余数？【解析】由于余数的积性与和性，最下面的10可以替换成3。3的幂模7余数周期是6，所以要求出除以6分别余几。除以6都余4，因为都是偶数，且除以3余1。【例14】已知n位数111111111能被2011整除，求证：22222220000.00001111.111111能被2011整除。其中2与0各是n+1个，1有2n+2个。【解析】由条件得知这个同余式是说，一个数中的任意一个数字可以平移n位，使得原数除以2011的余数不变。那么对要考查的被除数做保持余数的变形：首先去掉前n个2，前2n个1（用0占位），然后把剩下的2右移3n位，得到了2011,说明原数是2011的倍数。【例15】求证：S=111111111（2011个1）的倍数数字和最小是2011。【解析】这说明S的倍数减去的倍数仍然是S的倍数。假设存在S的某个倍数，数字和小于2011。不妨设这样的数最小是x。x至少应该是2012位数。如何减掉的倍数呢？首先在首位上去掉1，这时数字和减小1。然后应该在第2012位加上1。如果没进位，数字和不变。如果进位了，数字和变小。总之找到了更小的倍数，数字和小于2011，这和x的选取矛盾。所以S的倍数数字和最小是2011。习题1 求证12|(