综上所述，原方程无正整数解．
评注：方程右边可因式分解，而左边系数为3，因而选择模3对x进行分类处理． 例4.x、y是质数，解方程xy?yx?xy2?19． （2004年巴尔干地区数学奥林匹克） 分析：我们要充分利用x、y是质数的条件． 解：（Ⅰ）若x?y，则xy2?19．显然不可能． （Ⅱ）若x?y，则yx?xy?xy2?19．
而x、y是质数，由费马小定理，得xy?x?mody?．
∴yx?xy?xy2??x(mody)．即x??19(mody)．∴y|x?19① 由费马小定理，得yx?y(modx)．
∴yx?xy?xy2?y(modx)．即y?19(modx)．∴x|y?19②．
⑴若y?19，则由①知y?19?x，由②知x?y?19即y?x?19．∴y?x?19．
又y是质数且y?2，故y是奇质数．从而x?2，y?21不是质数．矛盾．所以此时无解． ⑵若y?19，则由①知19|x．故y?x?19．这与（Ⅰ）矛盾．
y|19?x,⑶若y?19，则由①、②，得x |19?x.?当y?17时，由x|19?y，得质数x?2．不满足y|19?x． 当y?13时，由x|19?y，得质数x?2或3．不满足y|19?x． 当y?11时，由x|19?y，得质数x?2．不满足y|19?x．
当y?7时，由x|19?y，得质数x?2或3．仅有?x,y???2,7?满足y|19?x，且满足原方程． 当y?5时，由x|19?y，得质数x?2或7．不满足y|19?x．
当y?3时，由x|19?y，得质数x?2．?x,y???2,3?满足y|19?x，且满足原方程． 综上，?x,y???2,7?,?2,3?为所求方程的解．
评注：在处理有关质数幂的问题中，费马小定理常发挥重要作用． 例5.设n是整数，求证：若2?21?12n2是整数，则它是完全平方数．
6
（2007年英国数学奥林匹克）
证明：由2?21?12n2?Z，n?Z，得1?12n2是完全平方数． 设1?12n2?m2?m?N??，则?m?1??m?1??12n2． 又m?1、m?1奇偶性相同，故m?1、m?1均为偶数． 则m?1?m?1?3n2．记m?1?t，则m?1?t?1，其中t?N?．
2222故t?t?1??3n2?*?．要证2?21?12n2?2?2m是完全平方数，只需证t是完全平方数． 根据?*?知，3t或3t?1，而gcd?t,t?1??1．
若3t，则由gcdt,t?1?1，且t??t?1??n2，知t与t?1都是完全平方数．
33?3?设t?k2，则t?3k2，t?1?3k2?1??1?mod3?不可能是完全平方数．矛盾．
3因此，3t?1．从而由gcdt,t?1?1，t?t?1?n2，知t与t?1都是完全平方数．
3??33综上，原结论成立．
注：还可利用佩尔方程理论解决这个问题． 三、完系、费马小定理及其它相关定理
例6.证明：对每个正整数n存在一个各位数字均为奇数的n位数能被5n整除． （2003年第32届美国数学奥林匹克）
证明：用数学归纳法．当n?1时，结论显然成立．
假设N?a1a2?an能被5n整除且各位数字都是奇数．考虑下列数：
N1?1a1a2?an?1?10?5M?5nnnnn?1?2nn?Mn?； ?； ?； ?； ?．
N2?3a1a2?an?3?10?5M?5N3?5a1a2?an?5?10?5M?5N4?7a1a2?an?7?10?5M?5N5?9a1a2?an?9?10?5M?5nnnnnn?3?2?5?2?M?M?M?Mnnn?7?2?9?2nnn而数1?2n?M,3?2n?M,5?2n?M,7?2n?M,9?2n?M是模5的完系， 所以N1,N2,N3,N4,N5中之一能被5n?5整除．归纳推理完成． 注：由此引申一个问题：
7
证明：对任意奇数，都可以找到它的一个倍数，使得该倍数的各位数字都是奇数． 这个问题利用例3的结论，再通过构造一个例子来证明这个命题．
p?1例7.设p是奇质数，证明：?k2p?1?k?1p?p?1?2?modp?．
2（2004年加拿大数学奥林匹克）
p?1证明：因为p?1是偶数，故?k2p?1?k?1?p?12k?1?k2p?1??p?k?2p?1???2p?1?i．
由二项式定理，得?p?k?模p2，得?p?k?故k2p?1??p?k?2p?112p?12p?1??Ci?0i2p?1?p???k?i．
2p?2?C2p?1?p???k?2p?2???k?22p?1??2p?1??p?k2p?2?k2p?1?modp?．
22p?1??2p?1??p?k2p?2??2p?p?k??pk2p?2?modp?．
2对1?k?p?1，必有gcd?k,p??1．由费马小定理，得kp?1?1?modp?．
故k2p?2?1?modp?．即pk2p?2?1．从而?pk2p?2??p?k2p?2?1??p??p?modp2?．
p?1因此?kk?12p?12p?p?1?p?1p?p22??p???p?modp?． ?222例
?x6?x3?x3y?y?1471578.求证：方程组?3329147?x?xy?y?y?z?157没有整数解．
（2005年第34届美国数学奥林匹克）
证明：①?②?1，得(x3?y?1)2?z9?147157?157147?1③． 考虑[2,9]?18，联系费马小定理，证明上式两边模19不同余． 由费马小定理，知gcd?a,19??1时，a18?1?mod19?； 否则gcd?a,19??1即19|a时，a18?0?mod19?． 因此?z9?2?z18?0或1?mod19?．从而z??1,0,1?mod19?④．
9对?n?Z，有n?0,?1,?2,?,?9?mod19?，所以n2??8,?3,?2,0,1,4,5,6,7,9?mod19?⑤． 由④、⑤，得?x3?y?1??z9???5,?6?mod19?⑥． 由费马小定理，得
147
1572?157147?1?(?5)157?5147?1??518?8?13?518?8?3?1
8
??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