欧拉定理

欧拉定理把费马小定理从素数模数推广到任意正整数 $n$ ：若 $gcd (a, n) = 1$ ，则 $a^{φ (n)} \equiv 1 (\mod n),$ 其中 $φ (n)$ 是与 $n$ 互素的剩余类个数。若 $n = p$ 是素数， $φ (p) = p - 1$ ，于是得到费马小定理。

互素剩余类的乘法

列出模 $n$ 下与 $n$ 互素的剩余类 $r_{1}, \dots, r_{φ (n)}$ 。乘以与 $n$ 互素的 $a$ ，不会使某个结果失去互素性，也不会把两个不同剩余类映成同一个：若 $a r_{i} \equiv a r_{j}$ ，由模逆元约去 $a$ 即得 $r_{i} \equiv r_{j}$ 。因此乘 $a$ 只是重排名单。

把重排前后的全部元素相乘，可得 $a^{φ (n)} \prod r_{i} \equiv \prod r_{i} (\mod n)$ 。由于每个 $r_{i}$ 都有逆元，整份乘积也可约去，留下所需的幂同余。证明真正依赖的是互素类能形成可约的乘法结构。

例如 $n = 10$ 、 $a = 3$ ， $φ (10) = 4$ ， $3^{4} = 81 \equiv 1 (\mod 10)$ 。若去掉互素条件，结论可能失效： $a = 2, n = 4$ 时 $φ (4) = 2$ ，但 $2^{2} \equiv 0 (\mod 4)$ 。求幂的实际周期有时小于 $φ (n)$ ；定理只保证一个可用指数，并不声称它最短。

参考资料

MIT，Mathematics for Computer Science，Euler's Theorem 章节。
MIT 18.781，初等数论讲义。
继续阅读：欧拉函数、费马小定理、模逆元。