这是伯克利2013年秋数学博士资格的一道数论题。令 m=561，若 a 与m互素，证明am−1≡ 1 (m o d m ) . a^{m-1} \equiv 1 \pmod{m} .am−1≡1(modm).

分析: 这道题和Fermat小定理有很深的背景。Fermat小定理说: 若 p 为素数，对任意整数 a， 且 a 与 p 互素 (也即p∤ap \nmid ap∤a，除了k×pk\times pk×p的数)，满足ap−1≡ 1 (m o d p ) a^{p-1} \equiv 1 \pmod{p}ap−1≡1(modp)

我们自然要问，Fermat小定理的逆命题是否依然成立呢？也就是说,如果对所有与m互素的a，都满足am−1≡ 1 (m o d m ) , a^{m-1} \equiv 1 \pmod{m} ,am−1≡1(modm), 请问m是否一定是素数？显然这道题是Fermat小定理的逆命题不成立的一个反例。下面我们来证明。

由于m=561=3×11×17m=561=3\times11 \times 17m=561=3×11×17 ，所以m不是素数。 另外 a 与 m 互素，因此3∤a,11∤a,17∤a3 \nmid a, 11 \nmid a, 17 \nmid a3∤a,11∤a,17∤a，则根据Fermat小定理有a 2≡ 1 (  mod 3 ) , a 10≡ 1 (  mod 11 ) , a 16≡ 1 (  mod 17 ) a^{2} \equiv 1(\bmod 3), \quad a^{10} \equiv 1(\bmod 11), \quad a^{16} \equiv 1(\bmod 17)a2≡1(mod3),a10≡1(mod11),a16≡1(mod17) 但是2∣560,10∣560,16∣5602 | 560, 10 | 560, 16 | 5602∣560,10∣560,16∣560,所以a 560 a^{560}a560对3,11,17中的每一个模也都余1，即a 560≡ 1 (  mod 3 ) , a 560≡ 1 (  mod 11 ) , a 560≡ 1 (  mod 17 ) a^{560} \equiv 1(\bmod 3), \quad a^{560} \equiv 1(\bmod 11), \quad a^{560} \equiv 1(\bmod 17)a560≡1(mod3),a560≡1(mod11),a560≡1(mod17)由于3,11,173,11,173,11,17 的最小公倍数为3×11×17=561=m3\times11 \times 17 = 561=m3×11×17=561=m，根据同余性质，可知a 560≡ 1 (m o d 561 ) a^{560} \equiv 1 \pmod{561}a560≡1(mod561) 成立。

这个反例说明了Fermat小定理的逆命题是不成立的。

整个证明非常简洁，但是我们了解了出题背景后，就会感觉这题倍感亲切，而不是孤零零的了。另外费马小定理只是欧拉定理的一个特殊情形。关于欧拉定理请参考我的另外一篇文章从欧拉函数、欧拉定理到RSA加解密。

原文