同余

同余中的一些定义。

同余

若整数 除以正整数 的余数相等，则称 模 同余，记作 。

同余类

对于 ，集合 的所有数模 同余，余数为 。该集合称作一个模 的同余类，记作 。

剩余系

完全剩余系

模 的同余类一共有 个，分别为 。它们构成 的完全剩余系。

简化剩余系

中与 互质的数所代表的同余类有 个（见欧拉函数），它们构成 的简化剩余系。

乘法封闭

简化剩余系关于模 乘法封闭。因为若 与 互质，则 与 互质，即 与 互质。

因此 都属于 的简化剩余系。