同余和同余式

定义

同余

设 若 即 则称 同余于 模 或 是 对模 的剩余，记作
不然则称 不同余于 模 或 不是 对模 的剩余，记作
关系式 (1) 称为模 的同余式，或简称同余式。

由于 等价于 所以同余式 (1) 等价于
因此，以后总假定模是满足 的。在同余式 (1) 中若 则称 是 对模 的最小非负剩余，若 则称 是 对模 的最小正剩余，若 或 则称 是 对模 的绝对最小剩余。

这样 就可记为 所以，所有的偶数可表示为 且由于奇数 满足 故所有的奇数可表示为 对给定的 和模 所有同余于 模 的数就可以是算术序列

定理

1. 的充要条件是 和 被 除后所得的最小非负余数相等，即若则

性质

对固定的模 同余，同余式和相等，相等式有以下同样的性质

1. 同余是一种等价关系，即有
2. 同余式可以相加，即若有则
3. 同余式可以相乘，即若 (2) 式成立，则有
4. 设 是两个整系数多项式，满足那么，若 则 通常我们把满足条件 (3) 的这两个多项式 称为多项式 同余于多项式 模 记作应该指出的是，对所有整数 有成立时，并不一定有式 (4) 成立
5. 设 那么，若同余式 (1) 成立，则
6. 设 那么同余式 (1) 等价于
7. 同余式等价于 特别地，当 时，同余式 (6) 等价于 即同余式 (6) 两边可约去
8. 若 则存在 使得我们把 称为是 对模 的逆，记作
9. 同余式组同时成立的充要条件是

证明