1、高中数学竞赛专题讲座专题训练同余部分的例题与习题v1.0 可编写可改正同余的见解与应用见解与性质1.定义：若整数 a,b 被整数 m(m1) 除的余数同样 , 则称 a 同余于 b 模 m,或 a,b 对模 m同余 . 记为 ab(modm).余数 r:0 r0,证明必有一个仅由 0 或 1 组成的自然数 a 是 m的倍数 .证明 ：考虑数字全为 1 的数 :1,11,111,1111, 中必有两个在 modm的同一节余类中 , 它们的差即为所求的 a.例 4. 证明从随意 m个整数 a1,a 2, ,a m中 , 必可选出若干个数 , 它们的和 ( 包含只一个加数 ) 能被 m整除 .证明
2、：考虑 m个数 a1,a 1 +a2,a 1+a2+a3, ,a 1+a2+ +am, 假如此中有一个数能被 m整除 , 则结论建立 , 不然 ,必有两个数属于 modm的同一节余类 , 这两个数的差即知足要求 .例 5. 证明数 11,111,1111, 中无平方数 .证明： 因随意整数 n20或 1(mod4), 而 111111111 3(mod4), 所以 , 数 11,11 1,1111, 中无平方数 .例 6. 确立 n5=1335+1105+845 +275 .22v1.0 可编写可改正55555n个位数字为 4, 明显 n的首位数字为1, 进一步估解：因 n 3+0 +4 +7
3、3+4+74(mod10), 所以计55+(84+27)555555133 167, 所以 n可取 134,144,154,164, 又:n21333133133 , 所以 ,n445553(mod3), 故 n=144.n 1+(-1)注： 欧拉猜想4 个自然数的5 次方之和不是5次方,于 1962年被三位美国数学家颠覆, 例 6 就是他们举的反例 .例 7.求 32006 的个位数及末两位数字 .解：(1)即求a(0 a9),使得2006a(mod10). 329 -1(mod10),420062004+24X501+2331(mod10),333 32 (mod10), 故32006 的
4、个位数是9;(2)即求b(0 b99), 使得32006b(mod100). 注意到 :4X25=100 且(4,25)=1,34811(mod5), 34816(mod25),381216- 54 -43611(mod25) , 3 66 -9(mod25),320220 , 由, 得(mod25)3 - 241(mod25); 31(mod4)3 1(mod4)20200631(mod100) , 3 320 X100? 3629(mod100), 故32006 的末两位数字是 29.例 8. 求 1 X3X5X7 X X2005 的末 3 位数字 .解：注意到 :8X125=1000 且
5、(8,125)=1 ，(2n -3)(2n- 1)(2n+1)(2n+3) (4n 2-9)(4n 2- 1) 1(mod8)， 及M=1 X3 X5X 7 X X2005=125m是 1003 个奇数之积， M1 X3 X57(mod8), 125m 5m7(mod8)， m3(mod8) ， M125m125X3375(mod8)， M125m375(mod8). 即 1 X3 X5 X 7 X X2005 的末 3 位数字为 375.例 9.求大于 5 的素数平方被30 除的余数 .解：设 p 是大于 5 的素数 , 且 pr(mod30)(rn1, 求最小的 m+n使得 1000|19
6、78 m-1978 n.mnnnk- 1)0(mod233解：令 k=m-n, 则 1978 -19780(mod1000)2? 989(1978? 5 )2n0(mod2 3 ) n 319783(mod5) 1978420201978k1，1(mod5)， 19783(mod25) 1978 3 0(mod 53 )1(mod25)，1978 -22(mod53),(-22)20202044232026(25 -3)3 (243)7(50 -1)26(mod5 ) 1978(mod53),1978 40(25+1) 251(mod53),1978 60(25+1)(50+1) 76(mod
7、5 3),1978 80(50+1) 2101(mod53),1978 100(25+1)(100+1) 1(mod5 3), 100|k k 最小 =100, m+n=m-n+2n 最小 =106.例 13. 设 a1, a2 , a3, 是整数序列 , 此中有无量多项为正整数 , 也有无量多项为负整数. 假定对每个正整数n , 数 a1 , a2 , a3 , an 被 n 除的余数都各不同样 . 证明 : 在数列 a1, a2 , a3,中 , 每个整数都恰好出现一次 .证明： 数列各项同时减去一个整数不改变此题的条件和结论, 故不如设 a1=0. 此时对每个正整数k 必有akk: 若a
8、k k, 取 n=ak, 则 a1ak0(mod n),矛盾 . 此刻对 k 概括证明 a1,a 2, ,a k 适合重排后是绝对值小于k 的 k 个相邻整数 .k=1明显 . 设 a1,a 2, ,ak 适合重排后为 (k 1i),0, ,i (0i k 1), 因为 a,a , ,a,ak+1是 (mod k+1) 的一个完满节余系, 故必 a i+1(mod k+1),但a k+1, 所以12kk+1k+1ak+1 只好是 i+1或 (k i),进而 a1,a 2, ,a k,a k+1 适合重排后是绝对值小于k+1 的 k+1个相邻整数 .由此得到 :1). 任一整数在数列中最多出现一
9、次;2). 若整数 u 和 v (ua,(p,a)=1, x2,x 3,x p+2 这 p+1 个数中必有两个属于modp的同一节余类 ,即有 mn2, 使得 xmxn(modp), 由题意有 xm-x na(x m-1-x n-1 ) 0(modp), 挨次类推 , 有 xm-n+1-x 10(modp), 即有55v1.0 可编写可改正p| xm-n+1, 因数列增 , 所以 xm-n+1p, x m-n+1 不是质数 .2. 确立所有正整数 n, 使方程 xn+(2+x) n+(2-x) n=0 有整数解 .解： 明显 , 若 n 为偶数 , 则方程无实数根 , 若 n=1, 则 x=-
10、4. 当 n3 且为奇数时方程左端是首项为 1,常数项为 2n+1 的多项式其整解只好是 -2 t (t 为非负整数 ) 形式 : 若 t=0,1,2 则 x=-1,-2,-4 都不是方程的根 ;若 t 3, 则 -2 nt +(2-2 t ) n+(2+2 t ) n=0-2 n(t-1) +(1-2 t-1 ) n+(1+2 t-1 ) n=0， -2 n(t-1) +(1-2 t-1 ) n+(1+2 t-1 ) n2(mod4)左端 0. 综上知 , 仅当 n=1 时, 原方程有独一整解x=-4.3.问能否存在一个无量项素数数列p ,p , ,p, 对随意 n 知足 |pn+1-2p |=1请说明原因 .12nn解： 若存在 , 则由 pn+1=2pn1p n 知p n 递加 , p33, p 31 或 2(mod3).
