历史
皮埃尔·德·费马
皮埃尔·德·费马于1636年发现了这个定理。在一封1640年10月18日的信中他第一次使用了上面的书写方式。在他的信中费马还提出a是一个素数的要求。
1736年,欧拉出版了一本名为“一些与素数有关的定理的证明”(拉丁文:Theorematum Quorundam ad Numeros PRIMOS Spectantium Demonstratio)”[2]的论文集,其中第一次给出了证明。但从莱布尼茨未发表的手稿中发现他在1683年以前已经得到几乎是相同的证明。
有些数学家独立提出相关的假说(有时也被错误地称为中国猜想),当 成立时,p是素数。这是费马小定理的一个特殊情况。然而,这一假说的前设是错的:例如, ,而341=11×31是一个伪素数。所有的伪素数都是此假说的反例。
卡迈克尔数
如上所述,中国猜想仅有一半是正确的。符合中国猜想但不是素数的数被称为伪素数。
更极端的反例是卡迈克尔数:
假设 与561互质,则 被561除都余1。这样的数被称为卡迈克尔数,561是最小的卡迈克尔数。Korselt在1899年就给出了卡迈克尔数的等价定义,但直到1910年才由卡迈克尔(Robert Daniel Carmichael)发现第一个卡迈克尔数:561。1994年William Alford、Andrew Granville及Carl Pomerance证明了卡迈克尔数有无穷多个。
证明
方法一
(i)若 是整数, 是素数,且 。若 不能整除 ,则 不能整除 。取整数集 为所有小于 的正整数集合( 构成 的完全剩余系,即 中不存在两个数同余 ), 是 中所有的元素乘以 组成的集合。因为 中的任何两个元素之差都不能被 整除,所以 中的任何两个元素之差也不能被 整除。
换句话说, ,考虑 共 个数,将它们分别除以 ,余数分别为 ,则集合 为集合 的重新排列,即 在余数中恰好各出现一次;这是因为对于任两个相异 而言( ),其差不是 的倍数(所以不会有相同余数),且任一个 亦不为 的倍数(所以余数不为0)。因此
-
即
-
在这里 ,且 ,因此将整个公式除以 即得到:
- [3]
- 也即
(ii)若 整除 ,则显然有 整除 ,即 。
方法二
若 为素数, 为整数,且 。考虑二项式系数 ,并限定 不为 或 ,则由于分子有素数 ,但分母不含 ,故分子的 能保留,不被约分而除去,即 恒为 的倍数[4]。
再考虑 的二项式展开,模 ,则
-
-
-
因此
-
-
-
-
-
-
-
令 ,即得 。[3]
方法三
在抽象代数教科书中,费马小定理常作为教授拉格朗日定理时的一个简单例子[5]。显然只需考虑 情形。此时模 所有非零的余数,在同余意义下对乘法构成一个群,这个群的阶是 。考虑群中的任何一个元素 ,根据拉格朗日定理, 的阶必整除群的阶。证毕。
应用
- 计算 除以13的余数
-
-
-
-
-
故余数为3。
- 证明对于任意整数a而言, 恒为2730的倍数。
- 易由 推得 ,其中 为正整数。
- 故对指数13操作如下:13减1为12,12的正约数有1, 2, 3, 4, 6, 12,分别加1,为2, 3, 4, 5, 7, 13,其中2, 3, 5, 7, 13为素数,根据定理的延伸表达式, 为2的倍数、为3的倍数、为5的倍数、为7的倍数、为13的倍数,即2*3*5*7*13=2730的倍数。
- 证明对于任意整数a而言, 恒为3300的倍数。
证明
- 为132的倍数。
- 模仿前述操作,11减1为10,10的正约数有1, 2, 5, 10,分别加1,为2, 3, 6, 11,其中2, 3, 11为素数,因此 为2, 3, 11的最小公倍数的倍数,即66的倍数。
- 考虑 ,因为奇数的11次方仍为奇数,且奇数与奇数之和为偶数,故当a为奇数时, 为偶数;同理可知当a为偶数时, 仍为偶数。因此当a为任意整数时, 为偶数。
- 因此 的倍数 的倍数 的倍数。
- 为25的倍数。
- 由后文的欧拉定理可知 (当a与25互素时),即 (当a为任意整数时)。因此 为25的倍数。
- 因此 为132与25的的最小公倍数的倍数,即3300的倍数。
推广
注释
参见
参考