1. 从一道“简单”的编程题说起为什么我们需要欧拉定理如果你刷过一些算法题尤其是涉及大数取模、幂运算的题目大概率见过类似这样的描述“计算a^b mod m的值其中a, b, m都是可能高达10^18级别的整数”。新手的第一反应可能是这还不简单写个循环每次乘一下再取模不就行了但当你尝试用for (long long i 0; i b; i) ans (ans * a) % m;去实现时程序会立刻给你一个无情的超时TLE——因为b可以大到10^18这个循环要跑一万亿次显然不现实。这时你会学到第一个关键技巧快速幂算法。它的核心是利用二进制和倍增思想将时间复杂度从O(b)降到了O(log b)。比如计算3^13 mod 713的二进制是1101那么3^13 3^(8) * 3^(4) * 3^(1)我们只需要通过反复平方3^1, 3^2, 3^4, 3^8...就能快速组合出结果。这是解决大指数取模问题的基石也是理解后续内容的前提。然而问题会变得更“狡猾”。如果题目变成“计算a^b mod m但b本身也是一个极其巨大的数甚至可能以字符串或指数形式给出比如b 10^100000”。这时连快速幂中O(log b)的复杂度都不可接受了因为log b仍然和b的位数成正比对于10^100000这样的数其位数是10万级循环10万次在竞赛时限内也常常是危险的。更棘手的情况出现在需要计算“指数塔”或者模数m不是质数的时候。例如计算a^(b^c) mod m或者当a和m不互质时简单的快速幂可能无法直接应用。这时我们就需要请出数论中的两位“重量级选手”欧拉定理和它的特殊情形费马小定理。它们提供的核心价值在于能够将巨大的指数b进行“缩小”或“化简”使其变得可计算。理解它们不仅是解决特定难题的钥匙更是深入理解模运算世界规律的必经之路。本文就将围绕这两个定理的结论、证明思路、以及它们在算法竞赛和实际应用中的各种“神奇”用法进行一次深入的杂谈。2. 定理本身定义、证明与直观理解在进入应用之前我们必须先扎实地理解定理本身。很多人只是死记硬背公式遇到复杂问题就不知道如何变通。让我们从最基础的开始。2.1 费马小定理质数模数下的简化器定理陈述若p是一个质数且整数a不是p的倍数即gcd(a, p) 1则有a^(p-1) ≡ 1 (mod p)另一种常用等价形式是a^p ≡ a (mod p)这个形式对任意整数a都成立当a是p的倍数时两边模p都为0。证明思路简化版 考虑集合A {1, 2, 3, ..., p-1}这是模p的一个最小正剩余系。由于a与p互质集合B {a*1 mod p, a*2 mod p, ..., a*(p-1) mod p}中的每个元素也恰好是1到p-1这p-1个数的一个排列不会重复且没有0。因此两个集合所有元素的乘积在模p下是相等的(a*1) * (a*2) * ... * (a*(p-1)) ≡ 1 * 2 * ... * (p-1) (mod p)将左边的a提取出来共有p-1个即a^(p-1) * (p-1)! ≡ (p-1)! (mod p)。 由于(p-1)!与质数p互质因为p是质数(p-1)!不含因子p我们可以两边同时“除以”(p-1)!在模运算中乘以它的模逆元最终得到a^(p-1) ≡ 1 (mod p)。直观理解 你可以把模p的乘法运算想象成一个只有p-1个有效数字1到p-1的循环系统。用a去乘这个系统中的每一个数相当于对这个系统做了一次“洗牌”但洗牌后得到的还是原来那套牌。连续做p-1次这样的“洗牌”整个系统就回到了最初的状态这个“回到原点”的操作在乘法上体现为乘以a^(p-1)等于乘以1。这就是a^(p-1) ≡ 1 (mod p)的直观含义。2.2 欧拉定理费马小定理的通用升级版费马小定理要求模数p必须是质数这限制太大了。欧拉定理将其推广到了任意正整数模数m。定理陈述若整数a与正整数m互质即gcd(a, m) 1则有a^(φ(m)) ≡ 1 (mod m)其中φ(m)是欧拉函数表示小于等于m的正整数中与m互质的数的个数。证明思路与费马小定理同源 设所有小于m且与m互质的正整数构成集合R {r1, r2, ..., r_φ(m)}这个集合称为模m的一个简化剩余系。由于a与m互质那么集合S {a*r1 mod m, a*r2 mod m, ..., a*r_φ(m) mod m}中的每一个数仍然与m互质并且它们彼此模m不同余。因此S实际上也是模m的一个简化剩余系只是顺序可能被打乱。于是两个集合所有元素的乘积模m同余(a*r1) * (a*r2) * ... * (a*r_φ(m)) ≡ r1 * r2 * ... * r_φ(m) (mod m)提取φ(m)个a得到a^(φ(m)) * (r1*r2*...*r_φ(m)) ≡ r1*r2*...*r_φ(m) (mod m)。 由于每个r_i都与m互质它们的乘积也与m互质因此该乘积在模m下有乘法逆元。两边同时乘以这个逆元就得到了a^(φ(m)) ≡ 1 (mod m)。直观理解与进阶思考 欧拉定理是费马小定理的直接推广。当m取质数p时φ(p) p-1欧拉定理就退化成了费马小定理。这个定理揭示了模m乘法群由所有与m互质的数构成的一个核心性质这个群的阶即元素个数是φ(m)任何群中的元素a的φ(m)次方必然是单位元1。这是抽象代数中拉格朗日定理的一个特例也为RSA公钥加密算法提供了理论基础。注意定理成立的前提gcd(a, m) 1至关重要如果a和m不互质结论一般不成立。例如取a2, m4φ(4)2但2^2 4 ≡ 0 (mod 4)而不是1。2.3 欧拉函数 φ(m) 的计算要使用欧拉定理我们必须能快速计算φ(m)。它有以下几个关键性质积性函数如果gcd(m, n) 1那么φ(m*n) φ(m) * φ(n)。质数幂次对于质数p和正整数kφ(p^k) p^k - p^(k-1) p^(k-1) * (p-1)。因为从1到p^k的数中只有p的倍数共p^(k-1)个不与p^k互质。通用公式根据算术基本定理将m分解为质因数乘积m p1^a1 * p2^a2 * ... * pr^ar则φ(m) m * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pr)计算示例 计算φ(100)。100 2^2 * 5^2。根据公式φ(100) 100 * (1 - 1/2) * (1 - 1/5) 100 * (1/2) * (4/5) 40。 这意味着在1到100中有40个数与100互质。在算法实现中我们通常结合质因数分解来计算φ(m)。下面是一个C示例函数// 计算欧拉函数 phi(n) long long euler_phi(long long n) { long long ans n; long long temp n; for (long long i 2; i * i temp; i) { if (temp % i 0) { ans ans / i * (i - 1); // 等价于 ans * (1 - 1/i) while (temp % i 0) temp / i; } } if (temp 1) { // 处理剩余的大质因数 ans ans / temp * (temp - 1); } return ans; }3. 核心应用一大指数取模的降维打击这是欧拉定理和费马小定理最直接、最经典的应用场景。我们回到开头提到的问题。3.1 当指数 b 极大时使用欧拉定理降幂问题原型计算a^b mod mb是一个大整数例如有上万位。解法核心如果gcd(a, m) 1根据欧拉定理a^(φ(m)) ≡ 1 (mod m)。那么对于指数b我们可以将其除以φ(m)写成b k * φ(m) r其中0 r φ(m)。于是a^b ≡ a^(k*φ(m) r) ≡ (a^(φ(m)))^k * a^r ≡ 1^k * a^r ≡ a^r (mod m)这样一来我们只需要计算a^r mod m而r b mod φ(m)是一个小于φ(m)的数通常变得可管理了。计算b mod φ(m)需要对大数b进行取模运算这可以通过逐位处理字符串来实现复杂度是O(len(b))其中len(b)是b的位数。算法步骤计算φ_m φ(m)。计算r b mod φ_m注意b可能是字符串。使用快速幂计算a^r mod m。C代码片段假设b以字符串形式给出#include iostream #include string using namespace std; // 快速幂取模 long long pow_mod(long long a, long long b, long long mod) { long long res 1; a % mod; while (b 0) { if (b 1) res (res * a) % mod; a (a * a) % mod; b 1; } return res; } // 大数取模字符串形式的大数b对mod取模 long long big_mod(const string b, long long mod) { long long res 0; for (char digit : b) { res (res * 10 (digit - 0)) % mod; } return res; } // 使用欧拉定理降幂计算 a^b mod m (gcd(a, m) 1) long long huge_pow_mod(long long a, const string b, long long m) { long long phi_m euler_phi(m); // 使用前面定义的函数 long long r big_mod(b, phi_m); return pow_mod(a, r, m); }3.2 当 a 与 m 不互质时扩展欧拉定理现实问题往往更复杂。如果gcd(a, m) ! 1欧拉定理不能直接使用。这时需要扩展欧拉定理也称欧拉降幂公式。定理陈述对于任意a, b, mm 0有a^b ≡ a^(b mod φ(m) φ(m)) (mod m)当且仅当b φ(m)。这个“当且仅当b φ(m)”是关键。它意味着如果b φ(m)我们老老实实用快速幂计算a^b mod m。如果b φ(m)我们就可以将指数b替换为b mod φ(m) φ(m)然后再用快速幂计算。为什么这样可行一个非严格的解释是当b足够大时a^b中蕴含的m的因子来自a和m的公因子的幂次已经高到足以“支配”模运算的结果而剩余部分则遵循与m互质的那部分的周期规律即φ(m)。加上φ(m)这个偏移量正是为了确保指数在化简后仍然足够大以满足这种“支配”关系。通用降幂计算步骤计算φ_m φ(m)。判断指数b可能是大数与φ_m的大小关系。如果b可以表示为普通整数且b φ_m直接计算pow_mod(a, b, m)。如果b是大数字符串我们需要在计算b mod φ_m的同时判断b是否 φ_m。一个巧妙的方法是在逐位计算b mod φ_m的过程中用一个布尔变量flag来记录当前已处理的部分是否已经大于等于φ_m。由于φ_m通常不会太大除非m本身是巨大质数的乘积我们可以直接比较。根据判断结果选择指数若b φ_m则计算r big_mod(b, φ_m) φ_m然后计算pow_mod(a, r, m)。若b φ_m则直接计算pow_mod(a, b, m)此时b是普通整数。C代码片段处理不互质情况// 扩展欧拉定理降幂b为字符串 long long ex_euler_pow_mod(long long a, string b, long long m) { long long phi_m euler_phi(m); long long r 0; bool flag false; // 标记 b 是否 phi_m // 处理大数b并判断大小 for (char digit : b) { r r * 10 (digit - 0); if (r phi_m) { flag true; r % phi_m; } } if (flag) { // b phi_m return pow_mod(a, r phi_m, m); } else { // b phi_m, 此时r就是b本身 return pow_mod(a, r, m); } }3.3 实战例题解析题目计算2^(10^100) mod 1000000007即mod 1e97。分析模数m 1000000007它是一个质数因此φ(m) m - 1 1000000006。底数a 2与质数m互质满足欧拉定理条件。指数b 10^100一个巨大的数显然b φ(m)。应用扩展欧拉定理因为b φ(m)我们需要计算b mod φ(m)。10^100 mod 1000000006可以通过快速幂或循环计算吗不行因为100这个指数还算小但更通用的方法是利用模运算性质(a * b) mod m ((a mod m) * (b mod m)) mod m。计算10^100 mod 1000000006可以用快速幂模数是1000000006。设r 10^100 mod 1000000006则最终答案为pow_mod(2, r 1000000006, 1000000007)。计算r因为100不大我们可以用快速幂计算pow_mod(10, 100, 1000000006)。 最终我们通过两次快速幂一次算r一次算最终结果解决了这个看似天文数字级别的问题。这就是降幂的威力。4. 核心应用二乘法逆元的求解与意义在模运算中我们没有直接的除法。但“除以一个数”在模意义下等价于“乘以这个数的乘法逆元”。数a在模m下的乘法逆元x满足a * x ≡ 1 (mod m)。逆元存在的前提是gcd(a, m) 1。4.1 用费马小定理求逆元模数为质数当模数m为质数p时根据费马小定理对于任意不是p倍数的a有a^(p-1) ≡ 1 (mod p)。这可以改写为a * a^(p-2) ≡ 1 (mod p)对比逆元定义a * x ≡ 1 (mod p)我们立刻得到x ≡ a^(p-2) (mod p)。 因此在模质数p下a的逆元就是a^(p-2) mod p。计算方法使用快速幂计算pow_mod(a, p-2, p)。这是竞赛中最常用的求逆元方法因为模数1e97、998244353等都是质数。示例求3在模7下的逆元。 计算3^(7-2) 3^5 243。243 mod 7 5因为7*34238,243-2385。验证3 * 5 15 ≡ 1 (mod 7)。正确。4.2 用欧拉定理求逆元模数为任意与a互质的数当模数m不是质数但gcd(a, m) 1时根据欧拉定理a^(φ(m)) ≡ 1 (mod m)可得a * a^(φ(m)-1) ≡ 1 (mod m)所以a在模m下的逆元为a^(φ(m)-1) mod m。计算方法先计算φ(m)再用快速幂计算pow_mod(a, φ(m)-1, m)。对比与选择扩展欧几里得算法是求解ax my 1的通用方法可以直接解出逆元x时间复杂度O(log min(a, m))且不要求m是质数只要求gcd(a, m)1。通常比基于欧拉定理的快速幂方法更快、更稳定因为计算φ(m)本身需要O(√m)的质因数分解时间。费马小定理/欧拉定理快速幂法在已知φ(m)或m为质数时代码非常简洁。对于固定模数如常见质数模预处理后求逆元很快。线性递推求逆元当需要求1到n所有数模质数p的逆元时有O(n)的递推公式效率最高。实战建议在算法竞赛中如果模数是固定的质数如1e97优先使用费马小定理求逆元因为p-2是常数。如果模数非质数或需要单个逆元使用扩展欧几里得算法是更通用的选择。欧拉定理求逆元在特定场景如φ(m)很容易计算下可作为备选。5. 核心应用三在密码学与循环周期问题中的身影5.1 RSA加密算法的理论基础RSA公钥加密算法是现代密码学的基石之一其安全性基于大数分解的困难性。欧拉定理在其中扮演了核心角色。RSA密钥生成简述选择两个大质数p和q计算n p * q。n的长度比特数决定了安全性。计算欧拉函数φ(n) (p-1)*(q-1)。选择一个整数e满足1 e φ(n)且gcd(e, φ(n)) 1。e作为公钥的一部分。计算e对于模φ(n)的乘法逆元d即满足e * d ≡ 1 (mod φ(n))。d作为私钥。加密与解密加密对于明文M转换为整数且M n计算密文C M^e mod n。解密对于密文C计算明文M C^d mod n。为什么解密是正确的我们需要证明M ≡ M (mod n)。 证明的关键步骤依赖于欧拉定理。由于e * d ≡ 1 (mod φ(n))可写为e*d k*φ(n) 1。 解密过程C^d ≡ (M^e)^d ≡ M^(e*d) ≡ M^(k*φ(n) 1) (mod n)。 现在分两种情况如果gcd(M, n) 1由欧拉定理M^(φ(n)) ≡ 1 (mod n)所以M^(k*φ(n) 1) ≡ M (mod n)。如果gcd(M, n) ! 1由于np*qM必然是p或q的倍数因为M n。假设M是p的倍数那么M ≡ 0 (mod p)显然有M^(e*d) ≡ 0 ≡ M (mod p)。另一方面因为M不是q的倍数否则M是n的倍数但M n由费马小定理M^(q-1) ≡ 1 (mod q)。因为φ(n) (p-1)(q-1)所以M^(k*φ(n)) ≡ 1 (mod q)。于是M^(e*d) ≡ M (mod q)。根据中国剩余定理由M^(e*d) ≡ M (mod p)和M^(e*d) ≡ M (mod q)可以推出M^(e*d) ≡ M (mod n)。 综上解密总能恢复明文。这个证明完美展示了费马小定理和欧拉定理如何共同支撑起RSA算法的正确性。5.2 寻找模幂运算的循环节在计算a^k mod m的序列时随着k增加结果会出现循环。欧拉定理给出了循环节长度的上限。结论在a与m互质的前提下由欧拉定理a^(φ(m)) ≡ 1 (mod m)可知序列a^k mod m从k1开始其循环节的长度T一定是φ(m)的约数。这个最小的正周期T称为a模m的阶Order。应用场景在一些数学问题或构造性题目中需要寻找最小的正整数k使得a^k ≡ 1 (mod m)。我们可以先求出φ(m)然后枚举φ(m)的所有正约数d检查a^d ≡ 1 (mod m)是否成立找到满足条件的最小d即可。示例求最小的正整数k使得2^k ≡ 1 (mod 7)。φ(7)6。6的约数有1,2,3,6。2^1 mod 7 22^2 mod 7 42^3 mod 7 1因此最小的k是3。注意3确实是6的约数。这个性质在数论函数、原根以及一些周期性问题中非常有用。6. 进阶矩阵快速幂与线性递推快速幂的思想并不局限于数的乘法任何满足结合律的运算都可以应用比如矩阵乘法。这就引出了矩阵快速幂它是解决线性递推问题的利器。6.1 从斐波那契数列说起斐波那契数列定义为F(0)0, F(1)1, F(n)F(n-1)F(n-2) (n2)。求F(n) mod mn可以很大如10^18。直接递推或递归是O(n)太慢。我们可以将其转化为矩阵乘法形式[ F(n) ] [1 1] * [ F(n-1) ] [ F(n-1) ] [1 0] [ F(n-2) ]更一般地[ F(n) ] [1 1]^(n-1) * [ F(1) ] [ F(n-1) ] [1 0] [ F(0) ]设矩阵M [ [1,1], [1,0] ]初始向量V [F(1), F(0)]^T [1, 0]^T。 则[F(n), F(n-1)]^T M^(n-1) * V。计算M^(n-1)可以用矩阵快速幂在O(log n)时间内完成再乘以向量V得到结果。6.2 矩阵快速幂与欧拉定理的结合当问题涉及到对矩阵的幂取模并且指数n极大时我们同样可以考虑降幂。但这里需要注意欧拉定理对于矩阵并不直接成立。欧拉定理a^(φ(m)) ≡ 1 (mod m)要求a是与m互质的整数。对于矩阵M我们关心的是M^n mod m其中每个矩阵元素都是整数模m运算作用于每个元素。对于矩阵没有直接的“互质”概念和通用的欧拉定理。但是在一些特殊情况下特别是当矩阵M与模数m满足某些条件时其幂运算可能存在循环节循环节长度可能与φ(m)或其倍数有关但这需要针对具体矩阵进行分析通常依赖于矩阵的特征多项式、最小多项式等概念并利用凯莱-哈密顿定理矩阵满足其自身的特征方程。一个实用的竞赛思路在算法竞赛中如果遇到矩阵幂的指数n极大如字符串给出并且模数m较小比如m 10^5一个常见技巧是暴力寻找循环节。因为矩阵的状态是有限的矩阵元素模m后可能的状态数是有限的所以矩阵幂序列M, M^2, M^3, ... mod m一定会出现循环。我们可以通过模拟计算直到发现某个状态重复出现从而找到循环节长度T。然后就可以将巨大的指数n对T取模将问题化简。这种方法虽然理论上可能较慢最坏需O(m^3 * T)T可能达到m^2量级但对于小模数m通常是可行的。6.3 通用线性递推的矩阵构造对于k阶线性递推a(n) c1*a(n-1) c2*a(n-2) ... ck*a(n-k)。 可以构造k x k的转移矩阵MM [ [c1, c2, ..., ck-1, ck], [1, 0, ..., 0, 0 ], [0, 1, ..., 0, 0 ], ... [0, 0, ..., 1, 0 ] ]初始向量V [a(k-1), a(k-2), ..., a(0)]^T。 则[a(n), a(n-1), ..., a(n-k1)]^T M^(n-k1) * V。通过矩阵快速幂我们可以在O(k^3 log n)的时间内计算出a(n) mod m完美解决了高阶线性递推的超大项问题。7. 实战中的陷阱、技巧与心得理论懂了代码会写了但在实际比赛或项目中还有不少坑等着你。7.1 陷阱指数 b0 时的处理在使用扩展欧拉定理降幂时要特别注意b0的情况。根据公式a^b ≡ a^(b mod φ(m) φ(m)) (mod m)当b φ(m)。如果b0那么b φ(m)因为φ(m) 1我们应该直接计算a^0 mod m 1 mod m。但在某些实现中如果对b0进行大小判断和取模操作可能会出错。例如如果b是字符串0在判断b φ(m)时r最终为0flag为false我们会计算pow_mod(a, 0, m)这是正确的。但必须确保你的pow_mod函数能正确处理b0的情况返回1%m。7.2 技巧φ(m) 的计算优化与缓存计算φ(m)需要质因数分解对于单个查询O(√m)的复杂度可以接受。但如果需要在同一模数m下进行多次降幂操作比如处理多个不同底数a和指数b的查询那么每次调用都计算一次φ(m)是浪费的。一个简单的优化是预处理并缓存φ(m)的值。在竞赛中模数m通常是固定的可以在程序开始时计算一次φ(m)并存储起来。更进一步如果m很大比如10^12级别O(√m)的分解可能超时。这时可以考虑预处理质数表用筛法生成√m以内的所有质数然后用这些质数去试除m可以显著加快分解速度。7.3 心得理解“互质”前提的重要性这是最容易出错的地方。很多初学者记住了降幂公式但忽略了gcd(a, m) 1这个前提直接套用a^b ≡ a^(b mod φ(m)) (mod m)导致错误。错误示例计算2^3 mod 4。φ(4)2如果错误应用2^3 ≡ 2^(3 mod 2) 2^1 2 (mod 4)。但实际2^38, 8 mod 4 0。错误原因在于gcd(2,4)2 ≠ 1。正确的做法是使用扩展欧拉定理或者直接计算。对于a和m不互质的情况务必使用a^b ≡ a^(b mod φ(m) φ(m)) (mod m)当b φ(m)这个完整形式并且要注意其成立条件b φ(m)。当b φ(m)时即使不互质也只能直接快速幂计算。7.4 模运算的负数处理在快速幂或取模运算中底数a可能为负数。在C、Java等语言中%运算符对负数取模的结果是负数或与实现相关。为了保证结果在[0, m-1]范围内一个良好的习惯是在计算开始时先将底数a取一次模并调整为正数。long long mod(long long x, long long m) { return (x % m m) % m; // 保证结果在 [0, m-1] } long long pow_mod(long long a, long long b, long long m) { a mod(a, m); // 关键一步规范化a long long res 1 % m; // 处理 m1 的情况 while (b 0) { if (b 1) res (res * a) % m; a (a * a) % m; b 1; } return res; }7.5 大数指数 b 的大小比较优化在实现扩展欧拉定理判断b φ(m)时如果b是字符串φ(m)是long long类型直接逐位比较可能需要在字符串长度极大时进行很多次操作。一个优化是如果字符串b的长度位数已经超过φ(m)的位数那么b肯定大于φ(m)可以提前设置flagtrue并只进行取模运算无需逐位比较大小。只有当两者位数相同时才需要进行精确的逐位比较。这个优化对于指数b极其长的情况能节省一些时间。数论的世界深邃而美妙欧拉定理和费马小定理作为连接指数运算与模运算的桥梁其简洁的形式下蕴含着强大的力量。从解决一道简单的编程题到理解现代加密算法的基石再到处理复杂的线性递推掌握它们的关键在于深刻理解其成立的条件和本质并熟练运用降幂这一核心思想。在实战中时刻警惕互质前提小心处理边界条件如指数为0合理选择求逆元的方法才能避免掉入陷阱优雅地解决问题。