欧拉定理 & 费马小定理

费马小定理

定义

若 为素数，，则 。

另一个形式：对于任意整数 ，有 。

证明

设一个质数为 ，我们取一个不为 倍数的数 。

构造一个序列：，这个序列有着这样一个性质：

证明：

又因为每一个 都是独一无二的，且

得证（每一个 都对应了一个 )

设 , 则

证毕。

也可用归纳法证明：

显然 ，假设 成立，那么通过二项式定理有

因为 对于 成立，在模 意义下 ，那么 ，将 带入得 得证。

欧拉定理

在了解欧拉定理（Euler's theorem）之前，请先了解

欧拉函数。定理内容如下：

定义

若 ，则 。

证明

实际上这个证明过程跟上文费马小定理的证明过程是非常相似的：构造一个与 互质的数列，再进行操作。

设 为模 意义下的一个简化剩余系，则 也为模 意义下的一个简化剩余系。所以 ，可约去 ，即得 。

当 为素数时，由于 ，代入欧拉定理可立即得到费马小定理。

扩展欧拉定理

定义

解释

读者可能对第二行产生疑问，这一行表达的意思是：如果 的话，就不能降幂了。

主要是因为题目中 不会太大，而如果 ，自然复杂度是可以接受的。而如果 的话，复杂度可能就超出预期了，这个时候我们才需要降幂来降低复杂度。

证明

直观理解

需要知道的是，在 的条件下， 的取值范围一定在 ，而 ，那么对于任意一个数 ，那么很容易就能知道它的 后继，在有限的空间内这一定会形成一个循环。

在扩展欧拉定理中，循环分为纯循环和混循环。其中纯循环中不存在节点有两个前驱，而混循环则反之。而 形成的序列可以是一个混循环，那么只需要知道循环节的长度，和前面那一小段未进入循环节的长度，就可以根据这个性质来进行降幂了。

值得注意的是，无论是费马小定理，还是（扩展）欧拉定理，一个很重要的应用就是降幂，从而将不可能的表达式化为可能。

形式证明

证明转载自 synapse7，并进行了一些整理。

1. 命题： 的从 次， 次到 次幂模 构成的序列中，存在 和 ，使得前 个数（即从 到 ) 互不相同，从第 个数开始，每 个数就循环一次。

   证明：

   • 由鸽巢定理易证。

     我们把 称为 幂次模 的循环起始点， 称为循环长度。（注意： 可以为 ）

     用公式表述为：

2. 命题： 为素数的情况，该式成立。

   证明：

   • 若模 不能被 整除，而因为 是一个素数，那么 成立，根据欧拉定理，容易证明该式成立。

   • 若模 能被 整除，那么存在 和 使得 ，且 成立。所以根据欧拉定理有 。

     又由于 ，所以根据欧拉函数的求值规则，容易得到：，即我们有：。

     所以 ，即 ，两边同时乘以 ，得 （因为 ）

     所以对于 中素因子 的次数 满足：。我们可以简单变换形式，得到 推论：

     又由于 ，所以 （tips： 是素数，最小是 ，而 ）。

     所以因为 ，故有：

     所以

     即 。

3. 命题： 为素数的幂的情况，该式成立。

   证明：

   • 不妨令 ，是否依然有 ？

     答案是肯定的，由命题 1 可知存在 使得 ，所以 ，所以令 时，我们能有 。

     此时有关系： 且 ，且 ，由 与 的关系，依然可以得到 。

4. 合数： 为合数的情况，该式成立。

   证明：

   • 只证 拆成两个素数的幂的情况，大于两个的用数学归纳法可证。

     设 ，其中 ，而 的循环长度为 ；

     则 ，由于 ，那么 ，所以 ，；

     由 与 的关系，依然可以得到 。

     证毕。

习题

1. SPOJ #4141 "Euler Totient Function"[Difficulty: CakeWalk]
2. UVA #10179 "Irreducible Basic Fractions"[Difficulty: Easy]
3. UVA #10299 "Relatives"[Difficulty: Easy]
4. UVA #11327 "Enumerating Rational Numbers"[Difficulty: Medium]
5. TIMUS #1673 "Admission to Exam"[Difficulty: High]