若h和k不相等，则h?k和h?k?1都是非零数，但它们具有相异奇偶性，并且都小于2n． 于是其中一个是奇数，另一个不能被比2m的指数更高的2的幂整除．
????????这样h?kh?k?1不能被2m整除，即hh?1与kk?1对模n不同余．
222因此安置座位方案在n是一个2的幂时可操作．
反之，假设n?2m?2a?1?，其中a是正整数，m是非负整数． 若a?2m，取h?2m?a?1，k?2m?a． 则h?k?2a?1，h?k?1?2m?1，
22h?h?1?2?k?k?1?2?2m?2a?1?．
????故hh?1和kk?1对模n同余．
若a?2m，取h?2m?a?1，k?a?2m?1． 则h?k?2m?1，h?k?1?2a?1，
22h?h?1?2?k?k?1?2?2m?2a?1?．
????故也得到hh?1和kk?1对模n同余．
上述h、k的取值都是1~n范围内的整数．
因此若n不是一个2的幂就没有可能的安置座位方案． 练习
3.求数200320022001的末三位数字．
（2003年加拿大数学奥林匹克）
解：因为2003?3?mod1000?，所以200320022001?320022001?mod1000?．
为解决这个问题，我们首先确定一个正整数n使3n?1?mod1000?． 由二项式定理，得32m??10?1????1??m?10???1?上式中前三项后的各项之和能被1000整除．
于是设m?2q，则34q?1?20q?100q?2q?1???mod1000?．①
由1?20q?100q?2q?1??1000k?1，5q2?3q?25k?0，由十字相乘法易得q?25满足． 从而3100?1?mod1000?．
而2002?2?mod100?，故20022001?22001?mod100??22?21999?mod4?25?． 因为210?1024??1?mod25?，所以21999??210?199mmm?1?m?m?1?2?10???1?2m?2???10m．
?2???1?9199?512??12?13?mod25?．
于是20022001?22001?4?13?52?mod100?，再由①，得
11
200320022001?320022001?3100k?52?352?1?20?13?1300?25?241?mod1000?．
因此数200320022001的末三位数字是241．
练习4.设三角形的三边长分别是整数l，m，n，且l?m?n．已知34?34?34，其
101010中?x??x??x?，而?x?表示不超过x的最大整数．求这种三角形周长的最小值． （2003年全国高中数学联赛加试）
解：由题意，知3l?3m?3n?mod104?，即3l、3m、3n的末四位数字相同． 又当且仅当l?m?n时，以l，m，n（l?m?n）为边才能构成三角形． 由二项式定理，得34p??10?1?2p??????lmn?1?20p?100p?2p?1??1000p?2p?1??2p?2?3???102p．
⑴由此容易得到，34p?1?mod10?．即i?1时，h?4p?4，34?1?mod10?； ⑵若?20p?100k，则34p?1?mod102?，当p?5q时，320q?1?mod102?． 即i?2时，h?20q?20，320?1?mod102?；
⑶若?20p?100p?2p?1??1000k，则320q?1?mod103?． 由25q2?3q?5k?0，得q?5r，3100r?1?mod103?． 即i?3时，h?100r?100，3100?1?mod103?． ⑷若?20p?100p?2p?1??1000p?2p?1??2p?2?3?10000k，
则3100r?1?mod104?，62500r3?4125r2?59r?30k?0，得r?5s，3500s?1?mod104?． 即i?4时，h?500s?500，3500?1?mod104?． 设m?n?500x，l?n?500y，其中x?y， 则n?500y?n?500x?n，n?500?y?x??500． 故l?m?n?3n?500?x?y??3?501?500?3?3003．
即当三角形的三边长分别为l?1501，m?1001，n?501时，其周长l?m?n取得最小值，且最小值为3003．
练习5.求证：存在无穷多个这样的正整数，它们不能表示成少于十个奇数的平方和． 分析：对于否定性问题，我们常利用同余．
12
解：设正整数n能够表示成n?x12?x22?...?xs2,① 其中xi为奇数，i?1,2,...,s,1?s?9.
若n?2(mod8)，则由①及xi2?1(mod8),i?1,2,...,s知s?2(mod8)，即s?2. 若s?2,3|n，则由①及xi2?0,1(modi3?),，被n?3(mod9)则s?2.综上所述，
知1,x21?x2?0(mod3)，从而9|n.这说明若
8除余2，被9除余3，即具有形式72k?66,k?0,1,2,...的
正整数便不能表示成①，故命题得证．
评注：对于某些问题，常常需要多次选择不同的模进行同余处理． 练习6.证明：2730n13?n． 分析：由原式联想到费马小定理． 证明：2730?2?3?5?7?13．
137532n?n?mod13?，n?n?mod7?，n?n?mod5?，n?n?mod3?，n?n?mod2?．由费马小定理，
而由n13?n?n?n12?1?易得n7?n|n13?n，n5?n|n13?n，n3?n|n13?n，n2?n|n13?n． 所以k|n13?n，k?2,3,5,7,13．且2，3，5，7，13两两互质，因此原结论成立． 练习7.求出大于1的整数n的个数，使得对任意的整数a，都有n|a25?a． 分析：联想例4，猜想n的最大值为2730．
解：设满足条件的正整数组成集合S，若n|a25?a，m|a25?a，则[m,n]|a25?a，因此S中全部数的最小公倍数也属于S，即S中的最大数是其余每个数的倍数．m|a25?a，则m的约数也整除a25?a，于是只需确定最大数m，其一切大于1的约数组成集合S．
?m|225?2,m|325?3，并且(225?2,3?3)?2?3?5?7?1，由例3254，由费马小定理，易证
2?3?5?7?13|a25?a，所以m?2?3?5?7?13，集合S共有31个元素．
评注：利用特殊值法确定最大值，再进行证明是处理竞赛问题的典型技巧．
练习8.2340?1(mod341)但341?11?13为合数，则称341是伪质数，证明：伪质数有无穷多个． 分析：我们想办法构造出具体的表达或递推关系．
证明：已知341为伪质数，假设m是伪质数，下面证明2m?1是伪质数．
首先，设m?pq，其中p,q为大于1的整数，则2m?1?2pq?1?(2p)q?1，含有因子2p?1，
13
并且1?2p?1?2m?1，所以2m?1为合数．其次，由于m|2m?1?1，设2m?1?1?ms，其中s为大于1的正整数，2(2m?1)?1?1?2?1)?12?2m?1?(22m?1?1?1)(22m?1?1?1)，而22m?1?1?1?2ms?1?(2)?1，
ms可被2m?1整除，因而2(2mmmm?1(mod(2?1))，所以2?1是伪质数，并且2?1?m．
由此可知伪质数有无穷多个．
评注：利用递推关系构造是解决无穷解问题的重要构造方法．
332002练习9.求最小的正整数n，使得x13?x2有整数解． ?...?xn?2002（第43届IMO预选题）
分析：我们先估计出n的值，在构造出一组解． 解：2002?4(mod9)，43?1(mod9)，2002?667?3?1， 所以20022002?42002?4(mod9)．又x3?0,?1(mod9)，其中x?Z．
33于是x13,x13?x23,x13?x23?x33??4(mod9)．由于2002?10?10?1?1，
则20022002?2002?(2002667)3?(10?2002667)3?(10?2002667)3?(2002667)3?(2002667)3． 所以n?4．
评注：选择适当的模，利用同余进行估计是重要的方法之一．
练习10.正整数n不能被2，3整除，且不存在非负整数a，b，使得2a?3b?n．求n的最小值．
（2003年中国集训队测试）
分析：我们先通过具体赋值猜出n值，再进行证明．
解：n?1时，21?31?1；n?5时，22?32?5；n?7时，21?32?7；
n?11时，24?33?11|；n?13时，24?31?13；n?17n?19时，23?33?19；n?23时，25?32?23；n?25n?29时，25?31?29；n?31时，25?30?31；
时，26?34?17； 时，21?33?25；
下证n?35满足要求，用反证法，若不然，存在非负整数a，b，使得2a?3b?35． ⑴若2a?3b?35，显然a?0，1，2，故a?3．
模8，得?3b?3?mod8?，即3b?5?mod8?，但3b?1,3?mod8?，不可能．
14
⑵若3b?2a?35，易知b?0，1，模9，得2a?1?mod9?， ∵?2k?mod9??:2,4,8,7,5,1,2,4,?
∴26k?1，26k?1?2，26k?2?4，26k?3?8，26k?4?7，26k?5?5?mod9?． 于是n?6k，其中k为非负整数，所以3b?82k?35．再模7，得3b?1?mod7?． ∵?3k?mod7??:3,2,6,4,5,1,3,2,?，故b?6k?，k?为正整数， ∴36k??26k?35，?33k??23k??33k??23k??35．∴
?3?2?1,或33k??23k?5, 3k?3k3?2?35;3?2?7.3k?3k?3k?3k于是，33k??18或6，不可能．综上可知，nmin?35． 评注：对于不定方程无解的问题常用同余处理． 练习11.证明：对于任意正整数n，??（2004年亚太地区数学奥林匹克）
分析：当n和n?1是合数时，容易处理，我们只要处理n和n?1之一是质数的情况． 证明：对于n?1,2,3,4,5，我们有??(n?1)!??0，显然为偶数．我们考虑n?62??n?n?(n?1)!?是偶数． 2??n?n?．
如果n和n?1是合数，则它们一定整除?n?1?!，并且互质．所以它们的乘积整除?n?1?!．由于n和n?1中只有一个是偶数，对于m?6，?m?2?!所含的2的幂指数大于m所含的幂指数，所以??(n?1)!?是偶数． 2??n?n?我们最后考虑n?1?p为一个质数，和n?p为一个质数． 如果n?1?p，则p?1是一个合数，所以p?1整除?p?2?!．令k??p?2?!p?1，由威尔逊定理
?p?2?!?1?modp?，所以k?p?1??1?modp?，因此k所以
k?1是一个整数．但kp??1?modp?．
pk?1是偶数，所以k?1是奇数，因此是奇数．
?k???n?1?!???又?k??k?1?1，所以????2?是偶数． ppp?????n?n? 15