同余式与同余类
设 是非零整数， 和 是整数. 如 ，则称 和 模 同余 (或 模同余于 )，记作
如果 ，则称 和 模 不同余 ，记作
（1）式称为(模 的) 同余式 .
设 是一个固定的正整数. 由于“模 同余” 是整数集上的一个等价关系，由此可将整数按模 是否同余分为若干个两两不相交的类，使得同一个类中的任意两个数模 同余，而不同类中的两个数模 不同余；每一个正阳的类称为 模 的同余类 . 我们将整数 所属的模 的同余类记作 ，在不引起混淆时可简记为 ，它由所有模 同余于 的整数组成，即
称为它的一个 代表元 . 易知，当 时，有 ；否则 与 不相交(即没有公共元素)
由带余除法，任一整数，比与 中的一个模 同余，而 彼此模 不同余. 因此，模 恰有 个不同的同余类，它们是 . 我们用 表示这个 个类的集合. (一个类看作一个元素)
如果 ，则有同余类 中每个整数也均与 互素，这样的同余类称为模 的 缩同余类 ，换句话说， 是(模 ) 缩同余类指的是 .
我们用 表示模 的缩同余类组成的集合，其元素个数记作 ，称为 欧拉函数 ，这是初等数论中一个重要的函数. 显然， ，而对 即为 中与 互素的数的个数.
例如，若 是素数，则模 共有 个缩同余类： ，从而
个整数 称为 模 的完全剩余系 ，简称为模 的 完系 ，是指 彼此模 不同余. 数 则称为 模 的 最小非负完系 .
个整数 称为 模 的缩剩余系 ，简称为 缩系 ，是指它们彼此模 不同余，且均与 互素. 不超过 且与 互素的 个正整数则叫作模 的 最小正缩系
于是， 为模 的完系，等价于说 恰好是模 的全部 个同余类；而 是模 的缩系，则等价于说 恰好是模 的全部 个缩同余类，因此，任意两个完(缩)系中的数，将其中一个的顺序适当调整，必然两两模 同余.
如 ，则存在 使
我们将这样的 称为 对 模 的逆 ，记作 或 ，他们形成模 的一个同余类（从而在模 的意义下唯一）.特别地，有一个 满足
同余关系是等价关系，即有
(i) （自返性）
(ii) （对称性） 如果 ，则
(iii) （传递性） 如果 ，则
如果 ，则
(i)
(ii) .
设 是 元整数系数多项式. 如果 ，则
若
则 . 特别地，当 时，我们有
(i) 如果 ，则
(ii) 如果 ，则 . 反之亦然
(iii) 如果 ，则 ，反之亦然
设 是任意整数.
(i) 如果 是模 的完系，则 也是模 的完系；
(ii) 如果 是模 的缩系，则 也是模 x ax\equiv b\pmod{m} x m$ 的一个同余类
设 ，则
(i) ;
(ii) 的充分必要条件是
(iii) 如果 是模 的任一缩系，则它们的逆 也是模 的一个缩系.
