欧拉函数
欧拉函数 φ(n) 是小于等于 n 的正整数中与 n 互质的数的个数。
欧拉定理
内容
在数论中，欧拉定理,（也称费马-欧拉定理）是一个关于同余的性质。
欧拉定理表明，若n,a为正整数，且n,a互质，则:
a ^ φ(x) ≡ 1 (mod n)
费马小定理
定理
a是不能被质数p整除的正整数，则有 a^(p-1) ≡ 1 (mod p)
证明这个定理非常简单，由于p是质数，所以有 φ(p) = p-1，代入欧拉定理即可证明。
推论
推论：对于任意正整数a，有 a^p ≡ a (mod p)，因为a能被p整除时结论显然成立。
应用
基本例子
首先看一个基本的例子。
令a = 3，n = 5，这两个数是互素的。
比5小的正整数中与5互素的数有1、2、3和4，所以φ(5)=4。
计算:a^{φ(n)} = 3^4 =81，而81= 80 + 1 ≡ 1 （mod 5）。
与定理结果相符。
简化幂的模运算
这个定理可以用来简化幂的模运算。
比如计算7^{222}的个位数，实际是求7^{222}被10除的余数。
7和10互素，且φ(10)=4。
由欧拉定理知7^4≡1(mod 10)。
所以7^{222}=(7^4)^55(7^2)≡1^{55}7^2≡49≡9 (mod 10)。
