模运算/费马小定理

费马小定理

如果 $p$ 是一个素数，而 $a$ 是一个整数，则

$a^{p}\equiv a{\pmod {p}}$

示例：3 的幂 让我们来看看一个数在模运算下的幂。我们将查看 $\displaystyle 3,3^{2},3^{3},3^{4}...$ 我们将在一个素数 $\displaystyle p$ 模下进行计算。首先，我们将选择 $\displaystyle p=7$。我们可以计算每个数，然后进行模运算，例如 $\displaystyle 3^{4}=3\times 3\times 3\times 3=81\equiv 4\,\mathrm {mod} \,7$ $\displaystyle 3^{5}=3\times 3\times 3\times 3\times 3=243\equiv 5\,\mathrm {mod} \,7$ 但是，直接从 $\displaystyle 3^{n}$ 计算 $\displaystyle 3^{n+1}$ 会更快，如下所示 $\displaystyle 3^{1}=3\quad \quad \quad \equiv 3\,\mathrm {mod} \,7$ $\displaystyle 3^{2}=3\times 3=9\equiv 2\,\mathrm {mod} \,7$ $\displaystyle 3^{3}=2\times 3=6\equiv 6\,\mathrm {mod} \,7$ $\displaystyle 3^{4}=6\times 3=18\equiv 4\,\mathrm {mod} \,7$ $\displaystyle 3^{5}=4\times 3=12\equiv 5\,\mathrm {mod} \,7$ $\displaystyle 3^{6}=5\times 3=15\equiv 1\,\mathrm {mod} \,7$ $\displaystyle 3^{7}=1\times 3=3\equiv 3\,\mathrm {mod} \,7$ $\displaystyle 3^{8}=3\times 3=9\equiv 2\,\mathrm {mod} \,7$ 很明显，这个模式是重复的。这是因为 $\displaystyle 3^{6}\equiv 1\,{\bmod {\,}}7$. 即使不做计算，也很清楚这个模式必须在某个地方重复。对于 $\displaystyle 3^{n}\,{\bmod {\,}}7$，最多有 7 种不同的可能数字，所以如果我们计算 $\displaystyle n=1,2,3,4,5,6,7,8$，一定会在里面找到重复的答案。 注意： 这是抽屉原理的应用——鸽子比抽屉多，因此一个抽屉必须包含两只鸽子。如果你感兴趣，请点击鸽子图标，阅读有关抽屉原理的更多信息 鸽子： 3 的幂 $\displaystyle {\bmod {\,}}7$. 抽屉： 七个可能的余数 $\displaystyle {\bmod {\,}}7$. 一旦某个数字重复，从那个数字首次出现的地方开始，后面的序列就必须与之前的序列相同。我们甚至可以看到，我们会在重复第一次发生的地方得到一个 1 然后是一个 3。为什么呢？ 假设我们有一个重复的数字，换句话说 $\displaystyle 3^{a}\equiv 3^{a+b}$，其中 a 和 b 是正数。那么 $\displaystyle 3^{a}\equiv 3^{a}3^{b}$，我们可以将两边都除以 $\displaystyle 3^{a}$，得到 $\displaystyle 1\equiv 3^{b}$，即更早出现的重复。只需要稍微注意一下。在模算术中，并不总是允许除以公因数。我们在这里允许进行除法，因为我们之前使用欧几里德算法确定了对素数进行模运算。我们知道 $\displaystyle 3^{n}\,\mathrm {mod} \,7$ 不为零，因为否则 3 将是 7 的一个因数，而 7 是素数。

关于模运算需要注意的是，我们不能随意地对所有数字进行取模运算。例如，在 $\displaystyle {\bmod {\,}}7$ 的情况下，$\displaystyle 3^{8}$ 中的 $\displaystyle 8$ 的指数不能直接替换为 $\displaystyle 1$，因为 $3^{8}\neq 3^{1}\,{\bmod {7}}$。需要特别注意的是指数。在诸如 $\displaystyle 1000x\,{\bmod {7}}$ 和 $\displaystyle (1000+x)\,{\bmod {7}}$ 的表达式中，将 1000 替换为 $\displaystyle 6x\,{\bmod {7}}$ 和 $\displaystyle (6+x)\,{\bmod {7}}$，甚至 $\displaystyle -x\,{\bmod {7}}$ 和 $\displaystyle (x-1)\,{\bmod {7}}$ 是可以的。

练习：3 的幂 现在轮到你了。执行与示例中相同的操作，但这次针对 $\displaystyle p=11$。

这里 3 没有什么特殊之处。我们可以对其他数字进行相同的练习 $\displaystyle a$，其中 $\displaystyle a=1,2,4,5\,or\,6$。我们可能会更快地达到 $\displaystyle a^{n}\equiv 1$，对于 $\displaystyle a=1$，我们一定会这样，但我们仍然会得到 $\displaystyle a^{(p-1)}\equiv 1\,{\pmod {p}}$。

我们将通过多种方式证明这一点。之所以要费力地证明它，是因为它有助于我们看到证明结果的不同方法。在本例中，它主要是一种展示可以使用不同符号的方式。证明的第三种变体还将介绍乘性函数的概念，这在后面会很重要。