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