发布时间 : 星期六 文章同余理论更新完毕开始阅读45cbec23bcd126fff7050b40
??513?5?1??533?4?1?5?1??(?8)?5?8?1
34??7?5?8?1??11?5?8?1??5?mod19?⑦
2157147由⑥、⑦得?x?y?1??z9??147?157?1?mod19?．
32故?x3?y?1??z9?147157?157147?1． 因此，原方程组无整数解．
例9.证明序列?2n?3n?2,3,??至少含有一个无穷子序列，且其中的项两两互质． （1971年第13届国际数学奥林匹克）
证明：⑴22?3?1，，23?3?5，24?3两两互质；
⑵假设正整数n1，n2，…，nk使序列?i?2n?3，2n?3，…，2n?3两两互质，则只要证明
12k2存在nk?1使2n?3与序列?i?中的每个数都互质，即得这k?1个数两两互质．由归纳法，原命
k?1题得证．
证明2n?3不含序列?i?中的所有数的质因子即可．设?p1,p2,?,pr?是由序列?i?中的所有数
k?1的质因子组成的集合，显然p1,p2,?,pr都是奇质数，即gcd?2,pi??1．则由费马小定理，得
2pi?1?1?modpi?．
rr因此2??pi?1?i?1?1?modpi?，其中?i?1,2,?,r．进而2i?1r??pi?1??3?1?3??2?modpi?．
而
???pi?1???3,pi??1． pi??3?都是奇质数，故gcd?2i?1????rr因此取nk?1???pi?1?，则2i?1nk?1?3?2i?1??pi?1??3与2i?3都互质，其中?i?1,2,?,k．
n例10.求所有的质数p、q，使得pq?5p?2p??5q?2q?． （1996年保加利亚数学奥林匹克）
解：显然质数p、q都不为2，则?p,q?1??1．
如果p5p?2p，由费马小定理，得5p?5?modp?，2p?2?modp?．从而p5?2，所以p?3． 假设p,q?3，则p5q?2q，q5p?2p．
9
不妨设p?q，由裴蜀定理，存在正整数u、v，使u?q?1??vp?1．
显然质数p、q都不为5，由费马小定理，得5q?1?1?modq?，2q?1?1?modq?．故q5q?1?2q?1． 所以q5u?q?1??2u?q?1??5vp?1?2vp?1?5?5vp?2vp??3?2vp，又q5p?2p，所以q3?2vp，矛盾． 所以p、q之一为3．
若p?q?3，满足题意，则?p,q???3,3?．
若p?3，q?3??3?，则q53?23?9?13，所以q?13． 因此，所求的解为(p,q)?(3,3),(3,13),(13,3)．
评注：完系、费马小定理结合二项式定理等是处理整除、同余问题的重要工具．
练习及参考答案
练习1.设质数p满足p?7?mod8?，证明p不能表示成三个平方数之和． 分析：我们利用平方数模8的性质进行处理．
证明：设存在三个整数a，b，c使p?a2?b2?c2．而对?x?Z，有x2?0,1,4?mod4?． 所以a2?b2?c2?0,1,2,3,4,5,6?mod8?，而得不到a2?b2?c2?7?mod8?． 因此形如p?7?mod8?的质数不能表作三个平方数之和．
练习2.一会议厅有n张椅子围绕着一张圆桌．n位代表在开会．第一位代表任意选择他（或她）的座位．此后第?k?1?位代表坐在第k位代表的右边的（按逆时针方向）第k个座位，这里1?k?n?1．（特别地，第两位代表坐在第一位的下一个座位．）每张椅子不能坐多于一位代表．求能得到如此安置代表座位的n值． （2002年英国数学奥林匹克第2轮） 解：n?2m，其中m是任一非负整数．
记这些座位的编号分别为0,1,2,?,n?1．第k位代表坐在座位于是如果这n个数
k?k?1?2，其中k?1,2,?,n．
k?k?1?对模n不同余，这里k?1,2,?,n，那么这个安置座位方案是可能的． 2首先，假设n?2m，其中m是非负整数．特别地，当m?0时，显然安置座位方案是可能的．
h?h?1?k?k?1??h?k??h?k?1???当m?0时，我们有．
222
10
若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