欧拉定理 & 费马小定理

费马小定理

定义

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

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

证明

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

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

$$\prod _{i=1}^{p-1}{A}_i\equiv \prod _{i=1}^{p-1}(A_i\times a)(\mathrm{mod}p)$$

证明：

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

又因为每一个 $A_i\times a(\mathrm{mod}p)$ 都是独一无二的，且 $A_i\times a(\mathrm{mod}p)<p$

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

设 $f=(p-1)!$, 则 $f\equiv a\times A_1\times a\times A_2\times a\times A_3\cdots \times A_{p-1}(\mathrm{mod}p)$

$$\begin{array}{rl}{a}^{p-1}\times f& \equiv f(\mathrm{mod}p)\\ a^{p-1}& \equiv 1(\mathrm{mod}p)\end{array}$$

证毕。

也可用归纳法证明：

显然 $1^p\equiv 1(\mathrm{mod}p)$，假设 $a^p\equiv a(\mathrm{mod}p)$ 成立，那么通过二项式定理有

$$(a+1{)}^p=a^p+(\genfrac{}{}{0ex}{}{p}{1})a^{p-1}+(\genfrac{}{}{0ex}{}{p}{2})a^{p-2}+\cdots +(\genfrac{}{}{0ex}{}{p}{p-1})a+1$$

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

欧拉定理

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

定义

若 $gcd(a,m)=1$，则 $a^{\phi (m)}\equiv 1(\mathrm{mod}m)$。

证明

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

设 $r_1,r_2,\cdots ,r_{\phi (m)}$ 为模 $m$ 意义下的一个简化剩余系，则 $a{r}_1,a{r}_2,\cdots ,a{r}_{\phi (m)}$ 也为模 $m$ 意义下的一个简化剩余系。所以 $r_1{r}_2\cdots r_{\phi (m)}\equiv a{r}_1\cdot a{r}_2\cdots a{r}_{\phi (m)}\equiv a^{\phi (m)}{r}_1{r}_2\cdots r_{\phi (m)}(\mathrm{mod}m)$，可约去 $r_1{r}_2\cdots r_{\phi (m)}$，即得 $a^{\phi (m)}\equiv 1(\mathrm{mod}m)$。

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

扩展欧拉定理

定义

$$a^b\equiv \{\begin{array}{ll}{a}^{bmod\phi (m)},& gcd(a,m)=1,\\ a^b,& gcd(a,m)\ne 1,b<\phi (m),\\ a^{(bmod\phi (m))+\phi (m)},& gcd(a,m)\ne 1,b\ge \phi (m).\end{array}(\mathrm{mod}m)$$

解释

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

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

证明

直观理解

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

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

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

形式证明

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

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

   证明：

   • 由鸽巢定理易证。

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

     用公式表述为：$\mathrm{\forall }i\ge r,a^i\equiv a^{i+s}(\mathrm{mod}m)$

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

   证明：

   • 若模 $m$ 不能被 $a$ 整除，而因为 $a$ 是一个素数，那么 $gcd(a,m)=1$ 成立，根据欧拉定理，容易证明该式成立。

   • 若模 $m$ 能被 $a$ 整除，那么存在 $r$ 和 $m^{\prime }$ 使得 $m=a^r{m}^{\prime }$，且 $gcd(a,m^{\prime })=1$ 成立。所以根据欧拉定理有 $a^{\phi (m^{\prime })}\equiv 1(\mathrm{mod}{m}^{\prime })$。

     又由于 $gcd(a^r,m^{\prime })=1$，所以根据欧拉函数的求值规则，容易得到：$\phi (m)=\phi (m^{\prime })\times (a-1)a^{r-1}$，即我们有：$\phi (m^{\prime })\mid \phi (m)$。

     所以 $a^{\phi (m^{\prime })}\equiv 1(\mathrm{mod}{m}^{\prime }),\phi (m^{\prime })\mid \phi (m)⟹a^{\phi (m)}\equiv 1(\mathrm{mod}{m}^{\prime })$，即 $a^{\phi (m)}=k{m}^{\prime }+1$，两边同时乘以 $a^r$，得 $a^{r+\phi (m)}=km+a^r$（因为 $m=a^r{m}^{\prime }$）

     所以对于 $m$ 中素因子 $a$ 的次数 $r$ 满足：$a^r\equiv a^{r+\phi (m)}(\mathrm{mod}m)$。我们可以简单变换形式，得到 推论：

     $$b>r⟹a^b\equiv a^{r+((b-r)mod\phi (m))}(\mathrm{mod}m)$$

     又由于 $m=a^r{m}^{\prime }$，所以 $\phi (m)=\phi (a^r)\phi (m^{\prime })\ge \phi (a^r)=a^{r-1}(a-1)\ge r$（tips：$a$ 是素数，最小是 $2$，而 $r\ge 1$）。

     所以因为 $\phi (m)\ge r$，故有：

     $$a^r\equiv a^{r+\phi (m)}\equiv a^{rmod\phi (m)+\phi (m)}(\mathrm{mod}m)$$

     所以

     $$\begin{array}{rl}{a}^b& \equiv a^{r+(b-r)mod\phi (m)}\\ & \equiv a^{rmod\phi (m)+\phi (m)+(b-r)mod\phi (m)}\\ & \equiv a^{\phi (m)+bmod\phi (m)}\end{array}(\mathrm{mod}m)$$

     即 $a^b\equiv a^{bmod\phi (m)+\phi (m)}(\mathrm{mod}m)$。

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

   证明：

   • 不妨令 $a=p^k$，是否依然有 $\mathrm{\forall }r,a^r\equiv a^{r+\phi (m)}(\mathrm{mod}m)$？

     答案是肯定的，由命题 1 可知存在 $s$ 使得 $a^s\equiv 1(\mathrm{mod}m)$，所以 $p^{\mathrm{lcm}(s,k)}\equiv 1(\mathrm{mod}m)$，所以令 $s^{\prime }=\frac{s}{gcd(s,k)}$ 时，我们能有 $p^{s^{\prime }k}\equiv 1(\mathrm{mod}m)$。

     此时有关系：$s^{\prime }\mid s$ 且 $s\mid \phi (m)$，且 $r^{\prime }=\lceil \frac{r}{k}\rceil \le r\le \phi (m)$，由 $r^{\prime },s^{\prime }$ 与 $\phi (m)$ 的关系，依然可以得到 $a^b\equiv a^{bmod\phi (m)+\phi (m)}(\mathrm{mod}m)$。

4. 命题：$a$ 为合数的情况，该式成立。

   证明：

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

     设 $a=a_1{a}_2$，其中 $a_i=p_i^{k_i}$，而 $a_i$ 的循环长度为 $s_i$；

     则 $s\mid \mathrm{lcm}(s_1,s_2)$，由于 $s_1\mid \phi (m),s_2\mid \phi (m)$，那么 $\mathrm{lcm}(s_1,s_2)\mid \phi (m)$，所以 $s\mid \phi (m)$，$r=max(\lceil \frac{r_i}{k_i}\rceil )\le max(r_i)\le \phi (m)$；

     由 $r,s$ 与 $\phi (m)$ 的关系，依然可以得到 $a^b\equiv a^{bmod\phi (m)+\phi (m)}(\mathrm{mod}m)$。

     证毕。

习题

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]

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