MOD 运算也就是取模运算,欧拉函数 φ(n) 是数论里面和模运算高度绑定的核心函数,欧拉函数 φ(n) 的定义是,在 1 到 n 的整数当中,和 n 互质的正整数总个数,它最核心的价值就是支撑欧拉定理,欧拉定理专门用来简化 MOD 幂运算,也就是求 a 的 b 次方模 n 这类计算,在密码学 RSA 算法里面应用非常广泛,很多人学习的时候容易混淆,MOD 运算本身只是求余数,欧拉函数是配套这个模运算的工具,不是 MOD 运算本身,欧拉定理的条件是 a 和 n 互质,满足条件就有 a 的 φ(n) 次方 mod n 等于 1,利用这个结论,可以把很大的指数对 φ(n) 取模,大幅降低 MOD 幂运算的计算量,之所以这个组合非常重要,是因为大指数直接计算数值会非常巨大,借助欧拉函数降幂之后,MOD 运算就能快速算出结果。想要掌握 MOD 运算的欧拉函数,第一步理解欧拉函数定义,第二步学会对 n 做质因数分解求 φ(n),第三步牢记欧拉定理适用前提 a 与 n 互质,第四步利用 φ(n) 对指数降幂,最后完成 MOD 运算,综合来说 MOD 运算的欧拉函数,本质就是利用 φ(n) 实现模幂降幂,是数论和密码学必考知识点。
核心公式对照表
| 项目 | 公式 | 说明 |
|---|---|---|
| 欧拉函数定义 | φ(n) | 1 到 n 中和 n 互质正整数的个数 |
| 质数 p 的欧拉函数 | φ(p)=p-1 | 质数所有小于它的数都和它互质 |
| 质因数分解求 φ(n) | 若 n=p1^k1 × p2^k2,则 φ(n)=n×(1-1/p1)×(1-1/p2) | 积性函数,可分质因子计算 |
| 欧拉定理 | a^φ(n) ≡ 1 (mod n) | 前提 a 与 n 互质 |
| 费马小定理 | a^(p-1) ≡1 (mod p) | 欧拉定理特例,n 为质数 p |
深度知识点说明
第一 欧拉函数是积性函数,这个性质非常关键,如果 m 和 k 互质,那么 φ(mk)=φ(m)×φ(k),所以求 φ(n) 的时候,先把 n 拆成质数幂相乘,再分别计算每一项的欧拉函数再相乘,比如 n=12,分解 12=2²×3,φ(12)=12×(1-1/2)×(1-1/3)=4,也就是 1 到 12 里面和 12 互质的数一共有 4 个,分别是 1 5 7 11。
第二 欧拉定理在 MOD 幂运算的降幂逻辑,比如计算 a^b mod n,a 和 n 互质,因为 a^φ(n) mod n=1,所以指数 b 可以写成 b = k×φ(n)+r,那么 a^b mod n = a^r mod n,也就是指数 b 对 φ(n) 取余数,这个就是 MOD 运算里面欧拉函数最核心用法,把超大指数缩小,避免直接计算超大数。
第三 适用条件一定要记住,欧拉定理强制要求底数 a 和模数 n 互质,如果 a 和 n 不互质,不能直接套用欧拉定理降幂,这种情况要使用扩展欧拉定理,很多做题错误就是忽略互质条件,强行套用 MOD 运算的欧拉函数,最后结果出错。
第四 和费马小定理的关系,费马小定理是欧拉定理的特殊情况,当模数 n 是质数 p 的时候,φ(p)=p-1,代入欧拉定理就得到费马小定理,所以学习 MOD 运算的欧拉函数的时候,一般会同步学习费马小定理,二者经常放在考题里面对比。
计算示例
例子 计算 7^100 mod 10
第一步 判断 7 和 10 互质,计算 φ(10)=4
第二步 指数 100 对 φ(10)=4 取模,100 mod 4 =0
第三步 余数为 0 的时候,指数取 φ(n)=4,也就是 7^4 mod10
第四步 7^4 mod10=1,最终结果是 1
易错点清单
1 忘记欧拉定理前提,a 和 n 不互质还直接降幂
2 质因数分解出错,导致 φ(n) 计算错误
3 指数取模余数等于 0 的时候,忘记指数要替换成 φ(n)
4 混淆欧拉函数 φ(n) 和 MOD 运算,误以为 φ(n) 就是取模符号
实操解题步骤
1 确定模数 n,对 n 质因数分解,算出 φ(n)
2 判断底数 a 和 n 是否互质
3 互质则利用欧拉定理,对指数 b 模 φ(n) 降幂
4 计算降幂之后的 MOD 幂运算,得到最终余数
【常见问题】
问题 1 MOD 运算的欧拉函数,欧拉定理必须满足互质吗
回答 1 MOD 运算的欧拉函数对应的欧拉定理,必须满足底数 a 和模数 n 互质,MOD 运算的欧拉函数如果不满足互质,需要改用扩展欧拉定理。
问题 2 MOD 运算的欧拉函数,质数 p 的 φ(p) 等于多少
回答 1 MOD 运算的欧拉函数,质数 p 的 φ(p)=p-1,这也是费马小定理的来源,是 MOD 运算的欧拉函数最基础结论。
问题 3 MOD 运算的欧拉函数,它是积性函数吗
回答 1 MOD 运算的欧拉函数,欧拉函数属于积性函数,当两个数互质的时候 φ(ab)=φ(a)φ(b),这是 MOD 运算的欧拉函数分解计算的核心性质。
问题 4 MOD 运算的欧拉函数,主要用来做什么
回答 1 MOD 运算的欧拉函数,主要作用是简化大指数模幂运算,通过指数对 φ(n) 降幂,是 RSA 密码学里面 MOD 运算的欧拉函数核心应用场景。
【免责申明】
本内容 MOD 运算的欧拉函数属于数论学习科普,公式应用以教材标准定义为准,复杂非互质场景需要结合扩展欧拉定理,内容仅作为学习参考,不替代正式数论教材。


