若 为素数，，则 。

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

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

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

证明：

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

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

设 , 则

证毕。

也可用归纳法证明：

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

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

在了解欧拉定理（Euler's theorem）之前，请先了解 欧拉函数。定理内容如下：

若 ，则 。

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

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

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

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

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

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

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

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

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

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

证明：

由鸽巢定理易证。

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

用公式表述为：

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

证明：

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

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

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

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

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

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

所以因为 ，故有：

所以

即 。

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

证明：

不妨令 ，是否依然有 ？

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

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

命题： 为合数的情况，该式成立。

证明：

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

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

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

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

证毕。