

欧拉定理 & 费马小定理

费马小定理

定义

若为素数，，则。

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

证明

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

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

证明：

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

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

设 , 则

证毕。

也可用归纳法证明：

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

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

欧拉定理

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

定义

若，则。

证明

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

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

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

扩展欧拉定理

定义

解释

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

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

证明

直观理解

fermat1

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

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

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

形式证明

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

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

证明：
- 由鸽巢定理易证。
  
  我们把称为幂次模的循环起始点，称为循环长度。（注意：可以为）
  
  用公式表述为：
命题：为素数的情况，该式成立。

证明：
- 若模不能被整除，而因为是一个素数，那么成立，根据欧拉定理，容易证明该式成立。
- 若模能被整除，那么存在和使得，且成立。所以根据欧拉定理有。
  
  又由于，所以根据欧拉函数的求值规则，容易得到：，即我们有：。
  
  所以，即，两边同时乘以，得（因为）
  
  所以对于中素因子的次数满足：。我们可以简单变换形式，得到推论：
  
  又由于，所以（tips：是素数，最小是，而）。
  
  所以因为，故有：
  
  所以
  
  即。
命题：为素数的幂的情况，该式成立。

证明：
- 不妨令，是否依然有？
  
  答案是肯定的，由命题 1 可知存在使得，所以，所以令时，我们能有。
  
  此时有关系：且，且，由与的关系，依然可以得到。
合数：为合数的情况，该式成立。

证明：
- 只证拆成两个素数的幂的情况，大于两个的用数学归纳法可证。
  
  设，其中，而的循环长度为；
  
  则，由于，那么，所以，；
  
  由与的关系，依然可以得到。
  
  证毕。

习题

本页面最近更新：2022/9/24 12:14:35，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Enter-tainer, PeterlitsZo, Tiphereth-A, Acfboy, Dev-XYS, Great-designer, guodong2005, H-J-Granger, hjsjhn, hly1204, iamtwz, Ir1d, MegaOwIer, Menci, sshwy, stevebraveman, tth37, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用