这是伯克利2013年秋数学博士资格的一道数论题。令 m=561，若 a 与m互素，证明
\[a^{m-1} \equiv 1 \pmod{m} .\]
分析: 这道题和Fermat小定理有很深的背景。Fermat小定理说: 若 p 为素数，对任意整数 a， 且 a 与 p 互素 (也即$p \nmid a$，除了 $k\times p$的数)，满足
\[a^{p-1} \equiv 1 \pmod{p}\]
我们自然要问，Fermat小定理的逆命题是否依然成立呢？ 也就是说,如果对所有与m互素的a，都满足
\[a^{m-1} \equiv 1 \pmod{m} ,\]
请问m是否一定是素数？ 显然这道题是Fermat小定理的逆命题不成立的一个反例。下面我们来证明。
由于 $m=561=3\times11 \times 17$ ，所以m不是素数。 另外 a 与 m 互素，因此 $3 \nmid a, 11 \nmid a, 17 \nmid a$，则根据Fermat小定理有
\[a^{2} \equiv 1(\bmod 3), \quad a^{10} \equiv 1(\bmod 11), \quad a^{16} \equiv 1(\bmod 17)\]
但是$ 2 | 560, 10 | 560, 16 | 560$, 所以$a^{560}$对3,11,17中的每一个模也都余1，即
\[a^{560} \equiv 1(\bmod 3), \quad a^{560} \equiv 1(\bmod 11), \quad a^{560} \equiv 1(\bmod 17)\]
由于$3,11,17$ 的最小公倍数为 $3\times11 \times 17 = 561=m$，根据同余性质，可知
\[a^{560} \equiv 1 \pmod{561}\]
成立。
这个反例说明了Fermat小定理的逆命题是不成立的。
整个证明非常简洁，但是我们了解了出题背景后，就会感觉这题倍感亲切，而不是孤零零的了。另外费马小定理只是欧拉定理的一个特殊情形。关于欧拉定理请参考我的另外一篇文章 从欧拉函数、欧拉定理到RSA加解密 。
Fermat小定理的逆命题虽然是不成立的，但是这种反例的合数是非常稀少的(可能是具有的性质实在是太像素数了，但却是合数，所以不太容易出现)。这种反例的合数m被称之为Carmichael数(卡迈克尔数)。即合数m, 如果对所有与m互素的a，都满足
\[a^{m-1} \equiv 1 \pmod{m} ,\]
那么m就被称之为Carmichael数(卡迈克尔数)。
即使Carmichael数非常稀少，但是我们现在还不知道是否有无穷多个Carmichael数。 于是我写了个程序搜索1到一百万之间的Carmichael数(只有43个)，从下面的Carmichael数列表可知561是最小的Carmichael数。1到一百万之间的Carmichael数列表如下：
561:[3, 11, 17] 1105:[5, 13, 17] 1729:[7, 13, 19] 2465:[5, 17, 29] 2821:[7, 13, 31] 6601:[7, 23, 41] 8911:[7, 19, 67] 10585:[5, 29, 73] 15841:[7, 31, 73] 29341:[13, 37, 61] 41041:[7, 11, 13, 41] 46657:[13, 37, 97] 52633:[7, 73, 103] 62745:[3, 5, 47, 89] 63973:[7, 13, 19, 37] 75361:[11, 13, 17, 31] 101101:[7, 11, 13, 101] 115921:[13, 37, 241] 126217:[7, 13, 19, 73] 162401:[17, 41, 233] 172081:[7, 13, 31, 61] 188461:[7, 13, 19, 109] 252601:[41, 61, 101] 278545:[5, 17, 29, 113] 294409:[37, 73, 109] 314821:[13, 61, 397] 334153:[19, 43, 409] 340561:[13, 17, 23, 67] 399001:[31, 61, 211] 410041:[41, 73, 137] 449065:[5, 19, 29, 163] 488881:[37, 73, 181] 512461:[31, 61, 271] 530881:[13, 97, 421] 552721:[13, 17, 41, 61] 656601:[3, 11, 101, 197] 658801:[11, 13, 17, 271] 670033:[7, 13, 37, 199] 748657:[7, 13, 19, 433] 825265:[5, 7, 17, 19, 73] 838201:[7, 13, 61, 151] 852841:[11, 31, 41, 61] 997633:[7, 13, 19, 577]
注： []代表的是对应的素因数分解。
