费马小定理： \(a^{p}\equiv a\ (mod\ p)\)

陈一男个人学习网站 - 数论基础 - GeoGebra

费马小定理是数论中的一个重要定理，以下是关于它的详细介绍：

定理内容

如果 \(p\) 是一个质数，而 \(a\) 是任意整数，那么 \(a^{p}-a\) 是 \(p\) 的整数倍数，用模算术的符号表示为 \(a^{p}\equiv a\ (mod\ p)\).

若 \(a\) 不是 \(p\) 的倍数，即 \(a\) 与 \(p\) 互质，那么费马小定理可等价表述为 \(a^{p - 1}\equiv1\ (mod\ p)\).

举例说明

例如，当 \(a = 2\)，\(p = 7\) 时，\(2^{7}=128\)，\(128 - 2 = 126 = 7×18\)，即 \(2^{7}\equiv2\ (mod\ 7)\).

当 \(a = 3\)，\(p = 5\) 时，因为 \(3\) 与 \(5\) 互质，\(3^{4}=81\)，\(81\equiv1\ (mod\ 5)\) ，满足 \(a^{p - 1}\equiv1\ (mod\ p)\) 。

证明方法

利用二项式定理证明：当 \(a\) 与 \(p\) 互质时，考虑\((a + 1)^{p}\)的二项式展开\((a + 1)^{p}=\sum_{k = 0}^{p}C_{p}^{k}a^{k}\)，其中 \(C_{p}^{k}=\frac{p!}{k!(p - k)!}\)。对于\(0 < k < p\)，\(C_{p}^{k}=\frac{p(p - 1)\cdots(p - k + 1)}{k!}\)，因为 \(p\) 是质数，所以分子中的 \(p\) 不能被分母约掉，即\(p\mid C_{p}^{k}\)。那么\((a + 1)^{p}\equiv a^{p}+1\ (mod\ p)\)。由归纳法，已知 \(a^{p}\equiv a\ (mod\ p)\)，则\((a + 1)^{p}\equiv a + 1\ (mod\ p)\)，从而证明了费马小定理。

基于群论的证明：考虑整数模 \(p\) 的乘法群\(Z_{p}^{*}\)，其元素个数为\(p - 1\)。因为 \(a\) 与 \(p\) 互质，所以 \(a\) 在\(Z_{p}^{*}\) 中，根据群论中的拉格朗日定理，元素 \(a\) 的阶\(d\) 整除群的阶\(p - 1\)，即\(p - 1 = md\) 。那么 \(a^{p - 1}=a^{md}=(a^{d})^{m}\)，而 \(a^{d}\equiv1\ (mod\ p)\)，所以 \(a^{p - 1}\equiv1\ (mod\ p)\)。