如果n?p，则k??p?1?!p?1是偶数，所以k?1是奇数．由威尔逊定理k?p?1???1?modp?，所
????n?1?!??k?k?1以k?1是一个奇数，所以?k???2???p??p?1是偶数． pp???n?n???综上，原命题成立．
评注：当n和n?1之一是质数时，由?n?1?!我们联想到威尔逊定理． 练习12.设?an?，?bn?定义如下：
a0?1，a1?1，an?1?an?2an?1，b0?1，b1?7，bn?1?2bn?3bn?1?n?1,2,??．
证明：除“1”以外这两个数列没有其它相同的项．
证明：a0?1,a1?1,a2?3,a3?5,a5?11...，b0?1,b1?7,b2?17,b3?55,b4?161...
下面证明：a2n?1?5(mod8),a2n?2?3(mod8)；b2n?1?7(mod8),b2n?2?1(mod8)，其中n为正整数．
?a初值易验证，假设a2k?1?5(mod8),a2k?2?3(mod8)，则a2k?32k2??2a21k???3?25?5(mod8)，
a2k?4?a2k?3?2a2k?2?5?2?3?3(mod8)，可知n?k?1时结论成立．同理可证{bn}．
因而原命题成立．
练习13.求所有的正整数对?a,n?使得
?a?1?n?ann是整数．
证明：若a为任意正整数，则?a,1?显然是原问题的解，下面我们证明原问题没有其他解．若
n?2，易知?a,n???a,n?1??1，不妨设p为n的最小质因子，则
nnp?1p?a?1??a，又由费马小定理p?a?1??ap?1，而?p?1,n??1，由裴蜀定理存在
正整数u，v，使u?p?1??vn?1． 则p?a?1?u?p?1??au?p?1???a?1?vn?1?avn?1??a?1???a?1?vn?avn??avn，所以pavn，与?a,n??1矛盾．所以没有其他的正整数解．
练习14.试求与无穷数列an?2n?3n?6n?1?n?1,2,??的一切项均互素的所有正整数． （2005年第46届国际数学奥林匹克） 解：满足条件的正整数只有一个：1．
为此只要证明对任一素数p，存在正整数n使得pan．
16
由于a2?48，故p?2,3时结论为真．
设p?3，则p与2、3、6均互素，由费马小定理，2p?1?3p?1?6p?1?1?modp?． 于是2p?2?3?6p?2，3p?2?2?6p?2?modp?．
2p?2?3p?2?6p?2??3?2?1??6p?2?1?modp?．pap?2．证毕．
练习15.设k是一个大于1的固定的整数，m?4k2?5． 证明：存在正整数a、b，使得如下定义的数列
?xn?:x0其所有项均与m互质． （第45届IMO预选题）
?a,x1?b,xn?2?xn?1?xn，n?0,1,?
证：取a?1，b?2k2?k?2．因为4k2?5?modm?，所以2b?4k2?2k?4?2k?1?modm?． 从而4b2?4k2?4k?1?4k?6?4b?4?modm?．又因为m是奇数，故b2?b?1?modm?． 由于gcd?b,m??gcd?2k2?k?2,4k2?5??gcd?2k2?k?2,2k?1???2,2k?1??1， 故gcd?bn,m??1，其中n是任意正整数．
下面用数学归纳法证明：当n?0时，有xn?bn?modm?． 当n?0,1时，显然结论成立．
假设对于小于n的非负整数，结论都成立，其中n?2，
则有xn?xn?1?xn?2?bn?1?bn?2?bn?2?b?1??bn?2b2?bn?modm?． 因此，对于所有的非负整数n，有gcd?xn,m??gcd?bn,m??1．
练习16.设a,b???，且对?n???,都有?an?n??bn?n?．证明：a?b． （第46届IMO预选题）
证明：假设a?b，则b?a．取素数p?b，则?a,p???b,p??1． 由费马小定理，得ap?1?bp?1?1?modp?．
取n?k?p?1??1，则an?a?modp?，bn?b?modp?．从而an?n?a?n?modp?． 现在我们想让an?n?a?n?0?modp?，只要
17
a?n?a?n?a?k?p?1??1?a?1?k?0?modp?．
n因此仅须取k?a?1，即n??a?1??p?1??1即可． 此时p是an?a的质因子，故也是bn?b的质因子．
进而bn?n?b?n?b?a?0?modp?，即pb?a．但0?b?a?b?p，矛盾． 因此，原命题成立．
练习17.设p为质数．证明：存在一个质数q，使得对任意整数n，数np?p不能被q整除． （2003年第44届国际数学奥林匹克）
p?12p?12?1?p?p???p?p?1?modp?， 解：由于
p?1p?12则中至少有一个质因子q，满足q??1?modp?．
p?1pp下面证明q为所求．
假设存在整数n，使得np?p?modq?．则由q的选取，有np?pp?1?modq?． 另一方面，由费马小定理，nq?1?1?modq?（由于q为质数且?n,q??1）． 由于p2?|?q?1?，有?p2,q?1?|p，则np?1?modq?．因此，p?1?modq?． 从而，导出1?p???pp?1?p?modq?． 由q的选取，有p?0?modq?．矛盾．
2 18