基本支撑体系数学资料竞赛指导初中数学竞赛与课外活动指导专题“百校联赛”一等奖

同余式整除问题一、赛点要求：（一）同余的概念两个整数a和b被同一个正整数m除，所得的余数相同时，称a,b关于模m同余.记作a≡b(modm).如：8和15除以7同余1，记作8≡15(mod7),读作8和15关于模7同余.∵2022=7×286+1，∴2022≡1(mod7)；∵－7和6对于模13同余6（余数是非负数）∴－7≡6（mod13）；∵35和0除以5，余数都是0（即都能整除）∴35≡0（mod5）.（二）用同余式判定数的整除若a≡b(modm)，则m|(a－b).即a－b≡0(modm)m|(a－b).例如：11≡25(mod7)7|(25－11)；或7|(11－25).∵25+35≡2+3≡0(mod5)，∴5|25+35.（三）同余的性质(注意同余式与等式在变形中的异同点)传递性：.可加可乘性：推论可移性：a≡b+c(modm)(a－b)≡c(modm).可倍性：a≡b(modm)ka≡kb(modm)(k为正整数).可乘方：a≡b(modm)an≡bn(modm)(n为正整数).当d是a,b,m的正公因数时，a≡b(modm)(mod).如：2是20，26，6的正公因数，20≡26(mod6)(mod3).（四）根据抽屉原则：任给m+1个整数，其中至少有两个数对于模m同余.即至少有两个，其差能被m整除.例如：任给5个数a,b,c,d,e.其中至少有两个，它们的差能被4整除.∵除以4的余数只有0，1，2，3四种.∴5个数除以4至少有两个同余.二、类型分解：例1.已知：69，90，125除以正整数n有相同的余数.求：n的值解：∵69≡90(modn)，90≡125(modn).∴n|(90－69)，n|(125－90).而21,35的最大公约数是7，记作(21,35)=7(7是质数).∴n=7例2.求388除以5的余数.解：∵38≡3(mod5)，∴388≡38≡(32)4≡(－1)4≡1(mod5).评点：9除以5余4，－1除以5也是余4，∴32≡－1(mod5)例3.求的个位数字.解：∵74k+n与7n的个位数字相同，且9≡1(mod4)，∴99≡19≡1(mod4).∴与71的个位数字相同都是7.例4.求证：7|(22225555+55552222).证明：∵22225555+55552222=(22225)1111+(55552)1111∵2222=7×317+3，5555=7×793+4.∴2222≡3(mod7)；5555≡4(mod7).∴22225≡35≡5(mod7)；55552≡42≡2(mod7).∴22225+55552≡5+2≡0(mod7).即22225≡－55552(mod7).∴(22225)1111≡(－55552)1111≡－(55552)1111(mod7).∴22225555+55552222≡0(mod7).∴7|(22225555+55552222).例5.求使32n－1能被5整除的一切自然数n.解：∵32≡－1(mod5)，∴(32)n≡(－1)n(mod5).32n－1≡(－1)n－1(mod5)∵当且仅当n为偶数时，(－1)n－1=0.∴使32n－1能被5整除的一切自然数n是非负偶数例6.已知：a,b,c是三个互不相等的正整数.求证：a3b－ab3,b3c－bc3,c3a－ca（1986年全国初中数学联赛题）证明：用同余式判定整除法证明当正整数n的个位数是0，1，4，5，6，9时，n3的个位数也是0，1，4，5，6，9.∴这时n3≡n(mod10)；当正整数n的未位数为2，3，7，8时，n3的个位数分别是8，7，3，2.∵8与－2，7与－3，3与－7，2与－8，除以10是同余数，∴这时n3≡－n(mod10)；把三个正整数a,b,c按个位数的情况，分为上述两类时，则至少有两个属于同一类.设a,b的末位数是同一类，那么a3b－ab3≡ab－ab≡0(mod10)；或a3b－ab3≡(－a)b－a(－b)≡0(mod10).∴10|(a3b－ab3)三、专题训练：1.三个数33，45，69除以正整数N有相同余数，但余数不是0，那么N=_______.2.求的个位数字.3.求37除以19的余数；41989除以9的余数.4.求19891990÷1990的余数.5.四个数2836，4582，5164，6522都被同一个正整数除，所得的余数都相同且不是0，求除数和余数.6.求证：7|(33334444+44443333).7.已知：正整数n>2.求证：(mod4).8.任给8个整数，其中必有两个，它们的差能被7整除，试证之.9.求使2n+1能被3整除的一切自然数n.10.已知69，90，125除以N(N>1)有同余数，那么对于同样的N，81同余于()（A）3.（B）4.（C）5.（D）7.（E）8.（1971年美国中学数学竞赛试题）专题训练答案：N=12，6，2.(舍去3，∵余数是0).解法仿例1.个位数字是3.∵7≡－1(mod4),∴7≡(－1)7(mod4)……仿例3余数是18和1.∵37≡－1(mod19)∴原式≡－1≡18(mod19)；41989=(43)66364≡1(mod9)64663≡1663≡1.余数是1.∵1989≡－1(mod1990)∴19891990≡(－1)1990≡1(mod1990).根据题意2836≡4582≡5164≡6522≡r(modm)而且4582－2836=1746,6522－5164=1358.∴m|1746,且m|1358，(1746，1358)=2×97∴m=194,97,2(2不合题意.舍去)答：除数为194，余数是120或除数为97，余数是23∵33334444+44443333≡14444+(－1)3333≡0(mod7).00+11≡11≡3(mod4).8个正整数分别除以7，必有两个或两个以上是同余数∵2≡－1(mod3)∴2n≡(－1)n(mod3)2n+1≡(－1)n+1(mod3)当且仅当n奇数时,(－1)n+1≡0∴能被3整除的一切正整数n是奇数10.(B).四、同步测试：1.选择题(1)方程x2-y2=105的正整数解有(

).（A）一组（B）二组

（C）三组

（D）四组(2)在0,1,2,…，50这51个整数中，能同时被2，3，4整除的有（

）.（A）3个（B）4个

（C）5个

（D）6个2．填空题(1)的个位数分别为_________及_________.(2)满足不等式104≤A≤105的整数A的个数是x×104+1，则x的值________.(3)已知整数y被7除余数为5,那么y3被7除时余数为________.(4)(全俄第14届中学生数学竞赛试题)求出任何一组满足方程x2-51y2=1的自然数解x和y_________.3.(第26届国际数学竞赛预选题)求三个正整数x、y、z满足.4．（1985年上海数学竞赛题）在数列4，8，17，77，97，106，125，238中相邻若干个数之和是3的倍数，而不是9的倍数的数组共有多少组？5．求的整数解.6．求证可被37整除.7．（全俄1986年数学竞赛题）求满足条件的整数x，y的所有可能的值.8．（1985年上海初中数学竞赛题）已知直角三角形的两直角边长分别为l厘米、m厘米，斜边长为n厘米，且l，m，n均为正整数，l为质数.证明：2（l+m+n）是完全平方数.9.(1988年全国初中数学竞赛题)如果p、q、、都是整数，并且p＞1，q＞1，试求p+q的值.同步测试答案：及1.

(2)9.

(3)4.(4)原方程可变形为x2=(7y+1)2+2y(y-7),令y=7可得x=50.3.不妨设x≤y≤z,则,故x≤3.又有故x≥2.若x=2,则,故y≤6.又有,故y≥4.若y=4,则z=20.若y=5,则z=10.若y=6,则z无整数解.若x=3,类似可以确定3≤y≤4,y=3或4,z都不能是整数.4.可仿例2解.5.先求出,然后将方程变形为y=5+x-2要使y为整数,5x-1应是完全平方数,…,解得≡8(mod37),∴88882222≡82(mod37).7777≡7(mod37),77773333≡73(mod37),88882222+77773333≡(82+73)(mod37),而82+73=407,37|407,∴37|N.7.简解:原方程变形为3x2-(3y+7)x+3y2-7y=0由关于x的二次方程有解的条件△≥0及y为整数可得0≤y≤5,即y=0,1,2,3,4,5.逐一代入原方程可知,原方程仅有两组解