同余类与剩余系

来自潘承洞、潘承彪《初等数论》，有删改。

定义 1（同余类） 把全体整数分为若干个两两不相交的集合，使得
\((i)\) 在同一个集合中的任两个数模 \(m\) 一定同余；
\((ii)\) 在两个不同集合中的任两个数模 \(m\) 一定不同余。
每一个这样的集合称为模 \(m\) 的同余类。我们以 \(r\bmod m\) 表示 \(r\) 所属的模 \(m\) 的同余类。

容易知道对于正整数 \(m\)，这样的集合一共有 \(m\) 个，分别是 \(0\bmod m,1\bmod m,2\bmod m,…,(m-1)\bmod m\)。

定义 2（完全剩余系） 一组数 \(y_1,y_2,…,y_s\) 称为模 \(m\) 的完全剩余系，当且仅当 \(s=m\) 且 \(y_1,y_2,…,y_s\) 分别来自于模 \(m\) 的 \(m\) 个不同的同余类。

定义 3（既约同余类） 模 \(m\) 的同余类 \(r\bmod m\) 称为模 \(m\) 的既约同余类，当且仅当 \((r,m)=1\)。模 \(m\) 的所有不同既约同余类的个数为 \(\varphi(m)\)，通常称为欧拉函数。

定义 4（既约剩余系） 一组数 \(y_1,y_2,…,y_s\) 称为模 \(m\) 的既约剩余系，当且仅当 \(s=\varphi(m)\) 且 \(y_1,y_2,…,y_s\) 分别来自于模 \(m\) 的 \(\varphi(m)\) 个不同的既约同余类。