费马小定理 费马小定理（）是数论中的一个定理。假如formula_1是一个整数，formula_2是一个质数，那么formula_3是formula_2的倍数，可以表示为 formula_5 如果formula_1不是formula_2的倍数，这个定理也可以写成更加常用的一种形式 formula_8 费马小定理的逆叙述不成立，即假如formula_3是formula_2的倍数，formula_2不一定是一个质数。例如formula_12是formula_13的倍数，但formula_14，不是质数。满足费马小定理的合数被称为费马伪素数。 历史. 皮埃尔·德·费马于1636年发现了这个定理。在一封1640年10月18日的信中他第一次使用了上面的书写方式。在他的信中费马还提出a是一个素数的要求。 1736年，欧拉出版了一本名为“一些与素数有关的定理的证明”（拉丁文：Theorematum Quorundam ad Numeros PRIMOS Spectantium Demonstratio）”的论文集，其中第一次给出了证明。但从莱布尼茨未发表的手稿中发现他在1683年以前已经得到几乎是相同的证明。 有些数学家独立提出相关的假说（有时也被错误地称为中国猜想），当formula_15成立时，p是质数。这是费马小定理的一个特殊情况。然而，这一假说的前设是错的：例如，formula_16，而341=11×31是一个伪素数。所有的伪素数都是此假说的反例。 卡迈克尔数. 如上所述，中国猜想仅有一半是正确的。符合中国猜想但不是素数的数被称为伪素数。 更极端的反例是卡迈克尔数： 假设formula_1与561互质，则formula_18被561除都余1。这样的数被称为卡迈克尔数，561是最小的卡迈克尔数。Korselt在1899年就给出了卡迈克尔数的等价定义，但直到1910年才由卡迈克尔（Robert Daniel Carmichael）发现第一个卡迈克尔数：561。1994年William Alford、Andrew Granville及Carl Pomerance证明了卡迈克尔数有无穷多个。 证明. 方法一. （i）若formula_1是整数，formula_2是质数，且formula_21。若formula_2不能整除formula_23，则formula_2不能整除formula_25。取整数集formula_26为所有小于formula_2的正整数集合（formula_26构成formula_2的完全剩余系，即formula_26中不存在两个数同余formula_2），formula_32是formula_26中所有的元素乘以formula_1组成的集合。因为formula_26中的任何两个元素之差都不能被formula_2整除，所以formula_32中的任何两个元素之差也不能被formula_2整除。 换句话说，formula_21，考虑formula_40共formula_41个数，将它们分别除以formula_2，余数分别为formula_43，则集合formula_44为集合formula_45的重新排列，即formula_46在余数中恰好各出现一次；这是因为对于任两个相异formula_47而言（formula_48），其差不是formula_2的倍数（所以不会有相同余数），且任一个formula_47亦不为formula_2的倍数（所以余数不为0）。因此 formula_52 即 formula_53 在这里formula_54，且formula_55，因此将整个公式除以formula_56即得到： formula_57 也即 formula_5 （ii）若formula_2整除formula_1，则显然有formula_2整除formula_62，即formula_63。 方法二. 若formula_2为质数，formula_65为整数，且formula_66。考虑二项式系数formula_67，并限定formula_65不为formula_2或formula_70，则由于分子有质数formula_2，但分母不含formula_2，故分子的formula_2能保留，不被约分而除去，即formula_74恒为formula_2的倍数。 再考虑formula_76的二项式展开，模formula_2，则 formula_78 formula_79 formula_80 因此 formula_81 formula_82 formula_83 formula_84 formula_85 formula_86 formula_87 令formula_88，即得formula_5。 方法三. 在抽象代数教科书中，费马小定理常作为教授拉格朗日定理时的一个简单例子。显然只需考虑 formula_90 情形。此时模 formula_2 所有非零的余数，在同余意义下对乘法构成一个群，这个群的阶是 formula_92。考虑群中的任何一个元素 formula_93，根据拉格朗日定理，formula_93 的阶必整除群的阶。证毕。 formula_96 formula_97 formula_98 formula_99 formula_100 应用. 故余数为3。 推广. 欧拉定理. 费马小定理是欧拉定理的一个特殊情况：如果 formula_106 ，那么 formula_107 这里 formula_108 是欧拉函数。欧拉函数的值是所有小于或等于 formula_65 的正整数中与 formula_65 互质的数的个数。假如 formula_65 是一个素数，则 formula_112 ，即费马小定理。 上面证明费马小定理的群论方法，可以同理地证明欧拉定理。 考虑所有与 formula_65 互素的数，这些数模 formula_65 的余数所构成的集合，记为 formula_115，并将群乘法定义为相乘后模 formula_65 的同余。显然 formula_115 是一个群，因为它对群乘法封闭（若 formula_106 和 formula_119 则 formula_120），含幺元（即“1”），且任何一个元素 formula_1 的逆元素也在集合中（因为若 formula_122 则由群乘法封闭性任何formula_1 的幂次都在 formula_115 中，所以 formula_125 是 formula_115 这个有限集的子集）。根据定义， formula_115 的阶是 formula_108，于是根据拉格朗日定理， formula_115 中任何一个元素的阶必整除 formula_108。证毕。 卡迈克尔函数. 卡迈克尔函数比欧拉函数更小。费马小定理也是它的特殊情况。 formula_131 多项式除法. 因为formula_132 所以由formula_133的结果可以得出formula_134的结果 用多项式除法可以得出formula_135除以formula_136的次数少于formula_137的余式 例如formula_138，由多项式除法得到formula_139，则formula_140 这个余式的一般结果是： formula_141（除式） formula_142 n=0时为除式，用数学归纳法证明余式。 求formula_143 formula_144 formula_145