初中数学竞赛专题复习第三篇初等数论第20章同余试题新人教版

第22章[]x与{}x22.1.1★求1-的值．解析因为1200712006+,又1200720071=+=<,所以200612007<．故12006=．22.1.2★若n是正整数,求的值．解析因为3321n n n n<+++()3323311n n n n<+++=+,所以1n n<=+,所以n=．22.1.13★数1232008A=⨯⨯⨯⨯的末尾有多少个连续的零?解析A的质因数分解式中,5的最高次方幂为23420082008200820085555⎡⎤⎡⎤⎡⎤⎡⎤+++⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦⎣⎦40080163499=+++=,所以1232008A=⨯⨯⨯⨯的末尾有499个零．评注在()!12n n=⨯⨯⨯中,质数p的最高次幂是()2!mn n np np p p⎡⎤⎡⎤⎡⎤=+++⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦,其中m p n≤,且1m p n+>．22.1.4★★设2221111232007S=++++,求[]S．解析要求[]S,只需证明S介于两个连续的整数之间．所以需要对S进行适当的变形,通过放大、缩小的手段求出S的范围,从而确定[]S的取值．由题设知,1S >．考虑到()2111111k k k k k<=---,k =2,3,4,…,2007,可以得到 11111111122320062007S ⎛⎫⎛⎫⎛⎫<<+-+-++- ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭1222007=-<, 所以[]1S =．评注 上述解题过程中,首先对S 进行了“放缩”,又通过“拆项”的方法使和式中前后两项能够相互抵消一部分,使和式化简,从而得到了S 的范围．在对和式取整时,利用和式本身的性质进行“缩放”的方法非常重要,需要在平时的学习中多积累一 些和式的性质以及变形技巧．22.1.5★★ 计算和式23123223100101101101⨯⨯⨯⎡⎤⎡⎤⎡⎤+++⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦的值．解析 因为（23,101）=1,所以,当1,2,,100n =时,23101n 都不是整数,即23101n ⎧⎫⎨⎬⎩⎭都不为零．又因为()2310123101101n n -+ ()()23101231012323101101101101n n n n --⎡⎤⎧⎫⎡⎤⎧⎫=+++⎨⎬⎨⎬⎢⎥⎢⎥⎣⎦⎩⎭⎣⎦⎩⎭ =23,而()231012302101101n n -⎧⎫⎧⎫<+<⎨⎬⎨⎬⎩⎭⎩⎭,且()2310123101101n n -⎧⎫⎧⎫+⎨⎬⎨⎬⎩⎭⎩⎭是整数,所以 ()23101231101101n n -⎧⎫⎧⎫+=⎨⎬⎨⎬⎩⎭⎩⎭, 则()231012323122101101n n -⎡⎤⎡⎤+=-=⎢⎥⎢⎥⎣⎦⎣⎦． 从而,可以把231101⨯⎡⎤⎢⎥⎣⎦,232101⨯⎡⎤⎢⎥⎣⎦,…,23100101⨯⎡⎤⎢⎥⎣⎦首尾配对,共配成50对,每一对的和为22,所以 23123223100101101101⨯⨯⨯⎡⎤⎡⎤⎡⎤+++⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦2251100=⨯=． 22.1.6★★ 已知01a <<,且满足122918303030a a a ⎡⎤⎡⎤⎡⎤++++++=⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦,求[]10a 的值． 解析 因为122902303030a a a <+<+<<+<,所以130a ⎡⎤+⎢⎥⎣⎦,230a ⎡⎤+⎢⎥⎣⎦,…,2930a ⎡⎤+⎢⎥⎣⎦等于0或者1．由题设知,其中有18个等于1,所以12110303030a a a ⎡⎤⎡⎤⎡⎤+=+==+=⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦,1213291303030a a a ⎡⎤⎡⎤⎡⎤+=+==+=⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦, 所以110130a <+<, 121230a +<≤． 故183019a <≤,于是196103a <≤,所以[]106a =． 22.1.7★★ 求满足{}[]25125x x +=的所有实数x 的和．解析 原方程可化为{}[]12525x x -=,所以[]1250125x -<≤,可得[]100125x <≤,于是[]x =101,102,…,125,从而,满足条件的实数x 为[]{}[][][]1252452525x x x x x x -=+=+=+ 24101525⋅=+,24102525⋅+,…,24125525⋅+, 它们的和为 ()24255101102125283725⨯++++=．22.1.8★★ 已知20032004T <<,如果要求[]{}x x ⨯是正整数,求满足条件所有实数x 的和． 解析 显然,[]2003x =,2003是质数,{}01x <<,设{}2003x p =,由题设,p 是整数,12003p <≤．20032003p x =+,p =1,2,3,…,2002． 和1232002200320022003S ++++=⨯+ 4011007=． 22.1.9★ 解方程[]722x x -=． 解析 原方程可改写为[]722x x =+, 将其代人[][]l x x x <+≤,可得[][][]72l 2x x x +<+≤． 解此不等式组,有 []7522x -<-≤, 即[]3.5 2.5x -<-≤,所以[]3x =-．将[]3x =-代入原方程,得52x =-． 所以,原方程的解是52x =-． 评注 若一次方程中同时出现x 和[]x 的一次项,可以通过以下的步骤进行求解：（1）从方程中解出[]x 或x ,分别代入不等式组[]1x x x -<≤或[][]1x x x <-≤,求解后得到[]x 或x 的范围,从而求得[]x 的“可能取值”（注意不一定是解!）．（2）将这些“可能值”代人原方程进行求解．（3）检验．因为在（1）中将[]x 或x 代人不等式组,实际上是“放大”了x 的范围,所以必须验根！22.1.10★ 解方程：[]13122x x +=-．解析 设[]31x n +=,则n 为整数,且()0311x n +-<≤, ① 由原方程知122x n -=,即1124x n =+． ②3301124n n ++-<≤, 即7322n -<-≤．所以,3n =-或2n =-．代入②,得134x =-,254x =-．22.1.11★★ 解方程：[]33x x -=．解析 由原方程可化为[]33x x =-,代入不等式组[]1x x x -<≤,有[]313x x x x -<-=≤．整理后得到()2213x x <-≤．当0x <时,因为()210x x ->,所以210x -<,即10x -<<,所以()211x x -<,与()221x x <-矛盾． 当0x >时,因为()212x x ->,所以210x ->,即1x >．又因为()213x x -≤,所以2x <．所以12x <<,故[]1x =．代入原方程,得x =．22.1.12★★ 解方程[]2440510x x -+=．解析 这是一个关于x 的二次方程,如果从方程中解出[]x 或x ,并代入不等式组将会使问题复杂化．可 以利用[]x 的性质,通过建立不等关系缩小[]x 的取值范围,从而得到[]x 的可能取值．由原方程知,0x >．因为[][]1x x x <+≤,所以将[]x x =和[]1x x =+分别代入[]244051x x -+中,得到不等式组 [][][]()[]22440510,4140510,x x x x ⎧-+⎪⎨+-+>⎪⎩≤ 即[][][]317,22115,22x x x ⎧⎪⎪⎨⎪><⎪⎩≤≤或 所以[]3522x <≤或[]111722x <≤,[]x =2,6,7,8． 代入原方程得,得x经检验知,x =22.1.13★★ 已知x 、y 、z 满足：[]{}[]{}{}[]0.9,0.2,1.3,x y z x y z x y z ⎧++=-⎪++=-⎨⎪++=⎩①②③对于数a ,[]a 表示不大于a 的最大整数,{}[]a a a =-．求x 、y 、z 的值．解析 首先注意到,对于任意有理数a ,[]a a ≤,所以{}0a ≥．①+②+③得2220.6z y z ++=,即0.3z y z ++=． ④④－①得到{}[] 1.2y z +=,从而{}0.2y =,[]1z =；④－②得到{}[]0.1x y +=,从而{}0.1x =,[]0y =；④－③得到{}[]1x z +=-,因此{}1x =-,[]0z =．故0.9x =-,0.2y =,1z =．22.1.14★★ 解方程[][]999x x x x +=+（其中[]x 表示不超过x 的最大整数）．解析 若x 是整数,则[]x x =,于是非零整数都是原方程的解．若x 不是整数,则[]x x ≠,由题设得[]()[]()990x x x x --=,所以[]99x x =．设[]x n =,则x n a =+,01a <<．代入上式得()99n a n +=．当0n >时,()2991n n n <<+,这样的整数n 不存在．当0n <时,()2199n n n +<<,只有整数10n =-满足,此时0.1a =．于是9.9x =-．综上所述,原方程的解为所有非零整数和－9.9．22.1.15★★ 证明：对于任意实数x ,有[][]122x x x ⎡⎤++=⎢⎥⎣⎦．解析 设{}[x x x =+,其中{}01x <≤,则有[]{}1122x x x +=++,[]{}222x x =+．当{}102x <≤时,{}11122x +<≤,{}102212x <⨯=≤,所以[]12x x ⎡⎤+=⎢⎥⎣⎦,[][]22x x =,于是[][][]1222x x x x ⎡⎤++==⎢⎥⎣⎦． 当{}112x <≤时,{}13122x +<≤,{}12212x <⨯=≤,所以[]{}[]11122x x x x ⎡⎤⎡⎤+=++=+⎢⎥⎢⎥⎣⎦⎣⎦,[][]{}[]22221x x x x =+=+⎡⎤⎣⎦,于是[][][]12122x x x x ⎡⎤++=+=⎢⎥⎣⎦．所以,对于任意实数x ,[][]122x x x ⎡⎤++=⎢⎥⎣⎦恒成立．说明 本题中的等式有更为一般的形式：对任意实数x ,有[][]121n x x x x nx n n n -⎡⎤⎡⎤⎡⎤+++++++=⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦,其中n 为大于l 的一切正整数．这个等式称为埃尔米特（Hermite ）恒等式．22.1.16★★ 设x 、y 为正整数,(),1x y =,求证： ()()()11122y x x y x x y y y ---⎡⎤⎡⎤⎡⎤+++=⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦．解析 设r 为整数,且11r y -≤≤,则有()y r x yxrx rx x y y y y -⎡⎤⎡⎤⎡⎤=-=+-⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦1rx x y ⎡⎤=--⎢⎥⎣⎦, 两边同时叠加,得到()()121x y x y x y y y --⎡⎤⎡⎤⎡⎤+++⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦()()()1211x y x x y x y y y ⎛⎫-⎡⎤⎡⎤⎡⎤=---+++ ⎪⎢⎥⎢⎥⎢⎥ ⎪⎣⎦⎣⎦⎣⎦⎝⎭． 所以()12y x x x y y y ⎛⎫-⎡⎤⎡⎤⎡⎤+++ ⎪⎢⎥⎢⎥⎢⎥ ⎪⎣⎦⎣⎦⎣⎦⎝⎭()()112x y --=．评注 对任意实数x ,有[][][]1,,x x x ⎧--⎪-=⎨-⎪⎩，．当不是整数当是整数（请读者自证）22.1.17★★★ 如果n 是正整数,求证：解析 任意正整数n ,总存在正整数m ,满足()221m n m <+≤,不妨设2n m k =+,其中02k m ≤≤．（1）当01k m -≤≤时,即221m n m m +-≤≤．则m12m =+． ①又因为2211m n m m +++≤≤,所以12mm <+． ②由①、②式,得221m m <<+,所以2m =．另一方面,224242442m n m m +++-≤≤,2m =<21m +,即2m =． 故当01k m -≤≤时,等式成立．（2）当2m k m ≤≤时,2222m m n m k m m +=++≤≤,1m +,1m =+．22m +． ③又,+因为 ()22m m =+, 所以 ()()221m m m m +++++()()()222221441m m m m m m m m >++++++=++．即()2221m >+．21m >+． ④由③、④式,得21m =+． 另一方面,2244242482m m n m m +++++≤≤,21m +22m =+．所以21m =+．故当2m k m ≤≤时,等式亦成立．综上所述,原等式成立．22.1.18★★ 设a 、b 、c 是正实数,求a b b c c a u c a b +++⎡⎤⎡⎤⎡⎤=++⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦的最小值． 解析 对于实数x ,有[]1x x >-,所以a b b c c a u c a b +++⎡⎤⎡⎤⎡⎤=++⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦ 3a b b c c a c a b+++>++- 3a b b c c a b a c b a c ⎛⎫⎛⎫⎛⎫=+++++- ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭22233++-=≥．由于u 是整数,所以4u ≥．当6a =,8b =,9c =时,4u =．故u 的最小值为4．22.1.19★★ 在1,2,…,2005这2005个正整数中,有多少个可以表示成[]x x ⎡⎤⎣⎦的形式,其中x 是正实数．（这里[]a 表示不超过a 的最大整数．）解析 令{}[]x x x =-,则{}[0,1)x ∈,于是[][]{}()[][]{}[]2x x x x x x x x ⎡⎤⎡⎤⎡⎤=+=+⎣⎦⎣⎦⎣⎦,因为{}[][]0x x x <≤,所以{}[][]01x x x ⎡⎤-⎣⎦≤≤,令[]x n =,则[]x x ⎡⎤⎣⎦可以表示数2n ,21n +,…,21n n +-．由于2444319792005+=<,24520252005=>,所以,欲求的数的个数为 444512449902⨯+++==． 22.1.20★★★ 将正整数中所有被4整除以及被4除余1的数全部删去,剩下的数依照从小到大的顺序排成一个数列{}n a ：2,3,6,7,10,11,…．数列{}n a 的前n 项之和记为n S ,其中n =1,2,3,…．求2006S S ⎡=+++⎣的值．（其中[]x 表示不超过x 的最大整数） 解析 易知2142n a n -=-,241n a n =-,1n =,2,…,因此()()()21234212n n n S a a a a a a -=++++++()5132183n =++++- ()258322n n n n +-==+, ()22122441n n n S S a n n n -=-=+--()221n n =-+, 所以()()222221n n S n <<+,()()2221212n n S n --<<, 故[]22n S n =,[]2121n S n -=-,从而[]n S n =,于是 [][][]122006S S S S =+++ 200620071220062⨯=+++= 2013021=．22.1.21★★★★ 在212006⎡⎤⎢⎥⎣⎦,222006⎡⎤⎢⎥⎣⎦,232006⎡⎤⎢⎥⎣⎦,…,220062006⎡⎤⎢⎥⎣⎦中,有多少个不同的整数?（其中,[]x 表示不超过x 的最大整数）解析 设()22006n f n =,则当n =2,3,…,1003时, 有()()()221120062006n n f n f n ---=- 2112006n -=<, 而,()10f =,()210031003501.52006f ==,所以,从0到501的整数都能取到． 当n =1004,1005,…,2006时,有()()()221120062006n n f n f n ---=- 2112006n -=>, 而()()22100311004100420062006f +== 1501.515022006=++>, 所以,210042006⎡⎤⎢⎥⎣⎦,210052006⎡⎤⎢⎥⎣⎦,…,220062006⎡⎤⎢⎥⎣⎦是互不相同的整数． 从而,在212006⎡⎤⎢⎥⎣⎦,222006⎡⎤⎢⎥⎣⎦,232006⎡⎤⎢⎥⎣⎦,…,220062006⎡⎤⎢⎥⎣⎦中,共有50210031505+=个不同的整数．。

初中数学竞赛：数论的方法技巧数论是研究整数性质的一个数学分支，它历史悠久，而且有着强大的生命力。

数论问题叙述简明，“很多数论问题可以从经验中归纳出来，并且仅用三言两语就能向一个行外人解释清楚，但要证明它却远非易事”。

因而有人说：“用以发现天才，在初等数学中再也没有比数论更好的课程了。

任何学生，如能把当今任何一本数论教材中的习题做出，就应当受到鼓励，并劝他将来从事数学方面的工作。

”所以在国内外各级各类的数学竞赛中，数论问题总是占有相当大的比重。

数学竞赛中的数论问题，常常涉及整数的整除性、带余除法、奇数与偶数、质数与合数、约数与倍数、整数的分解与分拆。

主要的结论有：1．带余除法：若a，b是两个整数，b＞0，则存在两个整数q，r，使得a=bq+r （0≤r＜b），且q，r是唯一的。

特别地，如果r=0，那么a=bq。

这时，a被b整除，记作b|a，也称b是a 的约数，a是b的倍数。

2．若a|c，b|c，且a，b互质，则ab|c。

3．唯一分解定理：每一个大于1的自然数n都可以写成质数的连乘积，即其中p1＜p2＜…＜pk为质数，a1，a2，…，ak为自然数，并且这种表示是唯一的。

（1）式称为n的质因数分解或标准分解。

4．约数个数定理：设n的标准分解式为（1），则它的正约数个数为：d（n）=（a1+1）（a2+1）…（ak+1）。

5．整数集的离散性：n与n+1之间不再有其他整数。

因此，不等式x＜y与x≤y-1是等价的。

下面，我们将按解数论题的方法技巧来分类讲解。

一、利用整数的各种表示法对于某些研究整数本身的特性的问题，若能合理地选择整数的表示形式，则常常有助于问题的解决。

这些常用的形式有：1．十进制表示形式：n=an10n+an-110n-1+…+a0；2．带余形式：a=bq+r；4．2的乘方与奇数之积式：n=2m t，其中t为奇数。

例1 红、黄、白和蓝色卡片各1张，每张上写有1个数字，小明将这4张卡片如下图放置，使它们构成1个四位数，并计算这个四位数与它的各位数字之和的10倍的差。

第三章同余例题分析例1：求3406的末二位数。

解：∵（3，100）=1，∴3)100(φ≡1（mod 100）φ(100)=φ(22·52)=40,∴340≡1(mol 100)∴3406=(340)10·36≡(32)2·32≡-19×9≡-171≡29(mod 100)∴末二位数为29。

例2：证明（a+b ）p ≡a p +b p (mod p )证：由费尔马小定理知对一切整数有：a p ≡a （p ），b p ≡b (P )，由同余性质知有：a p +b p ≡a+b (p )又由费尔马小定理有（a+b ）p ≡a+b (p )（a+b ）p ≡a p +b p (p )例3：设素数p >2，则2P -1的质因数一定是2pk +1形。

证：设q 是2p -1的质因数，由于2p -1为奇数，∴q ≠2，∴（2·q ）=1,由条件q|2p -1,即2p ≡1（mod q ），又∵（q ,2）=1，2p ≡1（mod q ）设i 是使得2x ≡1（mod p ）成立最小正整数若1<i <p ，则有i |p 则与p 为素数矛盾∴i=p ,∴p |q -1又∵q -1为偶数，2|q -1,∴2p |q -1,q -1=2pk ,即q =2pk +1例4：证明13|42n +1+3n +2证：∵42n +1+3n +2≡4·16n +9·3n≡3n (4+9)≡13×3n ·≡0(13)∴13|42n +1+3n +2例5：证明5y +3=x 2无解证明：若5y +3=x 2有解，则两边关于模5同余有5y +3≡x 2(mod 5)即3≡x 2(mod 5)而任一个平方数x 2≡0,1,4(mod 5)∴30,1,4(mod 5)∴即得矛盾，即5y +3=x 2无解例6：求50111......被7除的余数。

第21章 不定方程§21.1 二元一次不定方程★求不定方程2x y -=的正整数解．解析 因为312-=，422-=，532-=，…，所以这个方程的正整数解有无数组，它们是2,,x n y n =+⎧⎨=⎩其中n 可以取一切正整数．★求11157x y +=的整数解．解析1 将方程变形得71511y x -=． 因为x 是整数，所以715y -应是11的倍数．由观察得02x =，01y =-是这个方程的一组整数解，所以方程的解为215,111,x t y t =-⎧⎨=-+⎩t 为整数． 解析2 先考察11151x y +=，通过观察易得()()1141531⨯-+⨯=，所以()()114715377⨯-⨯+⨯⨯=，可取028x =-，021y =．从而 2815,2111,x t y t =--⎧⎨=+⎩t 为整数． 评注 如果a 、b 是互质的整数，c 是整数，且方程ax by c +=①有一组整数解0x 、0y ．则此方程的一切整数解可以表示为00,,x x bt y y at =-⎧⎨=+⎩其中0t =，±1，±2，±3，…．★求方程62290x y +=的非负整数解．解析 因为(6，22)=2，所以方程两边同除以2得31145x y +=． ①由观察知，14x =，11y =-是方程3111x y +=②的一组整数解，从而方程①的一组整数解为()00454180,45145,x y =⨯=⎧⎪⎨=⨯-=-⎪⎩ 所以方程①的一切整数解为18011,453.x t y t =-⎧⎨=-+⎩因为要求的原方程的非负整数解，所以必有180110,4530.t t -⎧⎨-+⎩≥③≥④ 由于t 是整数，由③、④得15≤t ≤16，所以只有t =15，t =16两种可能．当t =15时，x =15，0y =；当t =16时，x =4，y = 3．所以原方程的非负整数解是15,0,x y =⎧⎨=⎩4,3.x y =⎧⎨=⎩ ★求方程719213x y +=的所有正整数解．解析 这个方程的系数较大，用观察法去求其特殊解比较困难，碰到这种情况我们可用逐步缩小系数 的方法使系数变小，最后再用观察法求解．用方程719213x y +=①的最小系数7除方程①的各项，并移项得213193530277y y x y --==-+．② 因为x 、y 是整数，故357y u -=也是整数，于是有573y u +=．再用5除此式的两边得 373255u u y u --==-+．③令325u v -= (整数)，由此得 253u v +=．④由观察知1u =-，1v =是方程④的一组解．将1u =-代入③得2y =．2y =代入②得x =25．于 是方程①有一组解025x =，02y =，所以它的一切解为2519,27.x t y t =-⎧⎨=+⎩0,1,2,t =±±由于要求方程的正整数解，所以25190,270.t t ->⎧⎨+>⎩ 解不等式，得t 只能取0，1．因此得原方程的正整数解为25,2,x y =⎧⎨=⎩6,9.x y =⎧⎨=⎩★求方程3710725x y +=的整数解．解析 因为10723733=⨯+，371334=⨯+，33841=⨯+．为用37和107表示1，我们把上述辗转相除过程回代，得1=33-8×4=37-4-8×4=37-9×4=37-9×(37-33)=9×33-8×37=9×(107-2×37)-8×37=9×107-26×37=37×(-26)+107×9,由此可知126x =-，19y =是方程371071x y +=的一组整数解．于是()02526650x =⨯-=-,0259225y =⨯=是方程3710725x y +=的一组整数解．所以原方程的一切整数解为650107,22537,x t y t =--⎧⎨=+⎩t 是整数． ★求方程92451000x y z +-=的整数解．解析 设9243x y t +=，即38x y t +=，于是351000t z -=．原方程可化为38,351000.x y t t z +=⎧⎨-=⎩①②用前面的方法可以求得①的解为38,3,x t u y t u =-⎧⎨=-+⎩u 是整数． ②的解为20005,10003,t v z v =+⎧⎨=+⎩v 是整数． 消去t ，得6000815,200035,10003,x u v y u v z v =-+⎧⎪=-+-⎨⎪=+⎩,u v 是整数．★求方程23723x y z ++=的整数解．解析 设23x y t +=，则23,723.x y t t z +=⎧⎨+=⎩①② 对于①，0x t =-，0y t =是一组特解，从而①的整数解为3,2,x t u y t u =--⎧⎨=+⎩u 是整数． 又02t =，03z =是方程②的一组特解，于是②的整数解为3,27,z v t v =-⎧⎨=+⎩v 是整数． 所以，原方程的整数解为273,272,3.x v u y v u z v =---⎧⎪=++⎨⎪=-⎩u 、v 是整数．★求方程组57952,35736x y z x y z ++=⎧⎨++=⎩的正整数解． 解析 消去z ，得 210z y +=． ①．易知04x =，02y =是它的一组特解，从而①的整数解为4,22,x t y t =-⎧⎨=+⎩t 是整数． 代入原方程组，得所有整数解为4,22,2.x t y t z t =-⎧⎪=+⎨⎪=-⎩t 是整数．由0x >，0y >，0z >得12t -<<，所以t =0，1，故原方程组的正整数解为4,2,2;x y z =⎧⎪=⎨⎪=⎩3,4,1.x y z =⎧⎪=⎨⎪=⎩★求方程351306x y +=的正整数解的组数．解析 因为130651435233y y x y -+==-+，所以0x =437，01y =-是一组特解．于是方程的整数 解为4375,13.x t y t =-⎧⎨=-+⎩t 是整数． 由43750,130.t t ->⎧⎨-+>⎩ 得143735t <<. 所以t =1，2，…，87．故原不定方程有87组正整数解．★★某国硬币有5分和7分两种，问用这两种硬币支付142分货款，有多少种不同的方法? 解析 设需x 枚7分，y 枚5分恰好支付142分，于是75142x y +=．①所以1427222855x x y x --==--． 由于7x ≤142，所以x ≤20，并且由上式知()5|21x -．因为(5，2)=1，所以5|1x -，从而 x =1，6，11，16．①的非负整数解为1,6,11,16,27;20;13; 6.x x x x y y y y ====⎧⎧⎧⎧⎨⎨⎨⎨====⎩⎩⎩⎩所以，共有4种不同的支付方式．评注 当方程的系数较小时，而且是求非负整数解或者是实际问题时，这时候的解的组数往往较少，可以用整除的性质加上枚举，也能较容易地解出方程．★★今有公鸡每只五个钱，母鸡每只三个钱，小鸡每个钱三只，用100个钱买100只鸡，问公 鸡、母鸡、小鸡各买了多少只?解析 设公鸡、母鸡、小鸡各买x 、y 、z 只，由题意列方程组153100,3100.x y z x y z ⎧++=⎪⎨⎪++=⎩①② ①化简得159300x y z ++=.③③-②得148200,x y +=即74100.x y +=解741x y +=得1,2.x y =-⎧⎨=⎩于是74100x y +=的一个特解为00100,200.x y =-⎧⎨=⎩所以74100x y +=的所有整 数解为1004,2007,x t y t =-+⎧⎨=-⎩t 是整数． 由题意知，0x <，y ，100z <，所以，01004100,02007100.t t <-+<⎧⎨<-<⎩解得2550,241428.77t t <<⎧⎪⎨<<⎪⎩ 故425287t <<. 由于t 是整数，故t 只能取26，27，28，而且x 、y 、z 还应满足100x y z ++=．所以即可能有三种情况：4只公鸡，18只母鸡，78只小鸡；或8只公鸡，11只母鸡，81只小鸡；或12只公鸡，4只母鸡，84只小鸡．★★小明玩套圈游戏，套中小鸡一次得9分，套中小猴一次得5分，套中小狗一次得2分．小明共套10次，每次都套中了，每个小玩具都至少被套中一次．小明套lO 次共得61分，问：小鸡至少被套中几次?解析 设套中小鸡x 次，套中小猴y 次，套中小狗z 次，则根据题意得95261,10.x y z x y z ++=⎧⎨++=⎩①② 我们要求这个方程组的正整数解．消去z ：从①中减去②×2得7341x y +=，于是4173x y -=．③ 由③可以看出417x <．从而x 的值只能是1，2，3，4，5．将③写成 21323x y x -=-+， 由于y 是整数，所以2x -必须是3的倍数．从而只有2、5两个值满足这一要求．但2x =时，9y =，1z =-不是正整数．在5x =时，2y =，3z =是本题的解．因此小鸡被套中5次．评注 本题问“小鸡至少被套中几次?”实际上却只有一个解，“至少”两字可以省去．★★今有浓度为5％、8％、9％的甲、乙、丙三种盐水分别为60克、60克、47克，现要配制成浓度为7％的盐水100克，问甲种盐水最多可用多少克?最少可用多少克?解析 设甲、乙、丙盐水分别各取x 克、y 克、z 克，配成浓度为7％的盐水100克，依题意有 100,589700.x y z x y z ++=⎧⎨++=⎩其中060x ≤≤，0≤y ≤60，0≤z ≤47．解方程组可得2004,3100.y x z x =-⎧⎨=-⎩由0200460,0310047.x x -⎧⎨-⎩≤≤≤≤ 得3549x ≤≤．又35x =，60y =，5z =和49x =，4y =，47z =均满足题设，故甲种盐水最少可用35克，最 多可用49克．§21.2 勾股数★★★满足方程222x y z +=的一切基本勾股数x 、y 、z （y 为偶数)，都可表示为以下形式：22x p q =-，2y pq =，22z p q =+，①其中p 、q 为正整数，(p ，q )=1，p q >，p 、q 一奇一偶．解析 设正整数p 、q 满足(p ，q )=1，p q >，p 、q 一奇一偶，则()()2222222x y p q pq +=-+ 42242224p p q q p q =-++()2222p q z =+=． 所以一切形如①的正整数x 、y 、z 都是方程222x y z +=的解．下面证明这样的x 、y 、z 是基本勾股 数．设(),,x y z d =，由于p 、q 一奇一偶，所以22p q -是奇数，由22|d x p q =-，于是d 是奇数．又由22|d p q +，得()()2222|d p q p q ++-，即2|2d p ，同理2|2d q ．因为d 是奇数，所以2|d p ，2|d q ，于是()22|,d p q ．由(),1p q =得()22,1p q =，所以1d =．这就证明了由①确定的x 、y 、z 是一组基本 勾股数．反过来，设x 、y 、z 是一组基本勾股数，且y 是偶数，x 和z 都是奇数，则2z x -和2z x +都是整数． 设,22z x z x d -+⎛⎫= ⎪⎝⎭，则存在正整数a 和b ，使 2z x da -=，2z x db +=，(),1a b =，于是()z d b a =+，()x d b a =-．由于(),1z x =，所以1d =，即,122z x z x -+⎛⎫= ⎪⎝⎭． 由222x y z +=得2222y z x z x +-⎛⎫=⋅ ⎪⎝⎭． 这就可推出上式中右面两个因式都是平方数．设22z x p +=，22z x q -=， 这里0p q >>．(,)1p q =，于是可得2222,2,x p q y pq z p q =-==+．由于z 是奇数，所以p 、q 一奇一偶．这就证明了方程222x y z +=的任意一组解x 、y 、z (y 为偶数) 都可由①表示．评注 如果正整数x 、y 、z 满足方程222x y z +=，那么就称x 、y 、z 是一组勾股数．边长为正整数的直角三角形就称为勾股三角形．在勾股数x 、y 、z 中，如果这三个数的最大公约数是1，那么这样的勾股数就称为基本勾股数．如果 （x ，y ，z ）=1d >，那么设x dx =′，y dy =′，z dz =′，则有（x ′，y ′，z ′）=1，并且由222x y z +=得222222d x d y d z '+'='，两边除以2d ，得222x y z '+'='．所以我们只需研究基本勾股数．在基本勾股数x 、y 、z 中，x 和y 必定一奇一偶．这一点可以用反证法证明：假定x 和y 的奇偶性相同，那么有两种可能的情况：①x 和y 同奇，②x 和y 同偶．如果x 和y 同奇，由于奇数的平方是4的倍数加1，所以22x y +是4的倍数加2，于是2z 是偶数，z 也是偶数，而偶数的平方是4的倍数，这与4的倍数加2矛盾，所以x 和y 不能都是奇数．如果x 和y 都是偶数，那么z 也是偶数，这与x 、y 、z 是基本勾股数矛盾，所以x 和y 中一奇一偶．由此也可推出z 是奇数．★设x 、y 、z 是勾股数，x 是质数，求证：21z -和()21x y ++都是完全平方数． 解析()()222x z y z y z y =-=+-．因为x 是质数，所以2x 只有1、x 、2x 三个正约数．由于0z y z y +>->，所以有2,1.z y x z y ⎧+=⎨-=⎩由此得221z x -=，()21222x y x y ++=++()222121x x x =+-+=+， 所以21z -和2(1)x y ++都是完全平方数．★求证：222n n +、21n +、2221n n ++(n 是正整数)是一组勾股数．解析 因为n 是正整数，2222122n n n n ++>+，222121n n n ++>+．由 ()()2222221n n n +++ ()22222441n n n n =++++ ()()222222221n n n n =++++ ()22221n n =++, 所以222n n +、21n +、2221n n ++是一组勾股数．★若勾股数组中，弦与股的差为1，则勾股数组的形式为21n +、222n n +、2221n n ++，其中n 为正整数．解析 设弦长为c ，股长为1c -，勾为x ．因为（c ，1c -）=1，所以x 、1c -、c 为一组基本勾股数．又c 为奇数，1c -为偶数，则x 为奇数． 设21x n =+，则()()222211n c c ++-=，得2221c n n =++，2122c n n -=+． 所以，勾股数组具有形式21n +、222n n +、2221n n ++．★★求证：勾股三角形的直角边的长能取任何大于2的正整数． 解析 当n 是大于1的奇数时，212n -和212n +都是正整数，并且 222221122n n n ⎛⎫⎛⎫-++= ⎪ ⎪⎝⎭⎝⎭．当n 是大于2的偶数时，214n -和214n +都是正整数，并且222221144n n n ⎛⎫⎛⎫+-=+ ⎪ ⎪⎝⎭⎝⎭．由以上两式可以看出，勾股三角形的一直角边n 可取大于2的任何正整数． ★★求证：在勾股三角形中， (1)必有一条直角边的长是3的倍数； (2)必有一条直角边的长是4的倍数； (3)必有一条边的长是5的倍数．解析 设该勾股三角形的三边的长分别为a 、b 、c （c 是斜边)，则222a b c +=．只要证明a 、b 、c 是基本勾股数时的情况．不失一般性，设b 为偶数，则 22a p q =-，2b pq =，22c p q =+，其中p 、q 满足上述定理中的条件．(1)若p 、q 中至少有一个是3的倍数，则b 是3的倍数；若p 、q 都不是3的倍数，设 31p k =±，31q l =±，则()()22223131a p q k l =-=±-±()22996k l k l =+±±是3的倍数．(2)由于p 、q 一奇一偶，所以2b pq =是4的倍数．(3)若a 、b 都不是5的倍数，则2a 的末位数是1或9；2b 的末位数字是4或6． 1+4=5，1+6=7，9+4=13，9+6=15，由于一个完全平方数的末位数不可能是7和3，所以 222c a b =+的末位数只可能是5．于是c 的末位数是5．评注 由此可推出，勾股三角形的面积必是6的倍数；三边之积必是60的倍数． ★★求基本勾股数组，其中一个数是16． 解析 设勾股数组x 、y 、z ，其中x =16． x =16=2×4×2=2×8×1，若4m =，2n =，有(,m n )-2≠1，从而只有8m =，1n =，(,)1m n =，且m 和n 为一奇一偶．于是22228163y m n =-=-=，22228165z m n =+=+=．从而，只有一组基本勾股数16、63、65．评注 若不要求基本勾股数，则x =16=2×4×2，设4m =，2n =，得 2212y m n =-=，2220z m n =+=．即16、12、20为一组勾股数．又22164322x ==⨯⨯，设232m =，22n =，得 2230y m n =-=，2234z m n =+=．即16、30、34为一组勾股数．★★设p 、m 、n 为一组勾股数，其中p 为奇质数，且n >p ，n >m ．求证：21n -必为完全平方数． 解析 因为p 、m 、n 为一组勾股数，n p >，n m >，则有222n m p =+． ()()222m n p n p n p =-=+-，m n p >-．设()1m n r r p =-<≤，则有()()222222p n m n n r r n r =-=--=-．因为1r p <≤，p 为奇质数，则1r =(否则，若1r p <<，则|r 2p ，矛盾)． 由1r =，得221p n =-，从而21n -是完全平方数．★★直角三角形的三边的长都是正整数，其中有一条直角边的长是35，它的周长的最大值和 最小值分别是多少?解析 设直角三角形的三边长分别是35，b ，c ，则 22235b c +=，即()()1225c b c b +-=．1225的大于35的正约数可作为c b +，其中最大的是1225，最小的是49，所以，直角三角形的周长的 最大值是 35+1225=1260， 最小值是35+49=84．★★设n 为大于2的正整数．证明：存在一个边长都是整数的直角三角形，它的一条直角边长 恰为n ．解析 只需证明不定方程222x n z +=，有正整数解．利用()()2z x z x n -+=，结合z x -与z x +具有相同的奇偶性，故当n 为奇数时，由（z x -，z x +）=（1，2n ），可得不定方程的一组正整数解 （x ，z ）=2211,22n n ⎛⎫-+ ⎪⎝⎭； 而当n 为偶数时，由条件，知n ≥4．利用 （z x -，z x +）=22,2n ⎛⎫⎪⎝⎭，可得不定方程的一组正整数解 （x ，z ）=2244,44n n ⎛⎫-+ ⎪⎝⎭． 综上，可知命题成立。

A卷一、填空题01.a除以5余1，b除以5余4。

如果3a＞b，那么3a−b除以5的余数是__________。

02. 71427和19的乘积被7除，余数是__________。

03. 1+22+33+44+55+66+77+88+99≡__________ (mod3)。

04. 一个数除以3余2，除以4余1，这个数除以12的余数是__________。

05. 今天是星期一，过21995是星期__________。

06. 10100被7除的余数是__________。

07. 1至5 000之间同时被3、5、7除都余2的数有__________个。

08. 1至1 000之间同时被2、3、7除都余1的数有__________个。

09.用199433333个除以7，余数是__________。

10. 1993年的元旦是星期五，那么1996年五月一日是星期__________。

二、解答题11.甲、乙两数都只含有质因数3和5，它们的最大公约数是75。

已知甲数有12个约数，乙数有10个约数，那么甲、乙两数的最小公倍数是多少？12. 试证不小于5的质数的平方与1的差必能被24整除。

B 卷一、填空题 01. 整数100011111个被6除的余数是__________。

02. (1989)1990的末二位数是__________。

03. 在所有的五位数中，各位数字之和等于43，并且能被11整除的数是__________。

04. 777777的末位数是__________。

05.令n 是一个奇数，则n 2除以8的余数是__________。

06. 21000除以13的余数是__________。

07.设a 、b 都是正整数，且a 被7除余数是2，b 被7除余数是5，则a 2＋4b 被7除余数是__________。

08.如果m 是大于1的整数，69、90、125对于m 同余，那么m 的值是__________。

09. 19901990化为7进制数后的个位数字是__________。

数学教师解题能力培训之四数的整除（4）余数和同余教室姓名学号【知识要点】1、例如：37÷5＝7……2，四者之间的数量关系：被除数=除数×商+余数2、同余的概念：两个整数，被同一个大于1的整数m除，所得余数如果相同，那么，这两个整数对于除数m来说是同余的。

例如：14和26这两个数虽然大小不同，但它们分别除以6所得的余数相同，我们把14和26叫做关于模6同余。

3、同余最基本的性质是：几个同余式（模相同）相加、减、乘、乘方仍然同余。

【典型例题】例1、两个整数相除商8，余16；并且被除数、除数、商及余数的和是463.那么被除数是多少？解：因为：被除数=除数×8+16，并且被除数+除数=463―8―16＝439，所以除数=（439－16）÷（8+1）=47，被除数=47×8＋16=392.例2、被3除余2，被5除余3，被7除余4的最小自然数是多少？解：被3除余2的数有2，5，8，11，…其中8又能被5除余3，并且满足条件最小的，而［3，5］=15，所以8+15=23，23+15=38，38+15=53，53满足了被7除余4这个条件，并且最小。

例3、五（3）班同学上体育课，排成3行少1人，排成4行多3人，排成5行少1人，排成6行多5人，问上体育课的同学最少多少名？解：［3,4,5,6］=60, 60－1=59(人).例4、小刚在一次计算除法时，把被除数171错写成117，结果商少了3而余数恰好相同，这题中的除数是几？解：设除数为m,正确的商位q，余数为r，那么错写被除数后，除数仍为m，商为q－3，余数仍为r。

因为：171=m×q+r117= m×（q－3）+r于是171－117=（m×q+r）－（m×q－3 m+r）得m=18.【精英班】例5、有一个三位数，其中个位上的数是百位上的数的3倍，且这个三位数除以5余4，除以11余3.这个三位数是多少？解：这个三位数除以5余4，所以它的个位数字是4或9，因为个位数字是百位数字的3倍，所以个位数字只能是9，百位数字是3.因为这个数除以11余3，所以它的十位数字=3+（9－3）=9，这个三位数是399.【竞赛班】例6、11+22+33+44+55+66+77+88+99除以3的余数是多少？解：由数的整除性质和同余性质可推知：（1）3的倍数的任何次方（0除外）除以3的余数为0，可知33+66+99除以3余0.（2）不是3的倍数的偶次方除以3的余数为0，可知22+44+88除以3余1.（3）11除以3余1，55与25对于3同余，它们除以3余2. 77与17对于3同余，它们除以3余1.所以（1+2+1）÷3=1……1。

余数及同余一、带余除法的定义：一般地，如果a是整数，b是整数（b≠0）,若有a÷b=q…r，也就是a＝b×q＋r,0≤r＜b；我们称上面的除法算式为一个带余除法算式.这里：（1）当时：我们称a可以被b整除，记作b|a，q称为a除以b的商或完全商（2）当时：我们称a不可以被b整除，记作，q称为a除以b的商或不完全商二、同余的概念两个整数被同一个大于1的整数m除，所得的余数相同，就说这两个整数对于除数m来说是同余的.也可以换句话来说这个概念，如果两个整数的差能被大于1的整数m整除，那么这两个整数对于除数m来说是同余的.同余的概念和符号都是德国伟大数学家高斯引进的.一般地，两个整数a和b，除以大于1的正整数m，如果所得的余数相同，就说a、b对于模m同余，记作a≡b（mod m）.由于一个整数被m除的余数只能是0、1、2、3、…、m-1这m个数，所以全体整数可按被m除的余数分类，凡是余数相同的归为一类，全体整数就被划分成了m类，同一类中的任何两数被m除的余数都相等，即同一类中任何两数的差都能被m整除，不同类的任何两数被m除的余数都不相等.三、同余的性质1.如果a≡b（mod m），那么m|（a-b）；如果整数a和b对于模m是同余的，那么a与b的差能被m整除.2.a≡a（mod m），即任何整数都与自身同余.3.若a≡b（mod m），则b≡a（mod m）.4.若a≡b（mod m），b≡c（mod m），则a≡c（mod m）.5.若a≡b（mod m），c≡d（mod m），则a+c≡b+d （mod m），a－c≡b－d （mod m），a×c≡b×d （mod m）.6.若a≡b（mod m），则an≡bn（mod m）。

（其中n为正整数）.例1.用一个两位数除708，余数为43，求这个两位数.[答疑编号5721170101]【答案】95【解答】根据被除数-余数=商×除数，可知，所求两位数一定是707-43=665的大于43的约数，所以所求的两位数是95.例2.数713、1103、830、947被一个数除所得余数相同（余数不为0），求这个除数.[答疑编号5721170102]【答案】39，13或3.【解答】1103－713=390=3×13×2×5，947－830=117=3×13×3，1103－947=156=2×13×3×2，除数为39，13或3.例3.从1、2、…100中最多能选出多少个数，使选出的数中每两个的和都不能被3整除？[答疑编号5721170103]【答案】35【解答】1、2、…100中，除以3余1的数共34个，即1、4、7、10、…、100.除以3余2的数共33个，选出的数中，如果有除以3余1的，就一定不能有除以3余2的；如果有除以3余2的，也就不能有除以3余1的。

第三篇 初等数论第19章 整数的整除性§19．1整除19.1.1★证明：三个连续奇数的平方和加1,能被12整除,但不能被24整除．解析 要证明一个数能被12整除但不能被24整除,只需证明此数等于12乘上一个奇数即可．设三个连续的奇数分别为21n -、21n +、23n +（其中n 是整数）,于是()()()()22222121231121n n n n n -+++++=++．所以()()()22212|212123n n n ⎡⎤-++++⎣⎦．又()2111n n n n ++=++,而n 、1n +是相邻的两个整数,必定一奇一偶,所以()1n n +是偶数,从而21n n ++是奇数,故()()()22224212123n n n ⎡⎤-++++⎣⎦．19．1．2★★若x 、y 为整数,且23x y +,95x y +之一能被17整除,那么另一个也能被17整除．解析 设23u x y =+,95x y =+．若17|u ,从上面两式中消去y ,得 3517v u x -=． ① 所以 17|3v ．因为（17,3）=1,所以17|v 即17|95x y +．若17|v ,同样从①式可知17|5u ．因为（17,5）=1,所以17|u ,即17|23x y +． 19.1.3★★设n 是奇数,求证： 60|6321n n n ---．解析 因为260235=⨯⨯,22、3、5是两两互质的,所以只需证明22、3、5能整除6321n n n ---即可． 由于n 是奇数,有22|62n n -,22|31n +, 所以22|6231n n n ---； 又有3|63n n -,3|21n +, 所以3|6321n n n ---； 又有5|61n -,5|32n n +, 所以5|6321n n n ---．所以60|6321n n n ---．评注 我们通常把整数分成奇数和偶数两类,即被2除余数为0的是偶数,余数为1的是奇数．偶数常用2k 表示,奇数常用21k +表示,其实这就是按模2分类．又如,一个整数a 被3除时,余数只能是0、1、2这三种可能,因此,全体整数可以分为3k 、31k +、32k +这三类形式,这是按模3分类．有时为了解题方便,还常把整数按模4、模5、模6、模8等分类,但这要具体问题具体处理．19．1．4★★设n 为任意奇正整数,证明：15961000270320n n n n +--能被2006整除． 解析 因为200621759=⨯⨯,所以为证结论成立,只需证n 为奇正整数时,15961000270320n n n n +--能被2、17、59整除．显然,表达式能被2整除． 应用公式,n 为奇数时,()()121n n n n n a b a b a a b b ---+=+-++, ()()121n n n n n a b a b a a b b ----=-+++.由于159610005944+=⨯,2703205910+=⨯,所以15961000270320n n n n +--能被59整除. 又159627013261778-==⨯,10003206801740-==⨯,所以15961000270320n n n n +--能被17整除．19.1.5★★若整数a 不被2和3整除,求证：()224|1a -．解析 因为a 既不能被2整除,也不能被3整除,所以,按模2分类与按模3分类都是不合适的．较好的想法是按模6分类,把整数分成6k 、61k +、62k +、63k +、64k +、65k +这六类．由于6k 、62k +、64k +是2的倍数,63k +是3的倍数,所以a 只能具有61k +或65k +的形式,有时候为了方便起见,也常把65k +写成61k -（它们除以6余数均为5）． 故a 具有61k ±的形式,其中k 是整数,所以()()222161136121231a k k k k k -=±-=±=±．由于k 与31k ±为一奇一偶（若k 为奇数,则31k ±为偶数,若k 为偶数,则31k ±为奇数）,所以()2|31k k ±,于是便有()224|1a -．19．1．6★★★求证：31n +（n 为正整数）能被2或22整除,但不能被2的更高次幂整除． 解析 按模2分类．若2n k =为偶数,k 为正整数,则 ()22313131n k n +=+=+．由3k 是奇数,()23k 是奇数的平方,奇数的平方除以8余1,故可设()2381k l =+,于是()3182241n l l +=+=+,41l +是奇数,不含有2的因数,所以31n +能被2整除,但不能被2的更高次幂整除． 若21n k =+为奇数,k 为非负整数,则()()()22131313313811461n k k l l ++=+=⋅+=++=+．由于61l +是奇数,所以此时31n +能被22整除,但不能被2的更高次幂整除． 19.1.7★★设p 是质数,证明：满足22a pb =的正整数a 、b 不存在. 解析 用反证法．假定存在正整数a 、b ,使得 22a pb =.令() , a b d =,1a a d =,1b b d =,则()11 , 1a b =.所以 222211a d pb d =,2211a pb =,所以21|p a ．由于p 是质数,可知,1|p a .令12a pa =,则22221a p pb =,所以2221pa b =．同理可得,1|p b .即1a 、1b 都含有p 这个因子,这与()11 , 1a b =矛盾．19．1．8★★如果p 与2p +都是大于3的质数,那么6是1p +的约数.解析 每一整数可以写成6n 、61n -、61n +、62n -、62n +、63n +中的一种（n 为整数）,其中6n 、62n -、62n +、63n +在1n ≥时都是合数,分别被6、2、2、3整除．因此,质数p 是61n -或61n +的形式. 如果()611p n n =+≥,那么 ()263321p n n +=+=+是3的倍数,而且大于3,所以2p +不是质数．与已知条件矛盾． 因此()611p n n =-≥．这时16p n +=是6的倍数．评注 本题是将整数按照除以6,所得的余数分为6类．质数一定是61n +或61n -的形式．当然,反过来,形如61n -或61n +的数并不都是质数．但可以证明形如61n -的质数有无穷多个,形如61n +的质数也有无穷多个．猜测有无穷多个正整数n ,使61n -与61n +同为质数．这是孪生质数猜测,至今尚未解决． 19.1.9★★已知a 、b 是整数,22a b +能被3整除,求证：a 和b 都能被3整除． 证 用反证法.如果a 、b 不都能被3整除,那么有如下两种情况：（1）a 、b 两数中恰有一个能被3整除,不妨设3|a ,3b ．令3a m =,31b n =±（m 、n 都是整数）,于是()222222996133321a b m n n m n n +=+±+=+±+,不是3的倍数,矛盾．（2）a ,b 两数都不能被3整除.令31a m =±,31b n =±,则()()2222223131961961a b m n m m n n +=++±=±++±+()22333222m n m n =+±±+,不能被3整除,矛盾．由此可知,a 、b 都是3的倍数．19．1．10★★若正整数x 、y 使得2x x y+是素数,求证：x y ≤.解析 设2x p x y=+是素数,则()py x x p =-,所以()|p x x p -,故|p x ,或者|p x p -,故可得|p x ,且p x <.令x kp =,k 是大于1的整数,则 ()1y x k x =-≥．19.1.11★证明：形如abcabc 的六位数一定被7、11、13整除． 解析100171113abcabc abc abc =⨯=⨯⨯⨯．由此可见,abcabc 被7、11、13整除．19．1．12★任给一个正整数N ,把N 的各位数字按相反的顺序写出来,得到一个新的正整数N ',试证明：N N '-被9整除．解析 N 除以9,与N 的数字和除以9,所得余数相同．N '除以9,与N '的数字和除以9,所得余数相同．N 与N '的数字完全相同,只是顺序相反,所以N 与N '的数字和相等．N 除以9与N '除以9,所得的余数相同,所以N N '-被9整除． 19.1.13★19991999199919991999N =连写个.求N 被11除所得的余数．解 显然,N 的奇数位数字和与偶数位数字和的差为()1999999119998⨯+--=⨯.19998⨯除以11的余数与88⨯除以11的余数相同,即余数为9．从而N 除以11,所得的余数为9． 19．1．14★在568后面补上三个数字,组成一个六位数,使它能被3、4、5分别整除．符合这些条件的六位数中,最小的一个是多少？解析 要命名这个六位数尽可能小,而且能被5整除,百位数字和个位数字都应选0．这样,已知的五个数位上数字之和是5+6+8+0+0=19．要使这个六位数能被3整除,十位上可填2、5、8．由能被4整除的数的特征（这个数的末两位数应该能被4整除）可知,应在十位上填2． 这个六位数是568020．19.1.15★★已知四位数abcd 是11的倍数,且有b c a +=,bc 为完全平方数,求此四位数． 解析 在三个已知条件中,b c a +=说明给出b 和c ,a 就随之给定,再由11|abcd ,可定d .而bc 为完全平方数,将b 和c 的取值定在两位平方数的十位和个位数字范围中,只要从这个范围中挑选符合要求的即可．由bc 完全平方数,只可能为16、25、36、49、64、81这六种情况．由b c a +=,此时相应的a 为7、7、9、13、10、9．其中13和10显然不可能是四位数的千位数字．在716d 、725d 、936d 、981d ,这四种可能性中,由11|abcd ,应有()()11|d b a c +-+． ()()11|176d +-+时,d 可为1； ()()11|275d +-+时,这种d 不存在； ()11|396d +-+时,d 可为1； ()11|891d +-+时,d 可为2．故满足条件的四位数有：7161、9361、9812．评注bc 为完全平方数,表示bc 是两位整数,0b ≠,因此,不考虑00、01、04、09这四种情况,否则还应加上1012、4048、9097这三个四位数.19．1．16★★用0,1,2,…,9这十个数字组成能被11整除的最大的十位数是多少？解析 因为0+1+2+…+9=45．这个最大十位数若能被11整除,其奇数位上数字之和与偶数位上的数字之和的差（大减小）为0或11的倍数．由于这十个数字之和是45（奇数）,所以这个差不可能是0、22、44（偶数）．若这个差为33,则只能是396-,但0+1+2+3+4=10,即最小的五个数字之和都超过6,不可能．若这个差为11,()4511228+÷=,452817-=．如果偶数位为9、7、5、3、1,其和为25；奇数位为8、6、4、2、0,其和为20．交换偶数位上的1与奇数位上的4,可得偶数位上的数为9、7、5、4、3,奇数位上的数为8、6、2、1、0．19.1.17★★一个六位数88的倍数,这个数除以88所得的商是多少？ 解析88的倍数,而88811=⨯,8与11互质,所以,这个六位数既是8的倍数,又是11的倍数．由1234A B 能被8整除,可知34B 能被8整除（一个数末三位组成的数能被8整除,这个数就能被8整除）,所以B 是4．由能被11整除的数的特征（一个数奇数位数字之和与偶数位数字之和的差能被11整除,这个数就能被11整除）,可知奇数位数字之和与偶数位数字之和的差()()234144A A ++-++=-能被11整除,则40A -=,即4A =． 124344881413÷=．所以,这个六位数是124344,的商是1413．19．1．18★★如果六位数105整除,那么,它的最后两位数是多少？解析 因为这个六位数能被,而105357=⨯⨯,3、5、7这三个数两两互质,所以,这个六位数能同时被3、5、7整除．根据能被5整除的数的特征,它的个位数可以是0或5．根据能被3整除的数的特征,可知这个六位数有如下七种可能：199320,199350,199380,199305,199335,199365,199395．而能被7整除的数的特征是：这个数的末三位数字所表示的数与末三位以前的数字所表示的数的差（以大减小）能被7整除．经试算：395199196-=,196能被7整除．所以,199395能被105整除,它的最后两位数是95．19.1.19★★形如1993199319931993520n 个,且能被11整除的最小数是几？解析 本题实质上确定n 的最小值．利用被11整除的数的特征：偶数位数字之和与奇位数字之和的差能被11整除．该数的偶数位数字之和为122n +,奇数位数字之和为105n +,两者之差为()12210523n n n +-+=-．要使()11|23n -,不难看出最小的7n =,故所求最小数为71993199319931993520个．19．1．20★★★是否存在100个不同的正整数,使得它们的和与它们的最小公倍数相等？ 解析 存在满足条件的100个数．事实上,对任意正整数()3n ≥,下述n 个数3,23⨯,223⨯,…,223n -⨯,13n -, 它们的最小公倍数为123n -⨯,和为221222132323233323233n n n n ----+⨯+⨯++⨯+=+⨯++⨯+33211113232333323n n n n n -----=+⨯++⨯+==+=⨯．所以,这几个数的和等于它们的最小公倍数．取100n =,可知存在符合要求的10019.1.21★★下面这个41位数20555个 2099个能被7整除,问中间方格代表的数字是几？解析 因为5555555111111=⨯,9999999111111=⨯,11111137111337=⨯⨯⨯⨯,所以555555和999999都能被7整除,那么由18个5和18个9分别组成的18位数,也能被7整除．而原数=185230555000个个1851890999+个个,因此右边的三个加数中,前后两个数都能被1整除,那么只要中间的能被7整除,原数就能被7整除．把拆成两个数的和： 5599BA B +.因为7|55300,7|399,336+=． 评注 记住111111能被7整除很有用． 19．1．22★★一位魔术师让观众写下一个六位数a ,并将a 的各位数字相加得b ,他让观众说出a b -中的5个数字,观众报出1、3、5、7、9,魔术师便说出余下的那个数,问那个数是多少？解析 由于一个数除以9所得的余数与这个数的数字和除以9所得的余数相同,所以a b -是9的倍数．设余下的那个数为x ,则 ()9|13579x +++++, 即()9|7x +,由于09x ≤≤,所以,2x =．19．1．23★★若p 、q 、21p q -、21q p-都是整数,并且1p >,1q >．求pq 的值．解析 若p q =,则 212112p p q p p--==- 不是整数,所以p q ≠．不妨设p q <,于是2121212p q q q q q --<<=≤,而21p q -是整数,故211p q -=,即21q p =-．又214334q p p p p--==- 是整数,所以p 只能为3,从而5q =．所以 3515pq =⨯=．19．1．24★★★试求出两两互质的不同的三个正整数x 、y 、z 使得其中任意两个的和能被第三个数整除．解析 题中有三个未知数,我们设法得到一些方程,然后从中解出这些未知数．不妨设x y z <<,于是y z x +、z x y +、x yz+都是正整数．先考虑最小的一个：12x y z z z z++<=≤,所以1x yz+=,即z x y =+．再考虑z x y +,因为()|y z x +,即()|2y y x +,所以|2y x ,于是2212x y y y <=≤,所以21x y=,即2y x =,从而这三个数为x 、2x 、3x ．又因为这三个数两两互质,所以1x =．所求的三个数为1、2、3．19.1.25★★★求所有的有理数a ,使得421a -≤,并且44127a A a -=为整数.解析 由条件,可知1344a ≤≤.当14时,0A =是整数；下面考虑1344a <≤的情形,此时设pa q =,p 、q 为正整数,且() , 1p q =．则由()34427p q p A q -=为正整数和() , 1p q =可知4|4q q p -,进而|4q q p -,导致|q p ,再结合() , 1p q =,得1q =.于是()3427p p A -=,又114a p =>．故3p ≤,易知仅当3p =时A 为正整数． 综上可知,满足条件的14a =或13．19．1．26★★设正整数x 、y 、r 、t 满足1100x y r t <<<≤≤．求x ry t+的最小值．解析 由条件,可知11111121100100100100100100x r r y y y t y y y ++++=++=≥≥≥. 等号在()() , , , 1 , 10 , 11 , 100x y r t =时取到,因此所求的最小值为21100. 19.1.27★★已知正整数a 、b 、p 、q 、r 、s 满足条件1qr ps -=,p a rq b s<<．证明：b q s +≥．解析 由条件,可知pb aq <,as br <,故 1pb aq +≤, ①1as br +≤．② 将①s ⨯与②q ⨯,然后相加,得 psb s q brq ++≤．结合1rq ps -=,可知b q s +≥.19．1．28★★★将正整数N 接写在任意一个正整数的右面（例如,将2接写在35的右面得352）,如果得到的新数都能被N 整除,那么N 称为“魔术数”.问：在小于130的正整数中有多少个魔术数？ 解析设P 为任意一个正整数,将魔术数()130N N <接后得PN ,下面对N 为一位数、两位数、三位数分别进行讨论．（1）当N 为一位数时,10PN P N =+,依题意|N PN ,则|10N P .由于需对任意数P 成立,故|10N ．所以N =1,2,5．（2）当N 为两位数时,100PN P N =+,依题意|N PN ,则|100N P ,故|100N ．所以N =10,20,25,50．（3）当N 为三位数时,1000PN P N =+,依题意|N PN ,则|1000N P ,故|1000N ．所以100N =,125．综上所述,魔术数的个数为9个．评注 （1）我们可以证明：k 位魔术数一定是10k 的约数．事实上,设N 是k 位魔术数,将N 接写在正整数P 的右面得：10k PN P N =⨯+,由魔术数定义可知：|N PN ,因而10k P ⨯也能被N 整除,所以|10k N ．这样我们有： 一位魔术数为1,2,5；二位魔术数为10,20,25,50；三位魔术数为100,125,200,250,500；三位或三位以上的魔术数,每种个数均为5．（2）这里将问题分成几种情况去讨论,对每一种情况都增加了一个前提条件,从而降低了问题的难度,使问题较容易解决．19.1.29★★一个正整数如果从左读到右与从右到左读所得的结果相同,则称这个数为回文数．例如：1,343及2002都是回文数,但2005则不是．请问能否找到2005个不同的回文数122005 , , , n n n ,使得122005110 , 110 , , 110n n n +++也都是回文数？解析 取回文数10999901n =,则11011000011n +=也是回文数．因为n 中9的数目可以任选,可取110901n =,2109901n =,…,20052005910999901n =个,因此我们可以找到2005个回文数满足题目所要求的条件．19．1．30★★将2008个同学排成一行,并从左向右编为1至2008号．再从左向右从1到11地报数,报到11的同学原地不动,其余同学出列．留下的同学再次从左向右从1到11地报数,报到11的同学留下,其余同学出列．留下的同学第三次从左向右1到11报数,报到11的同学留下,其余同学出列．问最后留下的同学有多少人？他们的编号是几号？ 解 由题意,第一次报数后留下的同学,他们的编号必为11的倍数． 第二次报数后留下的同学,他们的编号必为211121=的倍数． 第三次报数后留下的同学,他们的编号必为3111331=的倍数．因此,最后留下的同学编号为1331的倍数,我们知道从1~2008中,1331的倍数只有一个,即1331号．所以,最后留下一位同学,编号为1331．19.1.31★★★甲、乙两人进行了下面的游戏．两人先约定一个整数N ,然后由甲开始,轮流把0、1、2、3、4、5、6、7、8、9这十个数字之一填入下面的任一方格中．□□□□□□每一方格只填一个数字,六个方格都填上数字（数字可重复）后,就形成一个六位数,如果这个六位数能被N 整除,就算乙胜；如果这六位数不能被N 整除,就算甲胜．设N 小于15,那么当N 取哪几个数时,乙才能取胜？ 解析 N 取偶数,甲可以在最右边方格里填一个奇数（六位数的个位）,就使六位数不能被N 整除,乙不能获胜．5N =,甲可以在六位数的个位填一个不是0或5的数,甲就获胜． 上面已经列出了乙不能获胜的N 的取值情况． 如果1N =,很明显乙必获胜．如果3N =或9,那么乙在填最后一个数时,总是能把六个数字之和凑成3的整数倍或9的整数倍．因此乙必获胜．当7N =,11,13时是本题最困难的情况．注意到100171113=⨯⨯,乙就有一种必胜的办法．我们从左往右数这六个格子,把第一与第四,第二与第五,第三与第六配对,甲在一对格子的一格上填某一个数字后,乙就在这一对格子的另一格子上填同样的数字,这就保证所填成的六位数能被1001整除,这个六位数就能被7、11或13整除,故乙就能获胜． 综合起来,使乙获胜的N 是1、3、7、9、11、13． 19．1．32★★小明家电话号码原为六位数,第一次升位是在首位号码和第二位号码之间加上数字8,成为一个七位数的电话号码；第二次升位是在首位号码前加上数字2,成为一个八位数的电话号码．小明发现,他家两次升位后的电话号码的八位数,恰是原来电话号码的六位数的81倍,问小明家原来的电话号码是多少？解析 设原来电话号码的六位数为abcdef ,则经过两次升位后电话号码的八位数为28a bcdef ．根据题意,有 8128abcdef a bcdef ⨯=．记43210101010x b c d e f =⨯+⨯+⨯+⨯+, 于是5568110812081010a x a x ⨯⨯+=⨯+⨯+,解得()125020871x a =⨯-． 因为5010x <≤,所以()5012502087110a ⨯-<≤,故1282087171a <≤. 因为a 为整数,所以2a =．于是 ()125020871282500x =⨯-⨯=． 所以,小明家原来的电话号码为282500．19.1.33★★若a 是不超过1000的正整数,且247a a ++是最简分数,则a 的取值有多少个？ 解析 因为2723444a a a a +=-+++,所以()4 , 231a +=,由于23是质数,所以4a +不是23的倍数即可,在5,6,…,1004中,23的倍数有43个,所以满足条件的正整数a 有100043957-=个．19．1．34★★★★在各位数码各不相同的10位数中,是11111的倍数的数共有多少个．解析 设这个10位数为abcdefghij ,因为这10位数的各位数码各不相同,所以a 、b 、c 、d 、e 、f 、g 、h 、i 、j 是0 , 1 , 2 , , 9的一个排列,故 45a b c d e f g h i j +++++++++=． 所以9|abcdefghij ．因为11111|abcdefghij 且（11111,9）=1,所以99999|abcdefghij ,即599999|10abcde fghij ⨯+．又99999|99999abcde ⋅,所以99999|abcde fghij +．因为0999992abcde fghij <+<⨯,所以99999abcde fghij +=, 所以9a f b g c h d i e j +=+=+=+=+=．而99081726354=+=+=+=+=+,所以,符合题意的数共有 54543212432123456⨯⨯⨯⨯⨯-⨯⨯⨯⨯=（个）．19.1.35★★★从1,2,…,9这九个数字中,每次取出3个不同的数字组成三位数,求其中能被3整除的三位数的和．解析 对于固定的三个不同的非零数字a 、b 、c ,任意排列,可得6个不同的三位数,它们的和为()2111a b c ++⨯．因为()3|3|abc a b c ⇔++,所以有以下两种情况：（1）a 、b 、c 除以3所得的余数相同,即a 、b 、c 取成{}1 , 4 , 7,或{}2 , 5 , 8,或{}3 , 6 , 9,这样得到的()332118⨯⨯⨯=个的三位数的总和为 ()()()21472583691119990++++++++⨯=⎡⎤⎣⎦．（2）a 、b 、c 除以3所得的余数各不相同,不妨设a 取自{}1 , 4 , 7,b 取自{}2 , 5 , 8,c 取自{}3 , 6 , 9,这种三位数共有()333321162⨯⨯⨯⨯⨯=个．对于固定的a ,易知b 、c 有339⨯=种取法,因而这162个三位数的和为 ()91239211189910++++⨯⨯=．综合（1）、（2）,可知,所求的满足条件的三位数总和为 9990+89910=99900．19．1．36★★★证明一个正整数,当且仅当它不是2的整数幂时,可以表示成若干个（至少两个）连续正整数的和．解析 当且仅当,有两方面的意思．一方面,当一个正整数不是2的整数幂时,它可以表示成几个连续正整数的和．另一方面,如果一个正整数可以表示成几个连续正整数的和,那么它一定不是2的整数幂．设n 不是2的整数幂．这时n 可以写成 2k n h =⋅,h 是大于1的奇数. ①我们可将n 写成h 个连续正整数的和．中间一个是2k ,它的两侧是21k -与21k +,再向外分别写22k -与22k +,…,直至122k h --与122k h -+（h 是奇数,所以12h -是整数）,即()()132********k k k k kh h n --⎛⎫⎛⎫=-+-++-+++++ ⎪ ⎪⎝⎭⎝⎭312222k k h h --⎛⎫⎛⎫+++ ⎪ ⎪⎝⎭⎝⎭．另一方面,设n 是()1h h >个连续正整数1k +,2k +,…,k h +的和,则 ()()()()()11122122k k h hn k k k h k h h +++=++++++==++,其中h 与21k h ++奇偶性不同,即至少有一个是大于1的奇数．所以这时n 不是2的整数幂． 评注 2的整数幂没有大于1的奇约数．所以一个整数,如果有大于1的奇约数就一定不是2的整数幂．19.1.37★★★玛丽发现将某个三位数自乘后,所得乘积的末三位数与原三位数相同．请问：满足上述性质的所有不同的三位数的和是多少？ 解析设三位数为abc ,则21000abc k abc =+,即()33125abc abc k -=⋅,而(), 11abc abc -=,所以,32|abc ,且35|1abc -；或者32|1abc -,且35|abc ．（1）若32|abc ,且35|1abc -,则1125abc -=,375,625,875,只有376abc =使得32|abc ,故此时376abc =满足题意．（2）若32|1abc -,且35|abc ,则125abc =,375,625,875,只有625abc =使得32|1abc -,故此时625abc =满足题意．所以,所求的和为376+625=1001．19．1．38★★★我们知道,4998约分后是12,但按下面的方法,居然也得14941:29882==.试求出所有分子和分母都是十进制两位正整数,分子的个位数与分母的十位数相同,且具有上述“奇怪”性质的真分数．解析 设真分数abbc具有上述性质,则ab bc <,且1ab a c bc =<,于是1010a b ab c c+=+,故()910ac b a c =-．若()9|10a c -,则()9|a c -,但是9a c -<,所以0a c -=,矛盾．故9不整除10a c -,所以3|b ．（1）若3b =,则310ac a c =-,于是10333131a a c a a -==+++,所以()()31|3a a +-,而331a a -<+,故只能是3a =,从而3c =,矛盾．（2）若6b =,则()3210ac a c =-,于是2021263232a a c a a -==+++,当6a >时,021232a a <-<+,此时c 不是整数；当6a =时,6c =,矛盾；当6a <时,应有12232a a -+≥,所以2a ≤,而当1a =时,4c =,此时,满足题意的真分数为1664,当2a =时,5c =,此时,满足题意的真分数为2665．（3）若9b =,则10ac a c =-,于是10101011a c a a ==-++,所以,()1|10a +,故a =1,4,9． 当1a =时,5c =,此时,满足题意的真分数为1995；当4a =时,8c =,此时,满足题意的真分数为4998；当9a =时,9c =,矛盾．综上所述,满足题意的真分数为：1664,2665,1995,4998.19.1.39★★★在1,2,3,…,1995这1995个数中,找出所有满足下面条件的数a ：()1995a +能整除1995a ⨯．解析 19951995aa+是一个整数．这个式子的分子、分母都有a ,所以应当先进行变形,使得分子不含有a ．()19951995199519951995199519951995199519951995a a a a a+-⨯⨯==-+++. 根据已知,19951995a a +是整数,所以199519951995a⨯+是整数．因为22221995199535719⨯=⨯⨯⨯,所以它的因数1995a +可以通过检验的方法定出．注意11995a ≤≤,所以199519953990a <+≤．如果1995a +不被19整除,那么它的值只能是以下两种： 223573675⨯⨯=,223572205⨯⨯=．如果1995a +被19整除,而不被219整除,那么它的值只能是以下两种： 237192793⨯⨯=,257193325⨯⨯=．如果1995a +被219整除,那么它的值只能是以下两种： 27192527⨯=,223193249⨯=．于是满足条件的a 有6个,即从以上1995a +的6个值分别减去1995,得出的6个值： 1680,210,798,1330,532,1254．评注 形如ac a b +的式子,可以化成cbc a b-+.使得只有分母含a ,而分子不含a ．这种方法有点像假分数化成带分数． 19．1．40★★★在1,2,…,2010这2010个正整数中,最多可以取出多少个数,使得所取出的数中任意三个数之和都能被33整除？解析 首先,如下61个数：11,11+33,11233+⨯,…,()1160331991+⨯=满足题设条件． 另一方面,设12n a a a <<<是从1,2,…,2010中取出的满足题设条件的数,对于这n 个数中的任意4个数 , , , i j k m a a a a ,因为()33|i k m a a a ++,()33|j k m a a a ++,所以()33|j i a a -． 因此,所取的数中任意两个之差都是33的倍数．设133i i a a d =+, 2 , 3 , , i n =.由()12333|a a a ++,得()12333|33333a d d ++． 所以133|3a ,111|a ,即111a ≥．1201011613333n n a a d --=<≤,故60n d ≤,所以,61n ≤． 综上所述,n 的最大值为61．19.1.41★★★圆周上放有N 枚棋子,如图所示．B 点的棋子紧邻A 点的棋子．小洪首先拿走B 点的棋子,然后顺时针每隔1枚拿走2枚棋子．这样连续转了10周．9次越过A ,当将要第10次越过A 取走其他棋子时,小洪发现圆周上余下20多枚棋子．若N 是14的倍数,请帮助小洪精确计算一下圆周上还有多少枚棋子．解析 如果在A 、B 之间再添一枚棋子,并在第一次取棋子时将它取走,那么每一次都是在相邻3枚棋子中取走2枚,所以每取一周,剩下的棋子是上一次剩下的13．B设最后剩下a 枚棋子．根据分析所说 1013N a +=, ① 即1031N a =⨯-．因为N 是14的倍数,所以N 是偶数,a 是奇数．又N 是7的倍数,而10539==（7的倍数）+52=（7的倍数）+4,所以41a -是7的倍数．因为a 是20与29之间的奇数,将a =21,23,25,27,29代入41a -,逐一检验,只有a =23时,4191713a -==⨯是7的倍数． 所以圆周上还有23枚棋子．评注 在A 、B 之间添上一枚棋子,使得取棋子有明显的规律,从而得到①．这是一种很巧妙的想法．在计算103除以7的余数时,可以将其中7的倍数抛弃,直至出现小于7的4．这是常用的方法． 19．1．42★★★★求证：对1i =,2,3,均有无穷多个正整数n ,使得n ,2n +,28n +中恰有i 个可表示为三个正整数的立方和．解析 三个整数的立方和被9除的余数不能为4或5,这是因为整数可写为3k 或31k ±（k是整数）,而()33393k k =⨯,()()332319331k k k k ±=±+±．对1i =,令()33312n m =--（m 是正整数）,则n 、28n +被9除的余数分别为4、5,故均不能表示为三个整数的立方和,而()()()3332313131n m m m +=-+-+-．对2i =,令()331222n m =-+（m 是正整数）被9除的余数为5,故不能表示为三个整数的立方和,而()3323126n m +=-++, ()333283155n m +=-++．对3i =,令3216n m =（m 是正整数）满足条件：()()()333345m m m m =++, ()3332611n m +=++, ()33328613n m +=++．§19．2奇数与偶数19.2.1★设有101个自然数,记为12101 , , , a a a ．已知12310123101a a a a s ++++=是偶数,求证：13599101a a a a a +++++是偶数．解析 ()1359910123451001012244100100a a a a a s a a a a a a +++++=-++++++是偶数．19．2．2★设121998 , , , x x x 都是1+或者1-．求证：12319982319980x x x x ++++≠．解析()12319981351997231998351997x x x x x x x x ++++=++++()241998241998x x x ++++.因为131997 , 3 , , 1997x x x 这999个数均为奇数,所以它们的和为奇数,于是12199821998x x x +++=奇数0≠．19.2.3★★设()12 , ,, 4n x x x n >为1+或为1-,并且123423451230n x x x x x x x x x x x x +++=．求证：n 是4的倍数．解析 设12342345123 , , , n x x x x x x x x x x x x 中1+有k 个,于是1-也有k 个,故2n k =为偶数．把12342345123 , ,, n x x x x x x x x x x x x 这n 个数相乘,得()()4121kn x x x =-,所以()11k-=．故k 是偶数,从而n 是4的倍数．19．2．4★某次数学竞赛,共有40道选择题,规定答对一题得5分,不答得1分,答错倒扣1分．证明：不论有多少人参赛,全体学生的得分总和一定是偶数． 解析 我们证明每一个学生的得分都是偶数．设某个学生答对了a 道题,答错了b 道题,那么还有40a b --道题没有答．于是此人的得分是 ()5404240a a b b a b +---=-+,这是一个偶数．所以,不论有多少人参赛,全体学生的得分总和一定是偶数．19.2.5★把前50个正整数分成两组,使第一组内各数之和等于第二组内各数之和,能办到吗？说明你的理由． 解析 不能办到．如果能办到,那么所有数加起来应该是第一组内各数之和的2倍,是偶数,但这50个数的总和为5051125025512⨯+++==⨯是个奇数,矛盾！19．2．6★设1,2,3,…,9的任一排列为129 , , , a a a ,求证：()()()129129a a a ---是一个偶数．解析 因为()()()()()()123912912391290a a a a a a a -+-+-++-=+++-+++=是偶数,所以,()()()1291 , 2 ,, 9a a a ---这9个数中必定有一个是偶数,从而可知()()()129129a a a ---是偶数．解析2 由于1,2,…,9中只有4个偶数,所以1a 、3a 、5a 、7a 、9a 中至少有一个是奇数,于是11a -、33a -、55a -、77a -、99a -中至少有一个是偶数,从而()()()129129a a a ---是偶数.19.2.7★有n 个数12 , ,, n x x x ,它们中的每一个数或者为1,或者为1-,如果1223110n n n x x x x x x x x -++++=, 求证：n 是4的倍数．解析 我们先证明2n k =为偶数,再证k 也是偶数．由于12 , , , n x x x 的绝对值都是1,所以12231 , , , n x x x x x x 的绝对值也都是1,即它们或者是为1+,或者为1-,设其中有k 个1-,由于总和为0,故1+也有k 个,从而2n k =． 下面我们来考虑()()()12231n x x x x x x ⋅⋅⋅.一方面,有()()()()122311kn x x x x x x ⋅⋅⋅=-,另一方面,有()()()()212231121n n x x x x x x x x x ⋅⋅⋅==．所以()11k-=,故k 是偶数,从而n 是4的倍数.19．2．8★★设a 、b 是正整数,且满足关系式()()1111111111123456789a b +-=．求证：a b -是4的倍数．解析 由已知条件可得11111a +与11111b -均为奇数,所以a 、b 均为偶数,又由已知条件()111112468a b ab -=+,因为ab 是4的倍数,24684617=⨯也是4的倍数,所以()11111a b ⨯-是4的倍数,故a b -是4的倍数．19.2.9★★9999和99!（注：99!123499=⨯⨯⨯⨯⨯,读作99的阶乘）能否表示成为99个连续的奇数的和？解析 （1）9999能．因为()()()()999898989898999998999699299992=-+-++-+++++()()989899969998+++．即9999能表示为99个连续奇数的和． （2）99!不能．因为99!12399=⨯⨯⨯⨯是一个偶数,而99个连续奇数之和仍为奇数,所以99!不能表示为99个连续奇数之和．评注 如果答案是肯定的,我们常常将满足题意的例子举出来或造出来,这称为构造法． 如果答案是否定的,常常采用反证法,找出其中的矛盾． 19．2．10★★代数式rvz rey suz swx tuy tvx --++-．① 中,r 、s 、t 、u 、v 、w 、x 、y 、z 可以分别取1+或1-． （1）证明：代数式的值都是偶数； （2）求这个代数式所能取到的最大值．解析 （1）①式中共有6项,每项的值都是奇数（1+或1-）,所以它们的代数和为偶数． （2）显然,①式的值6≤,但它取不到6这个值,事实上,在rvz 、rwy -、suz -、swx 、tuy 、tvx -这六项中,至少有一项是1-,要证明这一点,将上面这6项相乘,积是()21rstuvwxyz -=-．所以六项中,至少有一项是1-,这样,六项和至多是514-=．在u 、x 、y 为1-,其他字母为1时,①式的值是4,所以①的最大值为4． 评注 本例中的代数式实际上是行列式 r s t u v w x y z的展开式,行列式是一个很有用的工具,在今后的学习中还会遇到．19.2.11★★★在n n ⨯（n 为奇数）方格表里的每一个方格中任意填上一个1+或1-,在每一列的下面写上该列所有数的乘积,在每行的右面写上该行所有数的乘积,求证：这个乘积的和不等于0．解析 设每列下面的数为12 , , , n a a a ,每行右面的数为12 , , , n b b b ,依题意得1i a =+或1-,1i b =+或\1-, 1 , 2 , , i n =,若这2n 个乘积的和为0,即12120n n a a a b b b +++++++=,则这2n 个数中1+的个数与1-的个数一样多,都是n 个,但事实上,因为 1212n n a a a b b b =,()21212121n n n a a a bb b a a a ==．所以这2n 个数中1-的个数为偶数,即n 为偶数,矛盾．19．2．12★★在黑板上写上1,2,…,2000,2001,只要黑板上还有两个或两个以上的数,就擦去其中任意两个数a 和b ,并写上a b -,问最后黑板上剩下的数是奇数还是偶数？ 解析因为a b -与a b -有相同的奇偶性,而a b -又与a b +有相同的奇偶性,因此a b-与a b +具有相同的奇偶性． 所以黑板上剩下的数的奇偶性与20012002122001*********⨯+++==⨯的奇偶性相同,是奇数．19.2.13★★把图中的圆圈任意涂上红色或蓝色,问有没有可能使得在同一条直线上的红圈数都是奇数？请说明理由．解析 如果每条线上红圈都是奇数个,那么5条线上的红圈数相加仍是奇数．但另一方面,由于每个圈都在两条直线上,因而相加时每个红圈都被计算了两次,从而相加的总和应该是偶数．两方面的结果是矛盾的．因此,不可能使同一条线上的红圈数都是奇数．19．2．14★★围棋盘上有1919⨯个交叉点,在交叉点上已经放满了黑子与白子,并且黑子与白子相间地放,即黑子（白子）的上、下、左、右都放着白子（黑子）．问能否把这些黑子全部移到原来白子的位置上,而白子也全移到原来的黑子的位置上？ 解析 不能．因为1919361⨯=是奇数,所以,必有奇数个白子,偶数个黑子；或者奇数个黑子,偶数个白子．即黑、白子数必然一奇一偶．奇数不可能等于偶数,所以无法使黑子与白子的位置对调． 19.2.15★★参加会议的人,有不少互相握过手．握手的次数是奇数的那部分人,人数是奇数还是偶数？为什么？解析 由于每握一次手,握手的两个人,每一个都握了一次手．因此每握一次手,两个人握手次数的和就是2次．所以,全部与会的人握手的总次数必定是偶数．我们把参加会议的人分成两类,甲类握手次数是偶数,乙类握手次数是奇数,甲类人握手的总次数显然是偶数．注意甲类人握手的总次数加上乙类人握手的总次数等于全部与会的人握手的总次数,所以乙类人握手的总次数也应当是偶数．由于乙类人每人握手的次数都是奇数,而偶数个奇数相加,和才能为偶数,因此,乙类人必为偶数个,即握手次数是奇数的那部分人,人数是偶数．19．2．16★★设标有A 、B 、C 、D 、E 、F 、G 记号的七盏灯顺次排成一行,每盏灯安装一个开关．现在A 、C 、E 、G 四盏灯开着,其余三盏灯是关的．小刚从灯A 开始,顺次拉动开关.即从A 到G ,再从A 到G ,这样拉动了1999次开关后,哪几盏灯是开的？解析 一盏灯的开关被拉动奇数次后,改变状态,即开的变成关的,关的变成开的．一盏灯的开关被拉动偶数次后,不改变状态,即开的仍为开的,关的仍为关的．因此本题的关键是计算各盏灯被拉次数的奇偶性．由 199972854=⨯+,可知,A 、B 、C 、D 四盏灯的开关各被拉动了286次,而E 、F 、G 三盏灯的开关各被拉动了285次．所以,A 、B 、C 、D 四灯不改变状态,E 、F 、G 三灯改变状态．由于开始时A 、C 、E 、G 四灯是开着的．因此,最后A 、C 、F 三灯是开着的．19.2.17★★桌上放着七只杯子,杯口全朝上,每次翻转四个杯子．问能否经过若干次这样的翻动,使全部的杯子口都朝下？ 解析 不可能．我们将口向上的杯子记为0,口向下的杯子记为1．开始时,由于七个杯子全朝上,所以这七个数的和为0,是个偶数．一个杯子每翻动一次,所记的数由0变为1或由1变为0,改变了奇偶性．每一次翻转四个杯子,因此这七个数的和的奇偶性改变了四次,从而和的奇偶性仍与原来相同．所以,不论翻动多少次,这七个数的和与原来一样,仍为偶数．当杯子全部朝下时,这七个数的和为7,是奇数．因此,不论经过多少次翻转,都不可能使所有的杯子口都朝下．19．2．18★★★设1i x =1,1i =,2,…,2012．令 123420112012S x x x x x x =+++.。

同余问题的奥数题引言奥数是指数学奥林匹克竞赛（IMO）或全国中学生数学奥林匹克竞赛（NOI）等数学竞赛的简称。

同余问题是奥数中常见的一个重要概念，也是一种常用的解题方法。

本文将介绍同余问题在奥数中的应用，并通过一个具体的奥数题来详细讲解同余问题的解题过程。

同余问题定义在数论中，给定两个整数a和b，如果它们除以正整数m所得的余数相同，则称a与b对模m同余，记作a ≡ b (mod m)。

其中≡表示“同余”，mod表示“对模”。

这里m被称为模数。

性质1.如果a ≡ b (mod m)，则对于任意整数k，有a + km ≡ b (mod m)。

2.如果a ≡ b (mod m)，c ≡ d (mod m)，则a + c ≡ b + d (mod m)，ac≡ bd (mod m)。

3.如果a ≡ b (mod m)，则an ≡ bn (mod m)，其中n为任意正整数。

常见应用同余问题在密码学、编码理论、计算机科学等领域有着广泛应用。

在奥数中，同余问题常用于解决数字特征和数列性质相关的问题。

下面通过一个具体的奥数题来说明同余问题的应用。

奥数题示例题目描述一串由0-9组成的数字序列，长度为n。

现在要从这个序列中选择若干个数字，使得它们组成的整数能够被7整除。

问有多少种不同的选择方案。

解题思路我们可以使用动态规划的方法来解决这个问题。

首先定义一个二维数组dp，其中dp[i][j]表示在前i个数字中选取若干个数字，它们组成的整数对7取模等于j的方案数。

那么我们可以得到状态转移方程：dp[i][j] = dp[i-1][j] + dp[i-1][(10*j+digit)%7]其中digit表示第i个数字。

代码实现def solve(sequence):n = len(sequence)dp = [[0] * 7 for _ in range(n+1)]dp[0][0] = 1for i in range(1, n+1):digit = int(sequence[i-1])for j in range(7):dp[i][j] = dp[i-1][j]dp[i][(10*j+digit)%7] += dp[i-1][j]return dp[n][0]sequence = input("请输入一串由0-9组成的数字序列：")print("方案数：", solve(sequence))解题过程假设输入的数字序列为12345。

第20章同余20. 1.1* (DiiE明：任意平方数除以4,余数为0或1； (2)证明：任意平方数除以8,余数为0、1或4. 解析(1)因为奇数'=(2R + +4« + ]三l(nκxi4),偶数2 = (2k)2 =4k2≡0(nκxi4),KmOd 4)√ι为奇数;所以, 正整数斥0(mod4)/为偶数•B(2)奇数可以表示为2jt + l,从而奇数 2=4/+4k + l = 4k(k+ 1) + 1.因为两个连续整数R、斤+ 1中必有一个是偶数，所以4⅛(⅛ + l)是8的倍数，从而奇数2=8∕ +l≡l(mod8).又，偶数j(2R)2=4疋(R为整数)・若E =偶数= 2/,贝ιJ4⅛2=16r =0(mod8).若R =奇数=2/ + 1,贝IJ4k2 =4(2/ + 1)2 =16(r +∕) +4≡4(mod8)・0( mod 8),所以，平方数≡J(mod8),4( mod 8).评注事实上，我们也可以这样来证：因为对任意整数“，有心0, ±1, 2(mod4),所以，a≡0, 1(ITlOd4):又a≡Q9±L ±2, ±3, 4(mod8),所以，/三 0, L 4(mod8).20. 1. 2*求证：一个十进制数被9除所得的余数，等于它的各位数字被9除所得的余数.解析设这个十进制数心“如…吆也.因10≡l(nκxl9),故对任何整数心有IO4≡f =l(mod9)・因此= a n×∖0n +% XlOE +…+ q xlθ + q三 5I-I +・・• + "] +⅜(mod 9)・即A被9除所得的余数等于它的各位数字之和被9除所得的余数・评注⑴特别地，一个数能被9整除的充要条件是它的各位数字之和能被9整除.(2)算术中的“弃九验算法”就是依据本题的结论.20. 1. 3*★求证：(1) 8∣(55,w+17);(2)8∣(32Λ+7);(3)17∣(19,°OO-1).解析⑴因55≡-l(mod8),所以55lw9≡-l(mod8),55,999+ 17≡-l + 17 = 16≡0(mod8),于是8∣(55,999 +17).⑵因为32=9≡l(mod8), 32π≡l(mod8),所以32Λ+7≡l +7≡0(mod8),即8∣(32π+7).⑶因为I9≡2(modl7), I94≡24=16≡-l(modl7),所以19HXM) =(194广≡(-l)25°≡l(modl7)，于是17∣(19KMX,-1).20. 1. 4* ★对任意的正整数”，证明：4 = 2903"-803"-464”+261"能被1897整除. 解析1897 = 7x271, 7与271互质.因为2903 ≡ 5(InOd7), 803 ≡ 5(nιod7),464 ≡2(mod7), 261 ≡2(mod7),所以 A = 2903" -803" -464” + 261〃三5” 一5” 一T + T = 0(mod7),故 7 A 又因为2903 三 193(mod271),803≡261(nιod271)f464≡193(mod271),所以A = 2903” 一803“ 一464” + 26 I n≡ 193π -26Γ -193π+ 26Γ =0(mod271),故 271 A因(7, 271)=b所以1897整除A・20. 1. 5★证明：55552~ + 22225555能被 7 整除. 解析因为5555 ≡4(mod7) ∙ 45≡64≡l(mod7), 所以5555迪≡42222≡42.42≡≡16≡2(mod7)・因为2222≡3(mod7), 32≡2(mod7), 32≡l(mod7),所以2222W 35555353 5550. . Z AX925≡32 32-3(36)三223≡5(mod7)・于是 55552222 + 22225555≡(2+5)(mod7)≡0(mod7), 即 7155552222 + 22225555・20. 1. 6★★求最大的正整数“，使得3,024 -l能被2"整除.解析因为3,,β4 -1 =(3512 +1)(3256+,)(3,28 + 1)-..(3 + 1)(3-1),①而对于整数E,有32* +l≡(-lf +I = 2(mod4),所以，①式右边的11个括号中，(3+1)是4的倍数，其他的10个都是2的倍数，但不是4的倍数.故 n的最大值为12.20. 1. 7★求使2" -1为7的倍数的所有正整数“.解析因为23≡8≡l(mod7),所以对“按模3进行分类讨论.⑴若n = 3R,贝IJ2M-I=(23)C -1 = 8A -I≡1' -1 = 0(mod7):⑵若n = 3k + ∖9贝IJ2π-l = 2(25y-l = 28'-l≡2Λk一1 = l(mod7);⑶若n = 3k + 29贝IJ2π-l = 22.(23y-l = 4-8'-l4 V一l = 3(mod7)・所以，当且仅当3 〃时，2”-1为7的倍数・20. 1. 8★设“是正整数，求证：7不整除(4n + l).解析因为4l≡4(mod7)t 42≡2(nιod7)t 43≡l(mod7).所以当n = 3k时，4Π+1=(43)；+1 = 1 + 1 = 2(nιod7):当n = 3k+↑时，4” +1 = (4〉4 +1 = 4 +1 = 5 (mod 7):当刃= 3k+2时，4” +1 = (4' j ・ 16 +1 = 16 +1 = 3 (mod 7)・所以，对一切正整数“，7不整除4"+l.20. 1. 9★今天是星期日，过3πx>天是星期几？解析33=27≡-l(mod7),所以3wo =(33广-3≡(-1)Λ3∙3 = -3≡4(mod7).因此，过天是星期四.20. 1. 10★★求(25733 +46)26被50除所得的余数.解析257 ≡ 7(mod50), 257n≡ 7n(mod50).又7'=49三-l(mod50),所以74≡l(ιnod50).753=(74)s.7≡7(mod50).即 257n≡7(mod50).从而 257幻+46≡7 + 46≡ 3(mod50).(257^+46)26≡326(mo<i50).由于 35 = 243 = -7(mod50) . 31° ≡49 ≡-1(mod50),所以320≡l(mod50).于是3" = 320・ 3'・3 ≡ (-7)・ 3 = -21 ≡ 29(mod 50).故(25733 +4626)除以50所得的余数为29.20. 1. 11★⑴求33除2hm的余数；⑵求8除72Π+I-1的余数・解析⑴先找与±l(mod33)同余的数.因为 2'=32 三—1 (mod 33),所以 2,0≡l(mod33).2,w8 = (2,°),w-25 -23≡-8≡25(mod33).故所求的余数为25.(2)因为7 ≡-l(mod8),所以72"+,≡(-l)2n+,=-l(mod8),72-÷>-i≡-2≡6(mod8).即余数为6.20. 1. 12★求15+25+35+∙..+995+100S除以 4 所得的余数.解析因为(2/?)5≡0(rYlOd4), (2π + l)5≡2n + l(mod4),所以15+25+35+∙∙∙+99S+1005≡l + 3 + 5 +∙.. + 99 = 502≡0(mod4).20. 1. 13*形如F rl=2-+∖, H=Q t 1, 2, •••的数称为费马数.证明：当"22时，你的末位数字是7.解析当n^2时，2"是4的倍数，故令2" =4/.于是=24/+1 = 16, +1 = 6,+I≡7(modl0).即你的末位数字是7.评注费马数的头几个是F n=3,F∣= 5, F z=∖l,人=257, F i = 65537 ,它们都是素数.费马便猜测：对所有的正整数“，化都是素数.然而，这一猜测是错误的.首先推翻这个猜测的是欧拉，他证明了下一个费马数尺是合数.有兴趣的读者可以自己去证明.20. 1. 14★★已知n = 19 191 919∙∙∙1 919 ,求"被9除后所得商的个位数字是多少？19I9TI9I9解析因为"19 191 9弓…1 9191919个19191919×(l + 9÷l+9)≡1919×20≡2×2≡4(mod9).所以91”-4.又π-4的个位数字是5,故"被9除后所得商的个位数字是5・20. 1. 15★★求2w9的末两位数.解析因为2,° + l≡0(mod25), 2,0≡-l(mod25),(2,0),00≡(-l),0° = l(mod25),2HxM)-I ≡0(mod25).所以2,000 -l的末两位数字只可能是00、25、50、75,即2w°0的末两位数字只可能是01、26、51、76.又2≡0是4的倍数，故2∣∞0的末两位数字只可能是76.又2洌=2HJ∞-2,所以29W的末两位数字只可能是38、88,而4 88, 4、38,故2*w的末两位数字是88.20. 1. 16★★求所有的正整数",使得3, +3n + 7是一个立方数•解析假设存在正整数加、“，使得3√+3H +7=,√,则∕√≡l(mod3),于是∕√≡l(mod3).设 m = 3jt+ l,则3k(3k2+3k + ∖) = n2+n + 2,易^n2+n + 2不能被3整除，故不存在正整数"，使得3n2+3”+ 7是一个立方数.20. 1. 17★★有一列数排成一行，其中第一个数是3,第二个数是7,从第三个数开始，每个数恰好是前两个数的和，那么，第1997个数被3除，余数是多少？解析该数列是：3,7, 10, 17, 27, 44, 71, 115,186, 301, 487, 788,…除以3的余数分别是：0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1,…余数刚好是按"0, 1, 1, 2, 0, 2, 2, 1" 八个一循环.又1997≡ 5 (InOd 8),因此所求余数为0.20. 1. 18*★★求7亍的末位数字和7?』的末两位数字，英中斤是大于1的正整数.&个7解析我们知道，求一个数的末位数字就是求这个数除以10的余数，求一个数的末两位数字就是求这个数除以100的余数.为此先设法求出7 ≡ Kmod 10)中的/ ,然后求岀T =at + h(a,〃是整数)中的b.这样，问题归结为求7°被10除所得的余数.因为I2≡-l(modlO), 7Λ≡ 3(mod 10) ♦74≡l(modl0), 74m≡l(modlO),川是正整数.而7 三 3(mod4), 76≡ 36≡ (-1)6≡ l(mod4)・所以，T≡ 3(mod4)・可设f = 4m + 3.于是7? ≡74w+3≡73≡3(modl0).所以，7,的末位数字是3.考虑7,的末两位数字・这时，由72≡49(modl00), 7'三43(mod 100), 7」三1(mod 100),得74π≡l(modlOO).而 77∙'7 = 72r+,,其中t是整数且f >0.于是 77∙∙^7≡ 72,+1≡ 32,+,≡(-l)2"' ≡ 3(mod4).个7 Jt-I 个7可设7"'=4" + 3,那么个777∙7=74π+3≡73≡43(modl00).—个7所以，所求的末两位数字是43.20. 1. 19★★求n = l×3×5×∙∙∙×1997×1999 的末三位数字・解析这个积显然是5X25=125的倍数，设n=5×25×l×3×7×∙∙∙×23×27×∙∙∙×1999=125w ・由于1000=8X125,所以，我们只需求出加除以8所得的余数，进而便可求得“除以IOOO的余数.m= (1 × 3×7)×(9×11×13×15)× (17×19×21×23) × (27×29×31)×(33×35×37×39)×∙∙∙× (1985×1987×1989X1991)× (1993 × 1995×1997 X 1999)在上述乘枳中，除第一和第四个括号外，每个括号中都是四个数的乘积，这个积是(% + l)(8k + 3)(8R+5)(8k+7)≡1×3×5×7三 1 (mod8).而1x3x7 ≡5(mod8),27×29×31 ≡l(mod8)・于是zn≡5×l≡5(nκκi8)・所以，125m = 125×(8Λ + 5)≡ 125×5 = 625(modl000),即 n 的末三位数字是 625∙20. 1. 20*★ ★★如果R是大于1的整数，"是x2-kx + ∖= 0的根.对于大于10的任意正整数“，的个位数字总是7,求是的个位数字.解析首先，我们证明R的个位数字不可能是偶数•其次，根据冰+c浮与7对模10同余，从中确左E的个位数字.因为α是A∙2-ΛΛ +1= O的根，所以这方程的另一个根是丄・于是U1 Z÷ — = K ・a如果k的个位数字是偶数，那么的个位数字仍是偶数.a- +a-22 =(k2-2y f-2的个位数字也是偶数.对于/1 >10. 的个位数字也是偶数，与题设矛盾.R的末位数字不能是偶数.(1)如果R的个位数字是1或9,那么a2+cΓ2≡-l(modl0),由此得0于+*” ≡-!(modIO), n^∖.(2)如果R的个位数字是3或7,那么Cr +cΓ2≡7(modl0),由此得a1^≡7(modl0), H≥1.(3)如果k的个位数字是5,那么a2+cΓ2≡ 3(mod 10), a2+α'y≡ 7(modlθ).所以/ +π^2≡ 7( mod 10), “M2 ・综上所述，R的个位数字是3或5或7.20. 1. 21⅛⅛2005年12月15日，美国中密苏里州大学的数学家CUrtiS COOPer和SteVen BOOne教授发现了第43个麦森质数2'OIM0-I ,求这个质数的末两位数.解析因为2,0= 1024≡-l(mod25),所以23(M(>2457 =S O y(Mo T = (_])**Mo T≡-128≡-3≡22(mod25),所以，23w°2457的末两位数只能是22、47、72、97.又2≡^7≡0(mod4),所以，2“Uo如的末两位数只能是72.从而，23tMoII57-l的末两位数是71.20. 1. 22*★★求最小的正整数“，使得存在正整数“，满足2001155"+心32” .解析因为2001=3×23×29,所以，要使2OO1I55"+"∙32",只要使3l55rτ+α∙32J 23155n + U• 32”，29155”+"∙32".易知55w÷67-32w≡l÷o(-l)π(mθd3),55“ + a - 32” ≡9ιr+α∙9n≡(α + l). 9n (mod 23),55” + a - 32” ≡ (一3)” + α 丁 (InOd 29)・(1)若川是奇数，则<∕≡l(mod3),"三一l(mod23), t∕≡l(mod29),而(3, 29)=b 故u≡ 1(mod87)■令Λ=87⅛1+1=23⅛2-1,则87⅛+2≡0(mod23),所以-5⅛1+2≡0(nιod23)>即-45^+18≡0(mod23)t所以⅛1≡-18(mod23),则$能取的最小正整数是5.所以"是奇数时，α的最小正整数解是87x5 + 1=436.(2)若"是偶数，贝比三—l(mod3), <∕≡-I(mod23), 6/≡-1( mod 29),由于(3, 23)=1, (3. 29)=1,(23, 29)=1,所以^≡-l(mod3×23×29).故当“是偶数时，“的最小正整数解是3×23×29-l等于 2000 ・综上所述，满足条件的最小正整数。

第三章同余§ 1同余的概念及其基本性质定义1设meZ\称之为模。

若用加去除两个整数“与b所得的余数相同，则称"上对模加【可余，记作：a = b (mod /n)；若所得的余数不同，则称w,〃对模加不同余，记作："圭b(mod〃2)。

例如，8 = 1 (mod 7),:所有偶数“三0 (mod 2),所有奇数“ =1 (mod 2)。

同余是整数之间的一种关系，它具有下列性质：R a = a (mod m)；(反身性)2、若"三b (mod加)，贝肪三a (mod m)；(对称性)3、若"三b (mod m), b = c (mod m),贝h 三 c (mod 加);(传递性) 故同余关系是等价关系。

定理1整数对模加同余的充分必要条件是RP a = b + mt,r eZo证明设"=+ b = mq2 + r v 0 < r2 < m,贝l] a = b (mod m) O 打=r2 O a — b = m(q{一⑴)O I (" 一b)°性质1(1)若％三S (mod m)> a2 = b2 (mod m)> 则a x + a2 +b2 (mod /n)；(2)若"+ h = c (mod 〃?)，贝ij a = c-b (mod m)o性质2 若=/?, (mod /??), a2 =b2 (mod m),则"]5 "心(mod m)：特别地，若a = b (mod m),则畑三kb (mod加)。

定理2若比…亞三〃叶・％(mod/),兀三片(mod皿)，j = 1,2,…人则艺比…致坊‘…場三另3时灼)吓…yj (mod/)；特别地,若％三化(mod加),i = OJ2・・・，n，则心* +"心]北1 + - - +u()=b n x n +/>n_|x71'1 + …+ "o (mod 加)。

第20章 同 余20.1.1★(1)证明：任意平方数除以4，余数为0或1；(2)证明：任意平方数除以8，余数为0、1或4．解析 (1)因为奇数()222214411(mod 4)k k k =+=++≡， 偶数()222240(mod4)k k ==≡， 因此，正整数21(mod 4),;0(mod 4),.n n n ⎧≡⎨⎩奇偶为数为数 (2)奇数能够表示为21k +，从而奇数()22441411k k k k =++=++．因为两个持续整数k 、1k +中必有一个是偶数，因此()41k k +是8的倍数，从而奇数()2811mod8i =+≡．又，偶数()22224k k ==(k 为整数)． 若k =偶数2t =，那么()224160mod 8k t ==．若k =奇数21t =+，那么()()22244211644(mod8)k t t t =+=++≡． 因此，平方数()()()0mod8,1mod8,4mod8.⎧⎪≡⎨⎪⎩评注 事实上，咱们也能够如此来证：因为对任意整数a ，有0a ≡，±1，2(mod4)，因此，0a ≡，1(mod4)；又a ≡0，±1，±2，±3，4(mod8)，因此，2a ≡0，1，()4mod8．20.1.2★求证：一个十进制数被9除所得的余数，等于它的列位数字被9除所得的余数．解析 设那个十进制数1210n n A a a a a a -=．因10≡1(mod9)，故对任何整数k ≥1，有()1011mod9k k ≡=．因此1210n n A a a a a a -=1110101010n n n n a a a a --=⨯+⨯++⨯+ ()110mod9n n a a a a -≡++++．即A 被9除所得的余数等于它的列位数字之和被9除所得的余数．评注 (1)专门地，一个数能被9整除的充要条件是它的列位数字之和能被9整除．(2)算术中的“弃九 验算法”确实是依据此题的结论． 20.1.3★★求证：(1)()199985517+；(2)()2837n +；(3)()100017191-．解析 (1)因()551mod8≡-，因此()1999551mod8≡-，()19995517117160mod8+≡-+=≡，于是19998(5517)+．(2)因为2391(mod8)=≡，231(mod8)n ≡，因此()237170mod8n +≡+≡，即()2837n +．(3)因为()192mod17≡，()44192161mod17≡=≡-，因此()()()25025010004191911mod17=≡-≡，于是()100017191-．20.1.4★★对任意的正整数n ，证明：2903803464261n n n n A =--+能被1897整除．解析 18977271=⨯，7与271互质．因为()29035mod7≡，()8035mod7≡，()4642mod7≡，()2612mod7≡，因此()290380346426155220mod7n n n n n n n n A =--+≡--+=，故7|A又因为()2903193mod271≡，()803261mod271≡，因此2903803464261n n n n A =--+()1932611932610mod271n n n n ≡--+=，故271|A因(7，271)=1，因此1897整除A ．20.1.5★证明：2222555555552222+能被7整除．解析 因为()55554mod7≡，()34641mod7≡≡，因此 ()22222222222205555444162mod 7≡≡⋅≡≡．因为 ()22223mod7≡，()232mod7≡，()231mod7≡，因此55555555555502222333≡≡⋅()9252263333223≡⋅⋅⋅≡⋅⋅()5mod7≡．于是()()()222255555555222225mod 70mod 7+≡+≡，即 222255557|55552222+．20.1.6★★求最大的正整数n ，使得102431-能被2n 整除．解析 因为()()()()()1024512256112831313313131+-=+++-，①而关于整数k ≥1，有 ()()2231112mod4kk +≡-+=，因此，①式右边的11个括号中，(3+1)是4的倍数，其他的10个都是2的倍数，但不是4的倍数．故n 的最大值为12．20.1.7★求使21n -为7的倍数的所有正整数n ．解析 因为()3281mod 7≡≡，因此对n 按模3进行分类讨论．(1)假设3n k =，那么()()3212181110mod7k n k k -=-=-≡-=； (2)假设31n k =+，那么()321221281kn k -=⋅-=⋅- ()2111mod 7k ≡⋅-=;(3)假设32n k =+，那么()2321221481kn k -=⋅-=⋅-因此，当且仅当3|n 时，21n -为7的倍数．20.1.8★设n 是正整数，求证：7不整除()41n +．解析 因为()144mod 7≡，()242mod 7≡，()341mod 7≡．因此当3n k =时，()()34141112mod7kn +=+=+=； 当31n k =+时，()()341441415mod7kn +=⋅+=+=； 当32n k =+时，()()34141611613mod7kn +=⋅+=+=． 因此，对一切正整数n ，7不整除41n +．20.1.9★今天是礼拜日，过1003天是礼拜几?解析 ()33271mod 7=≡-，因此()()()333310033331334mod7=⋅≡-⋅=-≡． 因此，过1003天是礼拜四．20.1.10★★求3326(25746)+被50除所得的余数．解析 ()2577mod50≡，()33332577mod50≡．又()27491mod50=≡-，因此()471mod 50≡．()()83347777mod50=⋅≡． 即()332577mod50≡．从而()33257467463mod50+≡+≡．()332626(25746)3mod50+≡．由于()532437mod50==-．()103491mod50≡≡-，因此()2031mod50≡．于是()()262053333732129mod50=⋅⋅≡-⋅=-≡．故3326(25746)+除以50所得的余数为29．20.1.11★(1)求33除19982的余数；(2)求8除2171n +-的余数．解析 (1)先找与()1mod33±同余的数．因为()52321mod33=≡-，因此()1021mod33≡．()()199199810532222825mod33=⋅⋅≡-≡．故所求的余数为25．(2)因为()71mod8≡-，因此()()2121711mod8n n ++≡-=-，()217126mod8n +-≡-≡．即余数为6．20.1.12★求5555512399100+++++除以4所得的余数． 解析 因为()()520mod4n ≡，()()52121mod 4n n +≡+，因此5555512399100+++++ ()213599500mod4≡++++=≡．20.1.13★形如221k n F =+，n =0，1，2，…的数称为费马数．证明：当n ≥2时，n F 的末位数字是7．解析 当n ≥2时，2n 是4的倍数，故令24n t =．于是212k n F +=()421161617mod10t t t =+=+=+≡．即n F 的末位数字是7．评注 费马数的头几个是03F =，15F =，217F =，3257F =，465537F =，它们都是素数．费马便猜想：对所有的正整数n ，n F 都是素数．但是，这一猜想是错误的．第一推翻那个猜想的是欧拉，他证明了下一个费马数5F 是合数．有爱好的读者能够自己去证明．20.1.14★★已知1919191919 191 919 1 919n =个，求n 被9除后所得商的个位数字是多少?解析 因为1919191919 191 919 1 919n =个()19191919≡⨯+++()191920224mod9≡⨯≡⨯≡．因此9|4n -．又4n -的个位数字是5，故n 被9除后所得商的个位数字是5．20.1.15★★求9992的末两位数．解析 因为()10210mod 25+≡，()1021mod 25≡-，()()()10010010211mod25≡-=，()1000210mod 25-≡．因此100021-的末两位数字只可能是00、2五、50、75，即10002的末两位数字只可能是0一、2六、5l 、76． 又10002是4的倍数，故10002的末两位数字只可能是76．又9991000222=÷，因此9992的末两位数字只可能是3八、88，而4|88，4|38，故9992的末两位数字是 88．20.1.16★★求所有的正整数n ，使得2337n n ++是一个立方数．解析 假设存在正整数m 、n ，使得23337n n m ++=，那么()31mod3m ≡，于是()31mod3m ≡．设31m k =+，那么223(331)2k k k n n ++=++，易知22n n ++不能被3整除，故不存在正整数n ，使得2337n n ++是一个立方数．20.1.17★★有一列数排成一行，其中第一个数是3，第二个数是7，从第三个数开始，每一个数恰好是前 两个数的和，那么，第1997个数被3除，余数是多少?解析 该数列是：3，7，10，17，27，44，71，115，186，301，487，788，…除以3的余数别离是：0，1，1，2，0，2，2，1，0，1，1，2，0，2，2，1，…余数恰好是按“0，1，1，2，0，2，2，1”八个一循环． 又1997≡5(mod 8)，因此所求余数为0．20.1.18★★★求777的末位数字和7777k 个的末两位数字，其中k 是大于1的正整数．解析 咱们明白，求一个数的末位数字确实是求那个数除以10的余数，求一个数的末两位数字确实是求那个数除以100的余数．为此，先设法求出71(mod10)t ≡中的t ，然后求出77at b =+(a ，b 是整数)中的b ．如此，问题归结为求67被10除所得的余数．因为()()2371mod1073mod10≡-≡，，()()4471mod1071mod10m ≡≡，，m 是正整数．而()()()66673mod 47311mod 4≡≡≡-≡，． 因此，()773mod 4≡．可设7743m =+．于是()774337773mod10m +≡≡≡．因此，777的末位数字是3．考虑777的末两位数字．这时，由()2749mod100≡，()3743mod100≡，()471mod100≡，得()471mod100n ≡．而77211777t k +-=个，其中t 是整数且t ≥0．于是()()217721211777313mod 4t t t k +++-≡≡≡-≡个． 可设7717743k n -=+个，那么 ()774331777743mod100n k +-=≡≡个．因此，所求的末两位数字是43．20.1.19★★求n =1×3×5×…×1997×1999的末三位数字．解析 那个积显然是5×25=125的倍数，设n =5×25×1×3×7×…×23×27×…×1999=125m ．由于1000=8×125，因此，咱们只需求出m 除以8所得的余数，进而即可求得n 除以1000的余数． m =(1× 3×7)×(9×11×13×15)×(17×19×21×23)×(27×29×31)×(33×35×37×39)×…×(1985×1987×1989×1991)×(1993×1995×1997×1999)在上述乘积中，除第一和第四个括号外，每一个括号中都是四个数的乘积，那个积是()()()()81838587k k k k ++++1≡×3×5×71≡()mod8．而 ()1375mod8⨯⨯≡，()2729311mod8⨯⨯≡．于是 ()515mod8m ≡⨯≡．因此，()()125125851255625mod1000m k =⨯+≡⨯=，即n 的末三位数字是625．20.1.20★★★★若是k 是大于1的整数，a 是210x kx -+=的根．关于大于10的任意正整数n ，22n n a a -+的个位数字老是7，求是的个位数字．解析 第一，咱们证明k 的个位数字不可能是偶数．第二，依照22n n a a -+与7对模10同余，从中确信k 的个位数字．因为a 是210x kx -+=的根，因此这方程的另一个根是1a．于是 1a k a+=． 若是k 的个位数字是偶数，那么 2222122a a a k a -⎛⎫+=+-=- ⎪⎝⎭ 的个位数字仍是偶数．()22222222a a k -+=-- 的个位数字也是偶数．关于10n >，22n na a -+的个位数字也是偶数，与题设矛盾．k 的末位数字不能是偶数．(1)若是k 的个位数字是1或9，那么()221mod10a a -+≡-，由此得()221mod101n n a a n -+≡-，≥． (2)若是k 的个位数字是3或7，那么()227mod10a a -+≡，由此得()227mod10n na a -+≡，1n ≥．(3)若是k 的个位数字是5，那么()223mod10a a -+≡，()22227mod10a a -+≡． 因此()227mod10n n a a -+≡，2n ≥．综上所述，k 的个位数字是3或5或7．20.1.21★★2005年12月15日，美国中密苏里州大学的数学家Curtis Cooper 和Steven Boone 教授发 现了第43个麦森质数3040245721-，求那个质数的末两位数．解析 因为()10210241mod 25=≡-，因此()()3040545304024530402457107722212≡⋅≡-⋅()128322mod 25≡-≡-≡，因此，304024572的末两位数只能是2二、47、7二、97．又304024572≡0(mod4)，因此，304024572的末两位数只能是72．从而，3040245721-的末两位数是71． 20.1.22★★★求最小的正整数a ，使得存在正整数n ，知足2001|5532n n a +⋅．解析 因为2001=3×23×29，因此，要使2001|5532n n a +⋅，只要使3|5532n n a +⋅，23|5532n n a +⋅，29|5532n n a +⋅．易知()()553211mod3nn n a a +⋅≡+-， ()()55329919mod 23n n n n n a a a +⋅≡+⋅≡+⋅，()()553233mod 29nn n n a a +⋅≡-+⋅．(1)假设n 是奇数，那么()1mod3a ≡，()1mod 23a ≡-，()1mod 29a ≡，而(3，29)=1，故()1mod87a ≡ ．令12871231a k k =+=-，那么18720(mod23)k +≡，因此()1520mod 23k -+≡，即()145180mod 23k -+≡，因此()118mod23k ≡-，那么1k 能取的最小正整数是5．因此n 是奇数时，a 的最小正整数解是 8751436⨯+=．(2)假设n 是偶数，那么()1mod3a ≡-， ()1mod 23a ≡-，()1mod 29a ≡-，由于(3，23)=1，(3，29)=1，(23，29)=1，因此1a ≡-(mod3×23×29)．故当n 是偶数时，a 的最小正整数解是323291⨯⨯-等于2000． 综上所述，知足条件的最小正整数a 为436．20.1.23★★证明：对任意正整数n ，87n +不可能是三个整数的平方和． 解析 假设存在整数a 、b 、c ，使得22287n a b c +=++．由于对任意整数x ，2x ≡0，1，4(mod8)，于是222a b c ++≡0，1，2，3，4，5，6(mod8)．而()877mod8n +≡，矛盾！20.1.24★证明不定方程22257x y -=无整数解．解析 因为22257x y =+，显然，y 是奇数．(1)假设x 为偶数，那么()220mod8x ≡．又()21mod8y ≡．因此()2574mod8y +≡，矛盾，故x 不能为偶数．(2)假设x 为奇数，那么()222mod4x ≡．但()2570mod 4y +≡，矛盾，故x 不能为奇数．由(1)，(2)可知：原方程无整数解．20.1.25★证明：不定方程2286a b c +-=没有整数解．解析 若是n ≡0，1，2，3(mod4)，那么2n ≡0，1，4(mod 8)．因此22a b +≡0，1，2，4，5(mod8)．但与()226mod8a b +≡矛盾． 从而原不定方程无整数解．20.1.26★证明：不定方程4425x y z ++=没有整数解．解析 以5为模，若是0x ≡，±1，±2(mod5)，那么2x ≡0，1，4(mod5)，4x ≡0，1，1(mod5)．即对任一整数x ，4x ≡0，1(mod5)．一样，对任一整数y ，4y ≡0，1(mod5)．因此442x y ++≡2，3，4(mod5)．从而原不定方程无整数解．20.1.27★★★求最小的正整数n ，使得存在整数1x ，2x ，…，n x ，知足444121599n x x x +++=．解析 对任意整数a ，可知()20mod4a ≡或()21mod8a ≡，由此可得 40a ≡或()1mod16．利用那个结论，可知，假设n <15，设()44412mod16n x x x m +++=，那么 m ≤n <15，而 1599≡()15mod16，矛盾，因此n ≥15．另外，当n =15时，要求()444121mod16n x x x ≡≡≡≡，即1x ，2x ，…，n x 都为奇数，这为咱们找到适合的数指明了方向．事实上。

数论题练习〔一〕1.求满足2 p2+ p+8 = m2—2m的所有素数p和正整数m2,对于i =2, 3,…,k,正整数n除以i所得的余数为i — 1.假设n的最小值n0满足2000 <n0 <3000,那么正整数k的最小值为3.满足方程x2+y2 =2〔x + y〕+xy的所有正整数解有〔〕.〔A〕一组〔B〕二组〔C〕三组〔D〕四组4.正整数n分别除以2,3,4,5,6,7,8,9,10得到的余数依次为1,2,3,4,5,6,7,8,9 ,那么n的最小值为.泉州现代中学初中数学竞赛材料练习〔cjw〕第1页共7页2 入25. n是一个三位数,b是一个一位数,且刍,a +b都是整数,求a + b的最大值与最小值 b ab 16.a1,a2,%,a4, a5是满足条件a1+a?+a3+为+%=9的五个不同的整数,假设b是关于x的方程(x — a1 X x—a2/x—a 3X x— a 4X x— a 5 = 2021的整数根,那么b的值为.7.试求出所有这样的正整数a使得关于x的二次方程ax2+2(2a-1)x + 4(a —3)= 0至少有一个整数根.8.是否存在质数p, q,使得关于x的一元二次方程px2-qx+p = 0有有理数根?泉州现代中学初中数学竞赛材料练习( cjw) 第2页共7页9,m n均为正整数,且m>n,2006m2+m=2 007n2+n.问m-n是否为完全平方数？并证实你的结论.10.k为常数,关于x的一元二次方程(k2-2k)x 2+(4-6k)x+8=0的解都是整数.求k的值.11.n为自然数,9n2-10n+2 009能表示为两个连续自然数之积.那么n的最大值为.12.设a是3的正整数次哥,b是2的正整数次哥,试确定所有这样的a,b ,使得二次方程x2-ax +b =0的根是整数.泉州现代中学初中数学竞赛材料练习( cjw) 第3页共7页2 3 2 ..................13 .是否存在这样的正整数 n ,使得3n +7n-1能整除n +n +n+1?请说明理由.14 .使得2n(n+1)(n+2)(n+3)+12可表示为2个正整数平方和的自然数 n () 2 2(m,n ),满足万程 m +25n =10mn + 7( m + n ). 16 .方程x 3+6x 2+5x =y 3-y +2的整数解(x, y)的个数是( ).(A) 0 (B) 1 (C) 3 (D)无穷多117 .a, b 都是正整数,试问关于 x 的万程x 2-abx+1(a+b) = 0是否有两个整数解？如果有,请把它们求出来；如果没有,请给出证实 .泉州现代中学初中数学竞赛材料练习( cjw) 第4页共7页 A 不存在 B 有1个 C 有2个 D 有无数个15.证实：存在无穷多对正整数18.关于x, y的方程x2 +y2 =208(x —y)的所有正整数解为19.设a为质数,b为正整数,且9(2a + b)2 =509(4a + 511b)求a, b的值.20.正整数a满足192 a3+191,且a < 2021 ,求满足条件的所有可能的正整数a的和.21.试确定一切有理数r,使得关于x的方程rx2+(r+2K+r-1 =0有根且只有整数根.泉州现代中学初中数学竞赛材料练习( cjw) 第5页共7页22.p为质数,使二次方程X2 - 2px+p2 - 5p-1 = 0的两根都是整数,求出所有可能的p的值.23.设X ］为不超过X的最大整数,求方程4x2—40lx】+ 51=0的解.泉州现代中学初中数学竞赛材料练习〔cjw〕第6页共7页泉州现代中学初中数学竞赛材料练习〔cjw〕第7页共7页。

第三章同余1 同余的概念及其基本性质定义1 设m Z ，称之为模。

若用m去除两个整数a与b所得的余数相同，则称a, b对模m同余，记作： a b (mod m)；若所得的余数不同，则称a, b对模m不同余，记作： a b (mod m)。

例如，8 1 (mod 7)，；所有偶数 a 0 (mod 2)，所有奇数 a 1 (mod 2)。

同余是整数之间的一种关系，它具有下列性质：1、 a a (mod m)；(反身性)2、若a b (mod m)，则 b a (mod m)；(对称性)3、若 a b (mod m)， b c (mod m)，则 a c (mod m)；(传递性)故同余关系是等价关系。

定理1 整数a, b 对模m 同余的充分必要条件是m | (a b)，即a b mt，t Z。

证明设 a mq1 r1， b mq2r2，0 r1 , r2m，则 a b (mod m) r1 r2 a b m(q1 q2 ) m | (a b)。

性质1 (1) 若a1 b1 (mod m)，a2 b2 (mod m)，则a1a2 b1 b2 (mod m)；(2) 若a b c (mod m)，则 a c b (mod m)。

性质2 若a1 b1 (mod m)，a2b2(mod m)，则a1a2b1b2(modm)；特别地，若 a b (mod m)，则 k a kb (mod m)。

定理2 若 A 1 k B 1 k (mod m)， x i y i (mod m)， i 1,2, , k ，B 1 k y 1 1y k k(mod m)；特别地，若 a i b i (mod m)，1kn n1i 0,1,2,, n ，则a n x a n 1x性质3 若 a a 1d ， b b 1d ， (d , m) 1， a b (mod m)，则 a 1 b 1 (mod m)。

性质4 (1) 若 a b (mod m)， k 0，则 ak bk (mod mk)；(2) 若 a b (mod m)， d 是 a, b 及 m 的任一公因数，则a b(mod m )。

同余式知识定位数论是初中数学竞赛比较重要的一个知识点，在历年竞赛中占据非常发比例，其中同余理论是初等数论中的重要内容之一，其同余式概念及应用，剩余系概念要熟练掌握。

本文归纳总结了同余的若干性质，将通过例题来说明这些方法的运用。

知识梳理1、同余概念定义1：给定一个正整数m，如果用m去除a，b所得的余数相同，则称a与b对模m 同余，记作a≡b(modm)，并读作a同余b，模m。

（1）若a与b对模m同余，由定义1，有a=mq1＋r，b=mq2+r．所以a-b=m(q1-q2)，即m｜a-b。

反之，（2）若m｜a-b，设a=mq1＋r1，b=mq2＋r2，0≤r1，r2≤m-1，则有m｜r1-r2．因｜r1-r2｜≤m-1，故r1-r2=0，即r1＝r2。

于是，我们得到同余的另一个等价定义：定义2：若a与b是两个整数，并且它们的差a-b能被一正整数m整除，那么，就称a与b对模m同余．2、同余定理定理1：（1）a≡a(modm)．（2）若a≡b(modm)，则b≡a(modm)．（3）若a≡b(modm)，b≡c(modm)，则a≡c(modm)．定理2：若a≡b(modm)，c≡d(modm)，则a±c≡b±d(modm)，ac≡bd(modm)．证：由假设得m｜a-b，m｜c-d，所以m｜(a±c)-(b±d)，m｜c(a-b)＋b(c-d)，即a±c≡b±d(modm)，ac≡bd(modm)．由此我们还可以得到：若a≡b(modm)，k是整数，n是自然数，则a±k≡b±k(modm)，ak≡bk(modm)，a n≡b n(modm)．定理3：若ac≡bc(modm)，且(c，m)=1，则a≡b(modm)．定理4： 若n ≥2，a ≡b(modm 1)，a ≡b(modm 2)，…………a ≡b(modm n )，且M=[m 1，m 2，…，m n ]表示m 1，m 2，…，m n 的最小公倍数，则a ≡b(modM)3、剩余类和完全剩余系全体整数集合可按模m 来划分：当且仅当()mod a b m ≡时，a 和b 属于同一类。

初中数学竞赛专题复习第三篇初等数论第20章同余试题新人教版第20章同余20.1.1★(1)证明：任意平方数除以4，余数为0或1；(2)证明：任意平方数除以8，余数为0、1或4．解析 (1)因为奇数()222214411(mod 4)k k k =+=++≡，偶数()222240(mod 4)k k ==≡，所以，正整数21(mod 4),;0(mod 4),.n n n ?≡??奇偶为数为数 (2)奇数可以表示为21k +，从而奇数()22441411k k k k =++=++．因为两个连续整数k 、1k +中必有一个是偶数，所以()41k k +是8的倍数，从而奇数()2811mod8i =+≡．又，偶数()22224k k ==(k 为整数)．若k =偶数2t =，则()224160mod 8k t ==．若k =奇数21t =+，则 ()()22244211644(mod8)k t t t =+=++≡．所以，平方数()()()0mod8,1mod8,4mod8.≡评注事实上，我们也可以这样来证：因为对任意整数a ，有0a ≡，±1，2(mod4)，所以，0a ≡，1(mod4)；又a ≡0，±1，±2，±3，4(mod8)，所以，2a ≡0，1，()4mod8．20.1.2★求证：一个十进制数被9除所得的余数，等于它的各位数字被9除所得的余数．解析设这个十进制数1210n n A a a a a a -=L ．因10≡1(mod9)，故对任何整数k ≥1，有()1011mod9k k ≡=．因此1210n n A a a a a a -=L1110101010n n n n a a a a --=?+?++?+L()110mod9n n a a a a -≡++++L ．即A 被9除所得的余数等于它的各位数字之和被9除所得的余数．评注 (1)特别地，一个数能被9整除的充要条件是它的各位数字之和能被9整除．(2)算术中的“弃九验算法”就是依据本题的结论．20.1.3★★求证：(1)()199985517+；(2)()2837n +；(3)()100017191-．解析 (1)因()551mod8≡-，所以()1999551mod8≡-，()19995517117160mod8+≡-+=≡，于是19998(5517)+．(2)因为2391(mod8)=≡，231(mod8)n ≡，所以()237170mod8n +≡+≡，即()2837n +．(3)因为()192mod17≡，()44192161mod17≡=≡-，所以()()()25025010004191911mod17=≡-≡，于是()100017191-．20.1.4★★对任意的正整数n ，证明：2903803464261n n n n A =--+能被1897整除．解析 18977271=?，7与271互质．因为()29035mod7≡，()8035mod7≡，()4642mod7≡，()2612mod7≡，所以()290380346426155220mod7n n n n n n n n A =--+≡--+=，故7|A又因为()2903193mod271≡，()803261mod271≡，()464193mod271≡，所以2903803464261n n n n A =--+()1932611932610mod271n n n n ≡--+=，故271|A因(7，271)=1，所以1897整除A ．20.1.5★证明：2222555555552222+能被7整除．解析因为()55554mod7≡，()34641mod7≡≡，所以()22222222222205555444162mod 7≡≡?≡≡．因为()22223mod7≡，()232mod7≡，()231mod7≡，所以55555555555502222333≡≡?()9252263333223≡≡??()5mod7≡．于是()()()222255555555222225mod 70mod 7+≡+≡，即 222255557|55552222+．20.1.6★★求最大的正整数n ，使得102431-能被2n 整除．解析因为()()()()()1024512256112831313313131+-=+++-L ，①而对于整数k ≥1，有()()2231112mod4kk +≡-+=，所以，①式右边的11个括号中，(3+1)是4的倍数，其他的10个都是2的倍数，但不是4的倍数．故n 的最大值为12．20.1.7★求使21n -为7的倍数的所有正整数n ．解析因为()3281mod 7≡≡，所以对n 按模3进行分类讨论．(1)若3n k =，则()()3212181110mod7k n k k -=-=-≡-=； (2)若31n k =+，则()321221281kn k -=?-=?- ()2111mod 7k ≡?-=;(3)若32n k =+，则()2321221481kn k -=?-=?- ()4113mod 7k ≡?-=．所以，当且仅当3|n 时，21n -为7的倍数．20.1.8★设n 是正整数，求证：7不整除()41n +．解析因为()144mod 7≡，()242mod 7≡，()341mod 7≡．所以当3n k =时，()()34141112mod7k n +=+=+=；当31n k =+时，()()341441415mod7k n +=?+=+=；当32n k =+时，()()34141611613mod7k n +=?+=+=．所以，对一切正整数n ，7不整除41n +．20.1.9★今天是星期日，过1003天是星期几?解析()33271mod 7=≡-，所以()()()333310033331334mod7=?≡-?=-≡．因此，过1003天是星期四．20.1.10★★求3326(25746)+被50除所得的余数．解析()2577mod50≡，()33332577mod50≡．又()27491mod50=≡-，所以()471mod 50≡．()()83347777mod50=?≡．即()332577mod50≡．从而()33257467463mod50+≡+≡．()332626(25746)3mod50+≡．由于()532437mod50==-．()103491mod50≡≡-，所以()2031mod50≡．于是()()262053333732129mod50=??≡-?=-≡．故3326(25746)+除以50所得的余数为29．20.1.11★(1)求33除19982的余数；(2)求8除2171n +-的余数．解析 (1)先找与()1mod33±同余的数．因为()52321mod33=≡-，所以()1021mod33≡．()()199199810532222825mod33=??≡-≡．故所求的余数为25．(2)因为()71mod8≡-，所以()()2121711mod8n n ++≡-=-，()217126mod8n +-≡-≡．即余数为6．20.1.12★求5555512399100+++++L 除以4所得的余数．解析因为()()520mod 4n ≡，()()52121mod 4n n +≡+，所以5555512399100+++++L()213599500mod4≡++++=≡L ．20.1.13★形如221k n F =+，n =0，1，2，…的数称为费马数．证明：当n ≥2时，n F 的末位数字是7．解析当n ≥2时，2n 是4的倍数，故令24n t =．于是212k n F +=()421161617mod10t t t =+=+=+≡．即n F 的末位数字是7．评注费马数的头几个是03F =，15F =，217F =，3257F =，465537F =，它们都是素数．费马便猜测：对所有的正整数n ，n F 都是素数．然而，这一猜测是错误的．首先推翻这个猜测的是欧拉，他证明了下一个费马数5F 是合数．有兴趣的读者可以自己去证明．20.1.14★★已知1919191919 191 919 1 919n =L 144424443个，求n 被9除后所得商的个位数字是多少?解析因为1919191919 191 919 1 919n =L 144424443个()19191919≡?+++()191920224mod9≡?≡?≡．所以9|4n -．又4n -的个位数字是5，故n 被9除后所得商的个位数字是5．20.1.15★★求9992的末两位数．解析因为()10210mo d 25+≡，()1021mod 25≡-，()()()10010010211mod 25≡-=，()1000210mod 25-≡．所以100021-的末两位数字只可能是00、25、50、75，即10002的末两位数字只可能是01、26、5l 、76．又10002是4的倍数，故10002的末两位数字只可能是76．又9991000222=÷，所以9992的末两位数字只可能是38、88，而4|88，4|38，故9992的末两位数字是 88．20.1.16★★求所有的正整数n ，使得2337n n ++是一个立方数．解析假设存在正整数m 、n ，使得23337n n m ++=，则()31mod3m ≡，于是()31mod3m ≡．设31m k =+，则223(331)2k k k n n ++=++，易知22n n ++不能被3整除，故不存在正整数n ，使得2337n n ++是一个立方数．20.1.17★★有一列数排成一行，其中第一个数是3，第二个数是7，从第三个数开始，每个数恰好是前两个数的和，那么，第1997个数被3除，余数是多少?解析该数列是：3，7，10，17，27，44，71，115，186，301，487，788，…除以3的余数分别是：0，1，1，2，0，2，2，1，0，1，1，2，0，2，2，1，…余数刚好是按“0，1，1，2，0，2，2，1”八个一循环．又1997≡5(mod 8)，因此所求余数为0．20.1.18★★★求777的末位数字和{7777k N 个的末两位数字，其中k 是大于1的正整数．解析我们知道，求一个数的末位数字就是求这个数除以10的余数，求一个数的末两位数字就是求这个数除以100的余数．为此，先设法求出71(mod10)t ≡中的t ，然后求出77at b =+(a ，b 是整数)中的b ．这样，问题归结为求67被10除所得的余数．因为()()2371mod1073mod10≡-≡，，()()4471mod1071mod10m ≡≡，，m 是正整数．而()()()66673mod 47311mod 4≡≡≡-≡，．所以，()773mod 4≡．可设7743m =+．于是()774337773mod10m +≡≡≡．所以，777的末位数字是3．考虑777的末两位数字．这时，由()2749mod100≡，()3743mo d100≡，()471mod100≡，得()471mod100n ≡．而{77211777t k +-=N 个，其中t 是整数且t ≥0．于是{()()217721211777313mod 4t t t k +++-≡≡≡-≡N 个．可设{7717743k n -=+N 个，那么{()774331777743mod100n k +-=≡≡N 个．所以，所求的末两位数字是43．20.1.19★★求n =1×3×5×…×1997×1999的末三位数字．解析这个积显然是5×25=125的倍数，设n =5×25×1×3×7×…×23×27×…×1999=125m ．由于1000=8×125，所以，我们只需求出m 除以8所得的余数，进而便可求得n 除以1000的余数．m =(1× 3×7)×(9×11×13×15)×(17×19×21×23)×(27×29×31)×(33×35×37×39)×…×(1985×1987×1989×1991)×(1993×1995×1997×1999)在上述乘积中，除第一和第四个括号外，每个括号中都是四个数的乘积，这个积是()()()()81838587k k k k ++++1≡×3×5×71≡()mod8．而()1375mod8??≡，()2729311mod8??≡．于是()515mod8m ≡?≡．所以，()()125125851255625mod1000m k =?+≡?=，即n 的末三位数字是625．20.1.20★★★★如果k 是大于1的整数，a 是210x kx -+=的根．对于大于10的任意正整数n ，22n na a -+的个位数字总是7，求是的个位数字．解析首先，我们证明k 的个位数字不可能是偶数．其次，根据22n na a -+与7对模10同余，从中确定k 的个位数字．因为a 是210x kx -+=的根，所以这方程的另一个根是1a．于是 1a k a+=．如果k 的个位数字是偶数，那么 2222122a a a k a -??+=+-=- 的个位数字仍是偶数．()22222222a a k -+=-- 的个位数字也是偶数．对于10n >，22n na a -+的个位数字也是偶数，与题设矛盾．k 的末位数字不能是偶数．(1)如果k 的个位数字是1或9，那么()221mod10a a -+≡-，由此得()221mod101n n a a n -+≡-，≥． (2)如果k 的个位数字是3或7，那么()227mod10a a -+≡，由此得()227mod10n na a -+≡，1n ≥．(3)如果k 的个位数字是5，那么()223mod10a a -+≡，()22227mod10a a -+≡．所以()227mod10n n a a -+≡，2n ≥．综上所述，k 的个位数字是3或5或7．20.1.21★★2005年12月15日，美国中密苏里州大学的数学家Curtis Cooper 和Steven Boone 教授发现了第43个麦森质数3040245721-，求这个质数的末两位数．解析因为()10210241mod 25=≡-，所以()()3040545304024530402457107722212≡?≡-?()128322mod 25≡-≡-≡，所以，304024572的末两位数只能是22、47、72、97．又304024572≡0(mod4)，所以，304024572的末两位数只能是72．从而，3040245721-的末两位数是71．20.1.22★★★求最小的正整数a ，使得存在正整数n ，满足2001|5532n n a +?．解析因为2001=3×23×29，所以，要使2001|5532n n a +?，只要使3|5532n n a +?，23|5532n n a +?，29|5532n n a +?．易知()()553211mod3nn n a a +?≡+-，()()55329919mod 23n n n n n a a a +?≡+?≡+?，()()553233mod 29nn n n a a +?≡-+?．(1)若n 是奇数，则()1mod3a ≡，()1mod 23a ≡-，()1mod 29a ≡，而(3，29)=1，故()1mod87a ≡ ．令12871231a k k =+=-，则18720(mod23)k +≡，所以()1520mod 23k -+≡，即()145180mod 23k -+≡，所以()118mod23k ≡-，则1k 能取的最小正整数是5．所以n 是奇数时，a 的最小正整数解是 8751436?+=．(2)若n 是偶数，则()1mod3a ≡-，()1mod 23a ≡-，()1mod 29a ≡-，由于(3，23)=1，(3，29)=1，(23，29)=1，所以1a ≡-(mod3×23×29)．故当n 是偶数时，a 的最小正整数解是323291??-等于2000．综上所述，满足条件的最小正整数a 为436．20.1.23★★证明：对任意正整数n ，87n +不可能是三个整数的平方和．解析假设存在整数a 、b 、c ，使得22287n a b c +=++．由于对任意整数x ，2x ≡0，1，4(mod8)，于是222a b c ++≡0，1，2，3，4，5，6(mod8)．而()877mod8n +≡，矛盾！20.1.24★证明不定方程22257x y -=无整数解．解析因为22257x y =+，显然，y 是奇数．(1)若x 为偶数，则()220mod8x ≡．又()21mod8y ≡．所以()2574mod8y +≡，矛盾，故x 不能为偶数．(2)若x 为奇数，则()222mod4x ≡．但()2570mod 4y +≡，矛盾，故x 不能为奇数．由(1)，(2)可知：原方程无整数解．20.1.25★证明：不定方程2286a b c +-=没有整数解．解析如果n ≡0，1，2，3(mod4)，那么2n ≡0，1，4(mod 8)．所以22a b +≡0，1，2，4，5(mod8)．但与()226mod8a b +≡矛盾．从而原不定方程无整数解．20.1.26★证明：不定方程4425x y z ++=没有整数解．解析以5为模，如果0x ≡，±1，±2(mod5)，那么2x ≡0，1，4(mod5)，4x ≡0，1，1(mod5)．即对任一整数x ，4x ≡0，1(mod5)．同样，对任一整数y ，4y ≡0，1(mod5)．所以442x y ++≡2，3，4(mod5)．从而原不定方程无整数解．20.1.27★★★求最小的正整数n ，使得存在整数1x ，2x ，…，n x ，满足444121599n x x x +++=L ．解析对任意整数a ，可知()20mod4a ≡或()21mod8a ≡，由此可得40a ≡或()1mod16．利用这个结论，可知，若n <15，设()44412mod16n x x x m +++=L ，则m ≤n <15，而1599≡()15mod16，矛盾，所以n ≥15．另外，当n =15时，要求()444121mod16n x x x ≡≡≡≡L ，即1x ，2x ，…，n x 都为奇数，这为我们找到合适的数指明了方向．事实上。

第20章 同 余20。

1.1★（1）证明:任意平方数除以4,余数为0或1； （2)证明：任意平方数除以8，余数为0、1或4． 解析 （1）因为奇数， 偶数, 所以，正整数(2)奇数可以表示为,从而奇数． 因为两个连续整数、中必有一个是偶数，所以是8的倍数，从而奇数． 又，偶数(为整数）．若偶数,则． 若奇数，则． 所以，平方数评注 事实上，我们也可以这样来证：因为对任意整数，有，±1，2()，所以，，1()；又0，±1，±2,±3，4(）,所以,0，1，． 20。

1.2★求证：一个十进制数被9除所得的余数，等于它的各位数字被9除所得的余数．解析 设这个十进制数． 因101（)，故对任何整数≥1，有．因此．即被9除所得的余数等于它的各位数字之和被9除所得的余数．评注 (1)特别地,一个数能被9整除的充要条件是它的各位数字之和能被9整除．(2)算术中的“弃九验算法”就是依据本题的结论． 20。

1.3★★求证：（1）；（2);()222214411(m o d 4)k k k =+=++≡()222240(m o d 4)k k ==≡21(m o d 4),;0(m o d 4),.n n n ⎧≡⎨⎩奇偶为数为数21k +()22441411k k k k =++=++k1k +()41k k +()2811m o d 8i =+≡()22224k k ==kk =2t =()224160m o d 8k t ==k =21t =+()()22244211644(m o d 8)k t t t =+=++≡()()()0m o d 8,1m o d 8,4m o d 8.⎧⎪≡⎨⎪⎩a 0a ≡mod40a ≡mod4a ≡mod82a ≡()4mo d 81210n n Aa a a a a -=≡mod9k ()1011m o d 9k k≡=1210n n Aa a a a a -=1110101010nn n n a a a a --=⨯+⨯++⨯+()110m o d 9n n a a a a -≡++++A ()199985517+()2837n +(3）． 解析 （1)因，所以 ，，于是．（2)因为,，所以，即 ．（3）因为,，所以 , 于是．20.1.4★★对任意的正整数，证明：能被1897整除．解析 ,7与271互质．因为 ,， ，，所以,故7|又因为 ， ，，所以，故271｜因(7，271）=1，所以1897整除．20.1。