费尔马小定理及其应用

本文格式为Word版，下载可任意编辑——费尔马小定理及其应用费尔马小定理及其应用

费马尔（Fermat）小定理是初等数论中的一个重要定理，数学竞赛中经常需要用到这个定理.

Fermat小定理设p为质数，a为整数，则ap?a(modp).特别地，若p／a，则ap?1?1(modp).

例1设m、n为正整数，m是模m的一个完系，可知2?1,2?2,┄，

2?m也是模m的一个完系（完系的定义见2.1节）.所以，由同

余的性质知

1n?2n???(2?m)n(modm),

即m(2n?1)(1n?2n???mn).结合（m,2n?1)?1可知结论成立.

说明尽管当n为奇数时，对和式1n?2n???mn，可以通过“首尾配对〞，即将kn与(m?k)n配对后用因式分解的方法证出

m1n?2n???mn，但在n为偶数时，这种配对就无效了.

请细心体

会证明中“整体处理〞的思想.

下面我们将视角换到Fermat小定理的应用上.

例2设n为正整数.证明：73n?n的充要条件是73nn3?1.证明若73n?n3，则7／n，

3于是，由Fermat小定理，知

n6?1(mod7),从而，由73n?n3，知7(3n?n3)n3，故73nn3?1.反过来，若73nn3?1,则7∕n，并且7(3nn3?1)?n3，即73n?n6?n3，利用Fermat小定理知n6?1(mod7),故73n?n3.命题获证。

说明涉及指数的同余式经常需要用到Fermat小定理，由于由Fermat小定理得出的结论中，同余式的一边是1，这带来很大的便利.

例3由Fermat小定理知，对任意奇质数p，都有2p?1?1(modp).问：是

否存在合数n，使得2n?1?1(modn)成立？

解这样的合数n存在，而且有无穷多个.其中最小的满足条件的合数n?341?11?31（它是从两个不同奇质数作乘积去试算出来的）.

事实上，由于210?1?1023?341?3,

故210?1(mod341),所以2340?134?1(mod341),故341符合要求.

进一步，设a是一个符合要求的奇合数，则2a?1是一个奇合数（这一点利用因式分解可知）。再设2a?1?1?a?q,q为正奇数，则22a?1?1?1?22(2a?1)?1?22aq?1?(2a)2q?1?12q?1?0(mod2a?1).

因此2a?1也是一个符合要求的数.依此类推（结合341符合要求），可知有无穷多个满足条件的合数.

说明满足题中的合数n称为“伪质数〞，假使对任意(a,n)?1都有an?1?1(modn)成立，那么合数n称为“绝对伪质数〞.请读者寻觅“绝对伪质数〞.

例4设p为质数.证明：存在无穷多个正整数n，使得p2n?n.证明假使p?2，那么取n为偶数，就有p2n?n，命题成立.设p?2，则由Fermat小定理知2p?1?1(modp).因此，对任意正整数k，都有2k(p?1)?1(modp),

所以，只需证明存在无穷多个正整数k，使得

k(p?1)?1(modp)（这样，令n?k(p?1),就有p2n?n).而这只需k??1(modp),这样的k当然有无穷多个.所以，命题成立.

说明用Fermat小定理处理数论中的一些存在性问题有时十分便利、简单.

例5设x为整数，p是x2?1的奇质因子，证明：p?1(mod4).证明由于p为奇质数，若p≡／1(mod4),则p?3(mod4)，可设

p?4k?3，此时，由x2??1(modp),得

xp?1?x4k?2?(x2)2k?1?(?1)2k?1??1(modp).而由Fermat小定理，应有xp?1?1(modp),结合上式将导出p2.矛盾.所以，p?1(mod4).

说明利用此题的结论，我们可以证明：存在无穷多个模4余1的正整数为质数.

事实上，若只有有限个质数模4余1，设它们是p1,p2,?,pn.考虑数(2p1p2?pn)2?1的质因子即可导出矛盾.

2p?1?1例6求所有的质数p，使得是一个完全平方数.

p解设p是一个满足条件的质数，则显然p是一个奇质数.由Fermat小定理知

p2p?1?1，而2p?1?1?(2p?12?1)(2p?12?1),

p?12故p2p?12?1或p2p?12?1.

p?12由于(2所以，p2若p2使得

p?12p?12?1,2p?12?1)?(2?1,2)?1,

?1与p2?1中恰有一个成立.

p?12p?12p?12?1，则由条件及(2?1,2?1)?1可知存在正整数x，

2p?12?1?x2，

p?12此时(x?1)(x?1)?2,

所以，x?1与x?1都是2的冥次，而x为奇数，故x?1与x?1是两个相继的偶数，所以，只能是x?1?2,x?1?4,故x?3，此时p?7.若p2p?12?1，则同上知存在正整数x，使得

p?122?1?x2,

当p?3时，导致