8.6 费马定理
从17世纪到18世纪，对数论贡献最大的，先是费马，然后是欧拉。在18世纪末，数论研究中的零乱散碎的局面，由于拉格朗日的工作而有了新的变化。
费马对数论的研究是从阅读丢番图的著作《算术》一书开始的。1640年，费马在给梅森的一封信中提出了三个定理，并宣称说，这三个定理是他关于数的性质的研究基础。这三个定理是：
（1）若n是合数，则2n-1是合数。
（2）若n是素数，则2n-2可被2n除尽。
（3）若n是素数，则除了2kn+1这种形式的数外，2n-1不能被其他素数除尽。例如，2×11-1=2047，其因数为23与89或2×11+1与8×11+1。
然而，以费马命名的定理，却是费马小定理和费马大定理。
费马大定理是出现在丢番图《算术》一书的页边注解中的一个猜想：xn+yn=zn，当n＞2时，没有整数解。他写道：“与此相对照的是，不可能将一个立方数分拆成两个立方数，一个四方数分拆成两个四方数。一般地说，任何次数大于二的高次方数都不能分拆成两个幂次相同的数。我已找到这一定理的绝妙证明，可惜这里空白太小，写不下。”
1736年，欧拉首先突破费马小定理的证明。他先后发表过三个证明，并做了两个推广。第一个推广是，如果e=pn-1（p-1）且p是素数，则ae被p除的余数为0或1。当n=1时，就是费马小定理。第二，他引起了欧拉函数πN的概念，即πN表示所有不大于N且与N互素的正整数的个数。后来，高斯采用φ（N）表示，譬如φ（5）=4，φ（6）=2。在欧拉函数的基础上，欧拉提出了著名的欧拉定理：“若（a，N）=1，那么aφ（N）-1能被N整除。”注意，当N是素数时，φ（p）=p-1，所以欧拉定理就是费马小定理。
比较一下这两个推广很有意义。第一个推广，确乎仅仅是推广，并没有脱出本来的基调。第二个推广创造了新的概念φ（N），定理的内容由此发生了一个飞跃。新概念成为数论研究中的重要工具，“推广”成了导向新天地的边衢。
费马定理（1640） 如果p是素数，则对于所有整数a，ap≡a（mod p）。
证明 如果a是p的倍数，显然ap≡0≡a（mod p）。所以我们只需考虑a mod p≠0的情况。因为p是一个素数，这意味着a与p互素。考虑数
这p个数都是不同的，因为如果ax mod p=ay mod p，则由定义ax≡by（mod p）。因此x≡y（mod p）。
由于（1）给出p个不同的数，所有这些数还都非负和小于p，我们看出，头一个数是零，而剩下的是在某个顺序下的整数1，2，…，p-1。因此，
用a来乘这个同余式的每边，我们得到
这就证明了定理，因为因式1×2×…×（p-1）的每一个因数都同p互素，故可将其删去。