2.7　模的幂运算

2.7.1　欧拉定理

根据上面的数论知识，可以得到模运算的一个基本定理——欧拉定理。它与欧拉函数紧密相关，但概念不同。欧拉函数描述的是小于或等于的正整数中与互素的数的数目；欧拉定理在数论中是一个关于同余的性质，该定理被认为是数学世界中最美妙的定理之一，这是一个既优美且非常有用的结果。

定理2.7.1　欧拉定理（Euler’s Theorem）

如果，且，那么:

其中为欧拉函数。

例2.7.1　证明。

解：很显然，使用欧几里得算法可以算出，，因此，

定理2.7.2　模的幂运算

如果是非负整数并且满足，那么:

证明

例2.7.2　求的值。

解：