3.1.1等价关系与分类
为了进一步刻画欧拉函数。我们先叙述等价关系与分类。
对集合的子集R称为的一个关系，如果这个关系具有
1）自反性：；
2）对称性：；
3）传递性：。
则称R是的一个等价关系。元素等价如果，记作或简记为。
记子集，根据等价的关系的定义，其中任意两个元素都是等价的，
称为以元素为代表元的等价类（也可记作）。一个等价类中任何元素均可作代表元。
中任何一个元素必属于某个等价类（有些等价类可能只含一个元素）。任何两个等价类，要么相同，要么不交（交为空集）。
从每个等价类中取出一个代表元构成一个代表元系，记为可按等价类分解为全部等价类的两两不交并的类方程：
这样，我们按等价关系得到集合的一个分类。
反之，如果集合存在一个不交并的分解：，，
则我们可以定义一个等价关系：
，也就是说，
。
例如之前的同余给出的等价关系：
给定正整数，，也就是，给出了的等价关系，
等价类的集合为模的剩余类。
3.1.2欧拉函数
我们将证明
考虑。
在中定义关系，
容易验证这个关系满足自反，对称及传递性，因此是等价关系，以
表示等价类。
我们有，并且，故中数的个数恰为。
另一方面，由等级分类，中每个数必属且只属于某个，即
于是
其中中元素的个数。
若的因子，则也是的因子，反之亦然。例如，，。
因此当的正因子时，则的正因子。于是
如果是的素因子分解，则
其中的素因子。
进一步，如果是素数，我们可以证明是循环群。即存在，均有。
换言之。
这样的，高斯称之为“原根”。