欧拉定理

欧拉定理的证明与应用。

欧拉定理

若 与 互质，则 ，其中 为关于 的欧拉函数，这就是欧拉定理。

证明

设 为模 意义下的一个简化剩余系，
因为 与 互质，根据简化剩余系的乘法封闭性

因此

应用

费马小定理

若 为质数，则 与 互质，根据上式得到： ，也可以写成 ，这就是费马小定理。

乘法逆元

若整数 互质，则 为 的模 的乘法逆元。

如果 为质数，由费马小定理得

因此 为质数时， 在模 的乘法逆元为 。