欧拉定理

一句话理解

欧拉定理：a^{φ(n)}≡1 (mod n)（gcd(a,n)=1）。

为什么要学

降幂。

讲解

费马是 n 为质数的特例。

例子

指数模 φ(n) 降下来。注意互质条件。

常见错误

• 不互质仍降。
• 降幂忘了 φ。