费马小定理

费马小定理是初等数论里面一个很重要的结论。它声称:

p,a,Prime(p)ap=a\forall p, a,Prime(p) \rightarrow a^{p}=a

我仍然记得大一下学期的时候,初遇这个定理,顿觉手足无措、无所适从。我想要『理解』这个定理,换句话说,我想知道这些东西:

  • 这个定理是如何被发现的?
  • 有没有一个直观的理解可以让人『接受』这个事实?
  • 能不能从自然数的其他地方找到对这个事实的解释?

一般来说,定理的证明中有这些信息。然而,如果你搜索这个定理的证明,你会感觉到这证明实在是有点神奇:

1

当然,如果你已经懂了本文所要说的『直观解释』,那么这个证明对你来说就如同喝白开水一样平凡。但如果你不懂,那么你并不能从证明中获得对这个定理的理解。那么,究竟应该如何理解这个定理呢?

秘密之一:有限与无限

考虑任意的pp(不一定是素数)和aa,令

k=anmodpk = a^n \mod p

kk的取值是有限个还是无限个呢?显然,kk的个数是有限个。

这是因为,kk说到底也只能是Z/Zp\Z/\Z_p(如果不熟悉这种记法,可以把它理解为a(modp)a \pmod p的值)里的元素,而这个集合显然是有限的。也就是说,虽然nn是没有限制的,但anmodpa^n \mod p只能在一个有限范围内取值。下面把这个有限范围记为AA.

秘密之二:为什么是质数?

虽然kk的取值是有限集合AA,可是,为什么kk会再次回归到aa呢?问题的关键在于aa是不是一个可逆元素。如果它是可逆的,那么就会有一个非常有趣的性质:

因为AA是有限的,所以至少有一个元素tt满足n1,n2,an1an2(modp)\exist n_1,n_2, a^{n_1} \equiv a^{n_2} \pmod p,如此一来有:

an1an2(modp)a^{n_1} \equiv a^{n_2} \pmod p

由于aa是可逆的,an1a^{n_1}必然是可逆的,它的逆为(a1)n1(a^{-1})^{n_1},这样一来就有

1(a1)n2(an2)(modp)an2n1(modp)\begin{aligned} 1 \equiv& (a^{-1})^{n_2} (a^{n_2}) \pmod p \\ \equiv& a^{n_2-n_1} \pmod p \end{aligned}

这个an2n1(modp)a^{n_2-n_1} \pmod p如果乘一下aa,那么就会有:

an2n1+1a(modp)a^{n_2-n_1+1} \equiv a \pmod p

可见,如果aa可逆,那么必然有一个类似于『循环节』一样的东西,而这直接会导致11这个『单位元』在AA中,kk会再次回归到aa是很平凡的结论。

质数这时就立了头功,在模质数的剩余类中,每一个都是可逆的。所以这会导致每一个aa都有此性质。

不过,我们还需要继续认真考察ana^n所生成的集合。既然存在t=n2n1t=n_2-n_1那么一定存在一个最小的tt,把最小的tt记为t0t_0,对于任意的n1,n2n_1,n_2,如果n_1 < t_0 \and n_2 < t_0,那么an1≢an2(modp)a^{n_1} \not \equiv a^{n_2} \pmod p. 这也就是说,A=t0|A|=t_0.

其实这也是很显然的,因为把ana^nnn从大到小排列起来,11一定是『不同元素』中的最后一个。

秘密之三:拉格朗日定理

这个时候我们已经知道了AA大致长什么样子了。然而,t0t_0到底等于多少却仍然未知。我们刚才得到这个结论的手法,用的是一个很弱的条件。如果你明白群论的话,模pp的简化剩余系和乘法是构成了一个群的,这个群的阶数为p1p-1.

(A,×)(A,\times)这个东西构成了一个『子群』,由拉格朗日定理,它的阶数必然是p1p-1的因子。这样一来立刻可以得到t0p1t_0 \mid p - 1,自然有ap11(modp)a^{p-1} \equiv 1 \pmod p了。

如果不使用拉格朗日定理的证明过程,这个过程有没有直观解释呢?我暂时还没想到。