在数论，对
正整数n，欧拉函数是小于等于n的
正整数中与n
互质的数的数目。
基本性质
定义
一组数称为是模的既约
剩余系(简称
缩系)，如果对，并定义，即中与
互素的数的个数，称为欧拉函数。
显然，而对于，就是中与
互素的数的个数，比如说，若p为素数，则有。
性质
⑴设，则有
②若，则
⑵关于欧拉函数的两个重要结论：
①对于有.
①的证明：
易证
对,,设,则.一方面数有个，另一方面(按分类
计数)满足的有种取法.故有
②从反面思考或利用容斥原理易证.
欧拉定理的证明：
特别地，当时，，此时
同余类和完系
同余类
完系
在模的个
同余类中，每一类中取一个数，则叫做模的一个
完全剩余系(简称
完系)。显然，完系中的个数分别属于个不同的
剩余类。
最简单的模的完全剩余系是，也叫作模的最小非负
完系。