第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≡，()464193mod271≡，所以2903803464261n n n nA =--+()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 -=⋅-=⋅- ()4113mod 7k ≡⋅-=．所以，当且仅当3|n 时，21n-为7的倍数．20.1.8★设n 是正整数，求证：7不整除()41n +．解析 因为()144mod 7≡，()242mod 7≡，()341mod 7≡．所以当3n k =时，()()34141112mod7k n +=+=+=； 当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、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 个的末两位数字，其中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 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 +++=．解析 对任意整数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 都为奇数，这为我们找到合适的数指明了方向．事实上。