欧拉函数
在数论中，对正整数n，欧拉函数
是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为φ函数（由高斯所命名）或是欧拉总计函数（totient function，由西尔维斯特所命名）。
例如
，因为1,3,5,7均和8互质。
欧拉函数实际上是模n的同余类所构成的乘法群（即环
的所有可逆元组成的乘法群）的阶。这个性质与拉格朗日定理一起构成了欧拉定理的证明。
历史：欧拉函数与费马小定理
1736年，欧拉证明了费马小定理：
假若 
为质数，
为任意正整数，那么 
可被 
整除。
然后欧拉予以一般化：
假若 
与 
互质，那么 
可被 
整除。亦即，
。
其中 
即为欧拉总计函数。如果 为质数，那么 
，因此，有高斯的版本：
假若 为质数， 与 互质（ 不是 
的倍数），那么 
。
欧拉函数的值
（小于等于1的正整数中唯一和1互质的数就是1本身）。
若n是质数p的k次幂，
，因为除了p的倍数外，其他数都跟n互质。
欧拉函数是积性函数，即是说若m,n互质，
。证明：设A, B, C是跟m, n, mn互质的数的集，据中国剩余定理，
和
可建立双射(一一对应)的关系。（或者也可以从初等代数角度给出欧拉函数积性的简单证明） 因此的值使用算术基本定理便知，
若
则
。
其中
是使得
整除
的最大整数
（这里
）。
例如
性质
n的欧拉函数 也是循环群 Cn 的生成元的个数（也是n阶分圆多项式的次数）。Cn 中每个元素都能生成 Cn 的一个子群，即必然是某个子群的生成元。而且按照定义，不同的子群不可能有相同的生成元。此外， Cn 的所有子群都具有 Cd 的形式，其中d整除n（记作d | n）。因此只要考察n的所有因数d，将 Cd 的生成元个数相加，就将得到 Cn 的元素总个数：n。也就是说：
其中的d为n的正约数。