欧拉定理 & 费马小定理

费马小定理

定义

若为素数， $\gcd(a, p) = 1$ ，则 $a^{p - 1} \equiv 1 \pmod{p}$ 。

另一个形式：对于任意整数，有 $a^p \equiv a \pmod{p}$ 。

证明

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

构造一个序列： $A=\{1,2,3\dots,p-1\}$ ，这个序列有着这样一个性质：

\prod_{i=1}^{n}\space A_i\equiv\prod_{i=1}^{n} (A_i\times a) \pmod p

证明：

\because (A_i,p)=1,(A_i\times a,p)=1

又因为每一个 $A_i\times a \pmod p$ 都是独一无二的，且 $A_i\times a \pmod p < p$

得证（每一个 $A_i\times a$ 都对应了一个 )

设 , 则 $f\equiv a\times A_1\times a\times A_2\times a \times A_3 \dots \times A_{p-1} \pmod p$

\begin{aligned} a^{p-1}\times f &\equiv f \pmod p \\ a^{p-1} &\equiv 1 \pmod p \end{aligned}

证毕。

也可用归纳法证明：

显然 $1^p\equiv 1\pmod p$ ，假设 $a^p\equiv a\pmod p$ 成立，那么通过二项式定理有

(a+1)^p=a^p+\binom{p}{1}a^{p-1}+\binom{p}{2}a^{p-2}+\cdots +\binom{p}{p-1}a+1

因为 $\binom{p}{k}=\frac{p(p-1)\cdots (p-k+1)}{k!}$ 对于 $1\leq k\leq p-1$ 成立，在模意义下 $\binom{p}{1}\equiv \binom{p}{2}\equiv \cdots \equiv \binom{p}{p-1}\equiv 0\pmod p$ ，那么 $(a+1)^p \equiv a^p +1\pmod p$ ，将 $a^p\equiv a\pmod p$ 带入得 $(a+1)^p\equiv a+1\pmod p$ 得证。

欧拉定理

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

定义

若 $\gcd(a, m) = 1$ ，则 $a^{\varphi(m)} \equiv 1 \pmod{m}$ 。

证明

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

设 $r_1, r_2, \cdots, r_{\varphi(m)}$ 为模意义下的一个简化剩余系，则 $ar_1, ar_2, \cdots, ar_{\varphi(m)}$ 也为模意义下的一个简化剩余系。所以 $r_1r_2 \cdots r_{\varphi(m)} \equiv ar_1 \cdot ar_2 \cdots ar_{\varphi(m)} \equiv a^{\varphi(m)}r_1r_2 \cdots r_{\varphi(m)} \pmod{m}$ ，可约去 $r_1r_2 \cdots r_{\varphi(m)}$ ，即得 $a^{\varphi(m)} \equiv 1 \pmod{m}$ 。

当为素数时，由于 $\varphi(m) = m - 1$ ，代入欧拉定理可立即得到费马小定理。

扩展欧拉定理

定义

a^b \equiv \begin{cases} a^{b \bmod \varphi(m)}, &\gcd(a,m) = 1, \\ a^b, &\gcd(a,m)\ne 1, b < \varphi(m), \\ a^{(b \bmod \varphi(m)) + \varphi(m)}, &\gcd(a,m)\ne 1, b \ge \varphi(m). \end{cases} \pmod m

解释

读者可能对第二行产生疑问，这一行表达的意思是：如果 $b < \varphi(m)$ 的话，就不能降幂了。

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

证明

直观理解

fermat1

需要知道的是，在 $\pmod m$ 的条件下， $a^b \bmod m$ 的取值范围一定在，而 $a^i \bmod m = (a^{i-1} \bmod m) \times a \bmod m$ ，那么对于任意一个数，那么很容易就能知道它的后继，在有限的空间内这一定会形成一个循环。

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

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

形式证明

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

命题：的从次，次到次幂模构成的序列中，存在和，使得前个数（即从 $a^0 \bmod m$ 到 $a^{r-1} \bmod m$ ) 互不相同，从第个数开始，每个数就循环一次。

证明：
- 由鸽巢定理易证。
  
  我们把称为幂次模的循环起始点，称为循环长度。（注意：可以为）
  
  用公式表述为： $\forall i \ge r, a^i \equiv a^{i+s} \pmod{m}$
命题：为素数的情况，该式成立。

证明：
- 若模不能被整除，而因为是一个素数，那么 $\gcd(a, m) = 1$ 成立，根据欧拉定理，容易证明该式成立。
- 若模能被整除，那么存在和使得，且 $\gcd(a, m')=1$ 成立。所以根据欧拉定理有 $a^{\varphi(m')} \equiv 1 \pmod{m'}$ 。
  
  又由于 $\gcd(a^r, m')=1$ ，所以根据欧拉函数的求值规则，容易得到： $\varphi(m) = \varphi(m') \times (a-1)a^{r-1}$ ，即我们有： $\varphi(m') \mid \varphi(m)$ 。
  
  所以 $a^{\varphi(m')} \equiv 1 \pmod {m'}, \varphi(m') \mid \varphi(m) \Rightarrow a^{\varphi(m)} \equiv 1 \pmod {m'}$ ，即 $a^{\varphi(m)}=km'+1$ ，两边同时乘以，得 $a^{r+\varphi(m)} = km + a^r$ （因为）
  
  所以对于中素因子的次数满足： $a^r \equiv a^{r+\varphi(m)} \pmod m$ 。我们可以简单变换形式，得到推论：
  $b > r \implies a^b \equiv a^{r + ((b-r) \bmod \varphi(m))} \pmod {m}$
  又由于，所以 $\varphi(m) = \varphi(a^r) \varphi(m') \ge \varphi(a^r)=a^{r-1}(a-1) \ge r$ （tips：是素数，最小是，而 $r \ge 1$ ）。
  
  所以因为 $\varphi(m) \ge r$ ，故有：
  $a^r \equiv a^{r+\varphi(m)} \equiv a^{r \bmod \varphi(m)+\varphi(m)} \pmod m$
  所以
  $\begin{aligned} a^b &\equiv a^{r+(b-r) \bmod \varphi(m)} \\ &\equiv a^{r \bmod \varphi(m) + \varphi(m) + (b-r) \bmod \varphi(m)} \\ &\equiv a^{\varphi(m) + b \bmod \varphi(m)} \end{aligned} \pmod m$
  即 $a^b\equiv a^{b \bmod \varphi(m)+\varphi(m)}\pmod m$ 。
命题：为素数的幂的情况，该式成立。

证明：
- 不妨令，是否依然有 $\forall r, a^{r} \equiv a^{r+\varphi(m)} \pmod m$ ？
  
  答案是肯定的，由命题 1 可知存在使得 $a^s\equiv 1 \pmod m$ ，所以 $p^{\mathrm{lcm}(s,k)} \equiv 1 \pmod {m}$ ，所以令 $s'=\frac{s}{\gcd(s,k)}$ 时，我们能有 $p^{s'k} \equiv 1 \pmod {m}$ 。
  
  此时有关系： $s' \mid s$ 且 $s \mid \varphi(m)$ ，且 $r'= \lceil \frac{r}{k}\rceil \le r \le \varphi(m)$ ，由与 $\varphi(m)$ 的关系，依然可以得到 $a^b\equiv a^{b \bmod \varphi(m)+\varphi(m)}\pmod m$ 。
合数：为合数的情况，该式成立。

证明：
- 只证拆成两个素数的幂的情况，大于两个的用数学归纳法可证。
  
  设，其中 $a_i=p_i^{k_i}$ ，而的循环长度为；
  
  则 $s \mid \operatorname{lcm}(s_1,s_2)$ ，由于 $s_1 \mid \varphi(m),s_2 \mid \varphi(m)$ ，那么 $\operatorname{lcm}(s_1,s_2) \mid \varphi(m)$ ，所以 $s \mid \varphi(m)$ ， $r=\max(\lceil \frac{r_i}{k_i} \rceil) \le \max(r_i) \le \varphi(m)$ ；
  
  由与 $\varphi(m)$ 的关系，依然可以得到 $a^b \equiv a^{b \bmod \varphi(m)+\varphi(m)}\pmod m$ 。
  
  证毕。

习题

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