高考数学母题：同余理论.doc

第四讲:同余理论 31 第四讲:同余理论 同余是初等数论的基本概念、重要的研究对象、广泛用场的方法,在数学竞赛中具有中心位置. 同余定义:对正整数m,若整数a与b被除m的余数相等,则称a与b对模m同余,记作a≡b(modm); 同余性质:①若a≡b(modm),b≡c(modm),则a≡c(modm);②若a≡b(modm),c≡d(modm),则(ac)≡(bd)(modm), ac≡bd(modm),an≡bn(modm);③若ac≡bc(modm),(c,n)=d,则a≡b(mod),特别地,若ac≡bc(modm),(c,n)=1,则a≡b (modm);④若n|m,a≡b(modm),则a≡b(modn);若a≡b(modmi),则a≡b(modm1m2…mk),则⑤若(a,b,m)=d,a≡b(modm),则≡(mod);⑥若a≡b(modm),则(a,m)=(b,m); 费马定理:①若p为质数,且(a,p)=1,则ap-1≡1(modp);②若p为质数,对任意整数a,ap≡a(modp); 完全剩余:①同余类:由关于模m同余的整数组成的集合Mi={n=n=qm+i,q∈Z,i=0,1,2,…,m-1}叫做模m的同余类;当i≠j时,Mi∩Mj=;=Z;②完全剩余系:从每个Mi中取出一个数ai组成的集合{a0,a1,a2,…,am-1}叫做模m的完全剩余系;模m的完全剩余系{0,1,2,…,m-1}叫做模m的最小非负完系;m个连续整数构成模m的一个完全剩余系;如果(k,m)= 1,则{ka0+b,ka1+b,ka2+b,…,kam-1+b}是模m的一个完全剩余系; 同余方程:①一次同余方程:方程叫ax≡b(modm)(ma)做一次同余方程;②基本结论:(i)若(a,m)=1,则ax≡b(modm)有且只有一解;(ii)若(a,m)=d1,db,则ax≡b(modm)无解;(iii)若(a,m)=d1,d|b,则ax≡b(modm)有d个解,并且,若 αx≡β(modm1)的唯一解为x≡r(modm1),则ax≡b(modm)的d个解为x=r+km1(modm1),k=0,1,2,…,d-1,其中,α=,β=,m1=;③孙子定理(中国剩余定理):若m1,m2,…,mk(k≥2)是两两互素的正整数,对任意整数a1,a2,…,ak,一次同余方程组:必有解x≡(M1N1a1+M2N2a2+…+MkNkak)(modm),其中m=m1m2…mk,Mi=,Ni满足MiNi≡1(modmi)(即Ni为Mi对模m的逆)(i=1,2,…,k). 1.同余性质: [例1]:(2013年欧洲女子数学奥林匹克试题)求所有的正整数a、b,满足:存在三个连续的整数,使得多项式P(n)=的值为整数. [解析]:设三个连续的整数分别为x-1、x、x+1,由多项式P(n)=的值为整数(n5+a)≡0(modb);所以, A=(x+1)5-(x-1)5=10x4+20x2+2≡0(modb),B=(x+1)5-x5=5x4+10x3+10x2+5x+1≡0(modb),C=(x+1)5+(x -1)5-2x5=20x3+10x≡0(modb)D=4xA-(2x2+3C=-22x≡0(modb)22B+(5x3+10x2+10x+5)D=22≡0(modb)b=1,2,11,22;又因B=5x(x3+1)+10x2(x+1)+1为奇数b为奇数b=1,11;①当b=1时,P(n)=n5+a,对任意的正整数a均满足条件;②当b=11时,由n≡0,1,2,…,10(mod11)n5≡0,1,10;由(n5+a)≡0(mod11)a≡0,10,1(mod11),但当a≡0(mod11)时,不合题意;故(a,b)=(k,1),(11k-1,11),(11k-10,11)(k∈N+). [练习1]: 1.(2009年全国高中数学联赛天津预赛试题)甲在黑板上写下正整数1,2,…,2009,然后背对黑板,让乙将黑板上的这些数 32 第四讲:同余理论 擦去若干个后再添加擦去数之和被7除的余数.当经过若干次操作以后使黑板上只剩下两个数.其中的一个数是一位数.甲问乙:“剩下的两个数中较大的数是几？”乙答:“100”.则剩下的两个数中的那个一位数为_______. 2.①(1980年第14届全苏数学奥林匹克试题)接连写出19至80的两位数,问:所得到的数19