爱华网（选自《数论妙趣——数学女王的盛情款待》第六章 开门咒）
数论中充斥着许多易于观察到的事实，诱使人们用普通归纳推理的办法去进行推广。对此，必须慎之又慎，以免误入陷阱。
设想你偶而把2自乘7次，再减去2，得27－2＝126，随后发现，126恰好能被2的幂指数7整除。接着又发现，25－2＝30，30也能被2的幂指数5整除；211－2＝2048，2048也能被2的幂指数11整除。从7,5,11都是奇数产生一个想法，把2的幂指数换成偶数会怎么样？于是，又去试验24－2＝14，发现14不能被2的幂指数4整除；26－2＝62，62也不能被2的幂指数6整除；28－2＝254，254也不能被2的幂指数8整除。
这时，你或许会产生一个感觉：2的幂指数p为奇数时，2p－2似乎能被p整除；2的幂指数p为偶数时，2p－2似乎不能被p整除。为了慎重起见，你可能会测试一下29－2＝510，并惊讶地发现，9虽然是奇数，510却不能被2的幂指数9整除；还有，215－2＝32766，15虽然是奇数，32766也不能被2的幂指数15整除。于是感到，不能总在奇数和偶数上兜圈子，索性扩大试验范围，并对数据进行系统整理。于是得到：
P 2p－2 (2p－2)÷p
2(质数) 22－2＝4－2＝2 2÷2＝1
3(质数) 23－2＝8－2＝6 6÷3＝2
4(合数) 24－2＝16－2＝14 14不能被4整除
5(质数) 25－2＝32－2＝30 30÷5＝6
6(合数) 26－2＝64－2＝62 62不能被6整除
7(质数) 27－2＝128－2＝126 126÷7＝18。
8(合数) 28－2＝256－2＝254 254不能被8整除
9(合数) 29－2＝512－2＝510 510不能被9整除
10(合数)210－2＝1024－2＝10221022不能被10整除
11(质数)211－2＝2048－2＝20462046÷11＝186。
12(合数)212－2＝4096－2＝40944094不能被12整除
13(质数)213－2＝8192－2＝81908190÷13＝630
14(合数)214－2＝16384－2＝1638216382不能被14整除
15(合数)215－2＝32768－2＝3276632766不能被15整除
16(合数)216－2＝65536－2＝6553465534不能被16整除
17(质数)217－2＝131072－2＝131070131070不能被17整除
18(合数)217－2＝262144－2＝262142262142不能被18整除
19(质数)217－2＝524288－2＝524286524286÷19＝27594
20(合数)217－2＝1048576－2＝10485741048574不能被20整除
21(合数)217－2＝2097152－2＝20971502097150不能被21整除
22(合数)217－2＝4194304－2＝41943024194302不能被22整除
23(质数)217－2＝8388608－2＝83886068388606÷23＝364722
24(合数)217－2＝16777216－2＝1677721416777214不能被24整除
25(合数)217－2＝33554432－2＝3355443033554430不能被25整除
至此，事情已经非常清楚，你很可能会按耐不住兴奋的心情，作出自以为绝对正确无误的结论：
当p为质数时，2p－2能被p整除。当p为合数时，2p－2不能被p整除。
其实，这个结果，我国的古代先哲，早在公元前500年就已经知道了。只是到了1819年，有人发现，当p＝341时，2341－2也能被341整除，而341＝31×11，却是个合数，才使上面的“结论”产生动摇。
那么，真实情况又是怎样的呢？真实情况是：
p为质数时，2p－2恒能被p整除；p为合数时，2p－2有时也能被p整除。
通过这个事例，也使我们再一次认识到，仅仅靠归纳得出来的结论，往往是不可靠的。
后来，就是那位提出“xn＋yn＝zn，当n≥3时不成立”，而使无数数学大师为之绞尽脑汁苦思冥想了200多年，大名鼎鼎号称“业余数学王子”的费马，重新发现并证明了“p为质数时，2p－2恒能被p整除”，并且将其推广到：如果p为质数，xp－x（x是任意正整数）必能被p整除。
在提出公因子x后，xp－x＝x(xp－1－1)，并且设x不是p的倍数，这样，就得到著名的“费马小定理”：
若x是一个不能被质数p整除的整数，则xp－1－1必能被p整除。如果用同余式写法，就是xp－1≡1modp。
这种朴实无华的代数关系，似乎不会给人们留下什么深刻印象。然而它导致了众多的思维与奥妙的数学逻辑通道，因而被看成是数论大厦的一块基石。
费马小定理有着非常独特的作用，从下面这个例子，就可见一斑。
2134217826－1是一个非常非常大的数，有四千万位数字，需要40卷500页的大书，每页2000字，才能容纳得下。然而根据费马小定理，立即可以肯定它能被134217827整除。当然，先决条件是：134217827是质数。
费马小定理有多种证法，以同余证法最为简短而精致。
任意取一个质数，比如13。考虑从1到12的一系列整数1,2,3,4,5,6,7,8,9,10,11,12，给这些数都乘上一个与13互质的数，比如3，得到3,6,9,12,15,18,21,24,27,30,33,36。对于模13来说，这些数同余于3,6,9,12,2,5,8,11,1,4,7,10。这些余数实际上就是原来的1,2,3,4,5,6,7,8,9,10,11,12，只是顺序不同而已。
把1,2,3,…,12统统乘起来，乘积就是12的阶乘12！。把3,6,9,…,36也统统乘起来，并且提出公因子3，乘积就是312×12！。对于模13来说，这两个乘积都同余于1,2,3,…,12系列，尽管顺序不是一一对应，即312×12！≡12！mod13。两边同时除以12！得312≡1mod13。如果用p代替13，用x代替3，就得到费马小定理xp－1≡1modp。
需要提醒的是，不能把费马小定理理解为只是对质数成立。如果那样的话，就会得到一个判定质数的简单而实用准则：某数p能整除xp－1－1，则p必为质数。寻找简便易行的判定质数的方法，一直是人们梦寐以求的愿望。不幸的是，费马小定理对质数永远成立，对合数有时也成立，使得这一美好愿望落了空。不过，尽管如此，费马小定理仍然不失为数论大厦的一块基石。
