《初一寒假第4讲同余》由会员分享，可在线阅读，更多相关《初一寒假第4讲同余（9页珍藏版）》请在金锄头文库上搜索。
1、第四讲 同 余 定义 ：给定正整数 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，记为 a b (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
2、 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, , m k)；(4) a b (mod m) (a, m) = (b, m)；设
3、 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 的倍数，这是为什么
4、？ 【解析】10 0 1，101 1，102 1，103 1， (mod 11)20013240246135.()().)(mod1nNaa【例 2】 5467231545 能否被 7 整除。【解析】71113=1001100 1，103 1，106 1，109 1， (mod 7)5467231545=545+231103+467106 +5109根据同余的可乘与可加性，5467254()247()5mod7)545-231+467-5=776 是除以 7 余 6 的。 这样原数是除以 7 余 6 的。【补充】我们要求某数除以 37 的余数，只需从右到左把原数分成若干个 3 位数，再把这些
5、3 位数加起来求余数，请简述理由。【解析】3727=999 所以 10(mod37)这个同余式说明任意整数，可以把它的任意位置上的数字平移 3 位（当然要用 0占位，新位还有可能进位），得到一个与原数同余的数（模 37）。把分离出来的 3 位数平移到小数点左侧，得到的新数与原数同余。平移看似麻烦，其 实可以解决很多比较复杂的问题。【例 3】 是不是质数，数学家用了 90 年才知道。求证它有个约数是 641。.125【解析】依次验算同余式22 4，24 16，28 256，216 154，232 1 (mod 641)。因此 0 (mod 641)，15即 641 。125【例 4】 求(257
6、 33 46)26 被 50 除的余数。【解析】 (257 33 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。【总结】一般而言，知道一个整数的多少次幂关于模同余于 是非常有用的。1我们证明以下命题(欧拉定理)：两个正整数(a,b)=1 则存在正整数 r 满足1mod)rab【证明】考察 除以 b 的余数234,.a根据抽屉原理，必有 (od)0m1()nnab其中 mn。令 r=m-n 即得所证。【补充】求证存在某数是 2011 的倍数，数字和是
7、 2011。【解析】根据欧拉定理，必有正整数 r 满足234111122324200.(mod0).1()rrrrrrrr这 3 组数互不相等。分别从这 3 组选出 a,b,c 个求和。只要满足 201|()abcc就能满足题目的两个条件。一组解是（a,b,c, ）=(1820,9,182)【例 5】求 81234 被 13 除的余数。【解析】只要注意到 88=64 是余-1 的。所以答案是-1。【例 6】27 个国家各派两名代表参加会议，54 人坐成一圈。求证：不可能同国的代表都是隔着 9 个人。【解析】按照顺时针顺序报数，不妨设 1 与 11 同国，那么 21 与 31 同国， 41 与
8、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】求证 616|2351kk【解析】经检验，以下同余式成立在下一讲会交代为什么有这个巧合。662351(mod7)6162351(mod7)kk所以整除成立。【补充】p 是大于 3 的质数，求证 43|761p【解析】我们
9、还是找余数是 1 或-1 的情形。3371,6(mod4)大于 3 的质数，除以 6 只能余 1 或 5。分两种情况 讨论。p 是除以 6 余 1 的， 76(mod43)pp 是除以 6 余 5 的， 5961(od43)【例 8】把 11111,11112,99999 按照任意顺序写成一串，求证得到的数不是 2 的幂。【解析】只要证明除了 2 之外必有其它质因子，采用平移思想。由于都是 5 位数，我们应找到某个特殊模，使得在这个特殊模之下，原数任何数字可以平移 5 位，所得到的新数对该模余数不变。明显成立。10(mod9)原数 12314.9(mod9)这是因为把所有出现的 5 位数平移到
10、小数点左边，余数不变。求和得到原数 589(mod)这样原数必有约数 11111，所以不是 2 的幂。【例 9】 ，求 n。证明 总不是 7 的倍数。21(od7)n1n【解析】通过找规律发现 2 的幂除以 7 的余数是循环的：12345,.(mod)所以满足 的自然数 n 是 3 的倍数 0,3,621(mod7)n根据上面列出的同余式，2 的幂除以 7 得到的余数不会是 6，所以 总不是 721n的倍数。【例 10】 ，求自然数 n。3|(21)n【解析】自然数列除以 3 的余数周期是 3,2 的幂除以 3 的余数周期是 2.所以对 n 除以 6（最小公倍数）的余数分类讨论。答案是：除以
11、6 余 1,2 的数。【例 11】沿圆周写下 2010 个数码，从某一位开始，顺时针读出一个 2010 位数， 这个数能被 27 整除。证明：无论从哪一位开始顺时针读出的 2010 位数，都被 27 整除。【解析】假设这个能被 27 整除的数是 10A+a，a 是个位。只要证明把 a 挪到首位依然能被 27 整除。也就是 能被 27 整除。进一步归结为2091aA能被 27 整除。()()a20127|9,|【例 12】s=1920212223242526272829307677787980 能否被1980 整除？【解析】1980=99 20 （99,20）=1该数明显被 20 整除，只需检查
12、是否被 99 整除。23807918071.9(mod)s注意到可以凑对 99=19+80=20+79=所以整除。【例 13】 被 7 除余数？234101010.【解析】由于余数的积性与和性，最下面的 10 可以替换成 3。3 的幂模 7 余数周期是 6，所以要求出除以 6 分别余几。2341010,.除以 6 都余 4，因为都是偶数，且除以 3 余 1。2341010104.5(mod7)【例 14】已知 n 位数 111111111 能被 2011 整除，求证：22222220000.00001111.111111 能被 2011 整除。其中 2 与 0 各是 n+1 个，1有 2n+2
13、 个。【解析】由条件得知 10(mod21)n这个同余式是说，一个数中的任意一个数字可以平移 n 位，使得原数除以 2011 的余数不变。那么对要考查的被除数做保持余数的变形：首先去掉前 n 个 2，前 2n 个 1（用 0 占位），然后把剩下的 2 右移 3n 位，得到了2011,说明原数是 2011 的倍数。【例 15】求证：S=111111111（2011 个 1）的倍数数字和最小是 2011。【解析】 201(mod)这说明 S 的倍数减去 的倍数仍然是 S 的倍数。假设存在 S 的某个倍数，数201字和小于 2011。不妨设这样的数最小是 x。x 至少应该是 2012 位数。如何减掉
14、的倍数呢？首先在首位上去掉 1，这时数字和减小 1。然后应该在第 2012201位加上 1。如果没进位，数字和不变。如果进位了，数字和变小。总之找到了更小的倍数，数字和小于 2011，这和 x 的选取矛盾。所以 S 的倍数数字和最小是2011。习题1 求证 12|(a-b)(b-c)(c-d)(d-a)(a-c)(b-d)。a,b,c,d 是整数。解析：根据抽屉原理，必有两数对 3 同余。然后 说明：无论其中有多少个奇数，都能找到两个括号都是偶数。2 求证 是 3 的倍数。其中 n 是整数。321n解析： 22214.()16nn明显是整数，3 倍即是题目中的数。3 ， （5，d）=125|ambc求证存在整数 n 满足 32|cnba解析：n 是 m 模 5 的倒数。4 求最小的三位数 n 满足 。38(mod10)解析： 31928(od10)
