基本支撐體系數(shù)學資料競賽指導初中數(shù)學競賽與課外活動指導專題“百校聯(lián)賽”一等獎

同余式整除問題一、賽點要求：（一）同余的概念兩個整數(shù)a和b被同一個正整數(shù)m除，所得的余數(shù)相同時，稱a,b關(guān)于模m同余.記作a≡b(modm).如：8和15除以7同余1，記作8≡15(mod7),讀作8和15關(guān)于模7同余.∵2022=7×286+1，∴2022≡1(mod7)；∵－7和6對于模13同余6（余數(shù)是非負數(shù)）∴－7≡6（mod13）；∵35和0除以5，余數(shù)都是0（即都能整除）∴35≡0（mod5）.（二）用同余式判定數(shù)的整除若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.（三）同余的性質(zhì)(注意同余式與等式在變形中的異同點)傳遞性：.可加可乘性：推論可移性：a≡b+c(modm)(a－b)≡c(modm).可倍性：a≡b(modm)ka≡kb(modm)(k為正整數(shù)).可乘方：a≡b(modm)an≡bn(modm)(n為正整數(shù)).當d是a,b,m的正公因數(shù)時，a≡b(modm)(mod).如：2是20，26，6的正公因數(shù)，20≡26(mod6)(mod3).（四）根據(jù)抽屜原則：任給m+1個整數(shù)，其中至少有兩個數(shù)對于模m同余.即至少有兩個，其差能被m整除.例如：任給5個數(shù)a,b,c,d,e.其中至少有兩個，它們的差能被4整除.∵除以4的余數(shù)只有0，1，2，3四種.∴5個數(shù)除以4至少有兩個同余.二、類型分解：例1.已知：69，90，125除以正整數(shù)n有相同的余數(shù).求：n的值解：∵69≡90(modn)，90≡125(modn).∴n|(90－69)，n|(125－90).而21,35的最大公約數(shù)是7，記作(21,35)=7(7是質(zhì)數(shù)).∴n=7例2.求388除以5的余數(shù).解：∵38≡3(mod5)，∴388≡38≡(32)4≡(－1)4≡1(mod5).評點：9除以5余4，－1除以5也是余4，∴32≡－1(mod5)例3.求的個位數(shù)字.解：∵74k+n與7n的個位數(shù)字相同，且9≡1(mod4)，∴99≡19≡1(mod4).∴與71的個位數(shù)字相同都是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整除的一切自然數(shù)n.解：∵32≡－1(mod5)，∴(32)n≡(－1)n(mod5).32n－1≡(－1)n－1(mod5)∵當且僅當n為偶數(shù)時，(－1)n－1=0.∴使32n－1能被5整除的一切自然數(shù)n是非負偶數(shù)例6.已知：a,b,c是三個互不相等的正整數(shù).求證：a3b－ab3,b3c－bc3,c3a－ca（1986年全國初中數(shù)學聯(lián)賽題）證明：用同余式判定整除法證明當正整數(shù)n的個位數(shù)是0，1，4，5，6，9時，n3的個位數(shù)也是0，1，4，5，6，9.∴這時n3≡n(mod10)；當正整數(shù)n的未位數(shù)為2，3，7，8時，n3的個位數(shù)分別是8，7，3，2.∵8與－2，7與－3，3與－7，2與－8，除以10是同余數(shù)，∴這時n3≡－n(mod10)；把三個正整數(shù)a,b,c按個位數(shù)的情況，分為上述兩類時，則至少有兩個屬于同一類.設(shè)a,b的末位數(shù)是同一類，那么a3b－ab3≡ab－ab≡0(mod10)；或a3b－ab3≡(－a)b－a(－b)≡0(mod10).∴10|(a3b－ab3)三、專題訓練：1.三個數(shù)33，45，69除以正整數(shù)N有相同余數(shù)，但余數(shù)不是0，那么N=_______.2.求的個位數(shù)字.3.求37除以19的余數(shù)；41989除以9的余數(shù).4.求19891990÷1990的余數(shù).5.四個數(shù)2836，4582，5164，6522都被同一個正整數(shù)除，所得的余數(shù)都相同且不是0，求除數(shù)和余數(shù).6.求證：7|(33334444+44443333).7.已知：正整數(shù)n>2.求證：(mod4).8.任給8個整數(shù)，其中必有兩個，它們的差能被7整除，試證之.9.求使2n+1能被3整除的一切自然數(shù)n.10.已知69，90，125除以N(N>1)有同余數(shù)，那么對于同樣的N，81同余于()（A）3.（B）4.（C）5.（D）7.（E）8.（1971年美國中學數(shù)學競賽試題）專題訓練答案：N=12，6，2.(舍去3，∵余數(shù)是0).解法仿例1.個位數(shù)字是3.∵7≡－1(mod4),∴7≡(－1)7(mod4)……仿例3余數(shù)是18和1.∵37≡－1(mod19)∴原式≡－1≡18(mod19)；41989=(43)66364≡1(mod9)64663≡1663≡1.余數(shù)是1.∵1989≡－1(mod1990)∴19891990≡(－1)1990≡1(mod1990).根據(jù)題意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不合題意.舍去)答：除數(shù)為194，余數(shù)是120或除數(shù)為97，余數(shù)是23∵33334444+44443333≡14444+(－1)3333≡0(mod7).00+11≡11≡3(mod4).8個正整數(shù)分別除以7，必有兩個或兩個以上是同余數(shù)∵2≡－1(mod3)∴2n≡(－1)n(mod3)2n+1≡(－1)n+1(mod3)當且僅當n奇數(shù)時,(－1)n+1≡0∴能被3整除的一切正整數(shù)n是奇數(shù)10.(B).四、同步測試：1.選擇題(1)方程x2-y2=105的正整數(shù)解有(

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

（C）三組

（D）四組(2)在0,1,2,…，50這51個整數(shù)中，能同時被2，3，4整除的有（

）.（A）3個（B）4個

（C）5個

（D）6個2．填空題(1)的個位數(shù)分別為_________及_________.(2)滿足不等式104≤A≤105的整數(shù)A的個數(shù)是x×104+1，則x的值________.(3)已知整數(shù)y被7除余數(shù)為5,那么y3被7除時余數(shù)為________.(4)(全俄第14屆中學生數(shù)學競賽試題)求出任何一組滿足方程x2-51y2=1的自然數(shù)解x和y_________.3.(第26屆國際數(shù)學競賽預選題)求三個正整數(shù)x、y、z滿足.4．（1985年上海數(shù)學競賽題）在數(shù)列4，8，17，77，97，106，125，238中相鄰若干個數(shù)之和是3的倍數(shù)，而不是9的倍數(shù)的數(shù)組共有多少組？5．求的整數(shù)解.6．求證可被37整除.7．（全俄1986年數(shù)學競賽題）求滿足條件的整數(shù)x，y的所有可能的值.8．（1985年上海初中數(shù)學競賽題）已知直角三角形的兩直角邊長分別為l厘米、m厘米，斜邊長為n厘米，且l，m，n均為正整數(shù)，l為質(zhì)數(shù).證明：2（l+m+n）是完全平方數(shù).9.(1988年全國初中數(shù)學競賽題)如果p、q、、都是整數(shù)，并且p＞1，q＞1，試求p+q的值.同步測試答案：及1.

(2)9.

(3)4.(4)原方程可變形為x2=(7y+1)2+2y(y-7),令y=7可得x=50.3.不妨設(shè)x≤y≤z,則,故x≤3.又有故x≥2.若x=2,則,故y≤6.又有,故y≥4.若y=4,則z=20.若y=5,則z=10.若y=6,則z無整數(shù)解.若x=3,類似可以確定3≤y≤4,y=3或4,z都不能是整數(shù).4.可仿例2解.5.先求出,然后將方程變形為y=5+x-2要使y為整數(shù),5x-1應(yīng)是完全平方數(shù),…,解得≡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由關(guān)于x的二次方程有解的條件△≥0及y為整數(shù)可得0≤y≤5,即y=0,1,2,3,4,5.逐一代入原方程可知,原方程僅有兩組解