同余理论

设整数 $m\ne 0$。若 $m\mid (a-b)$，称 $m$ 为 模数（模），$a$ 同余 于 $b$ 模 $m$，$b$ 是 $a$ 对模 $m$ 的 剩余。记作 $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m)$。

否则，$a$ 不同余于 $b$ 模 $m$，$b$ 不是 $a$ 对模 $m$ 的剩余。记作 $a\not\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m)$。

这样的等式，称为模 $m$ 的同余式，简称 同余式。

根据整除的性质，上述同余式也等价于 $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}(-m))$。如果没有特别说明，模数总是正整数。

同余的性质

• 同余是等价关系，即同余具有
  • 自反性：$a\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}m)$。
  • 对称性：若 $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m)$，则 $b\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}m)$。
  • 传递性：若 $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m),b\equiv c(\mathrm{m}\mathrm{o}\mathrm{d}m)$，则 $a\equiv c(\mathrm{m}\mathrm{o}\mathrm{d}m)$。
• 线性运算：若 $a,b,c,d\in \mathbf{Z},m\in {\mathbf{N}}^{\ast },a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m),c\equiv d(\mathrm{m}\mathrm{o}\mathrm{d}m)$ 则有：
  • $a\pm c\equiv b\pm d(\mathrm{m}\mathrm{o}\mathrm{d}m)$。
  • $a\times c\equiv b\times d(\mathrm{m}\mathrm{o}\mathrm{d}m)$。
• 设 $f(x)={\sum }_{i=0}^n{a}_i{x}^i$ 和 $g(x)={\sum }_{i=0}^n{b}_i{x}^i$ 是两个整系数多项式，$m\in {\mathbf{N}}^{\ast }$，且 $a_i\equiv b_i(\mathrm{m}\mathrm{o}\mathrm{d}m),0\le i\le n$，则对任意整数 $x$ 均有 $f(x)\equiv g(x)(\mathrm{m}\mathrm{o}\mathrm{d}m)$。进而若 $s\equiv t(\mathrm{m}\mathrm{o}\mathrm{d}m)$，则 $f(s)\equiv g(t)(\mathrm{m}\mathrm{o}\mathrm{d}m)$。
• 同时乘： 若 $a,b\in \mathbf{Z},k,m\in {\mathbf{N}}^{\ast },a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m)$, 则 $ak\equiv bk(\mathrm{m}\mathrm{o}\mathrm{d}mk)$。
• 同时除： 若 $a,b\in \mathbf{Z},d,m\in {\mathbf{N}}^{\ast },d\mid a,d\mid b,d\mid m$，则当 $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m)$ 成立时，有 $\frac{a}{d}\equiv \frac{b}{d}\left(\mathrm{m}\mathrm{o}\mathrm{d}\frac{m}{d}\right)$。
• 映射到更小模数： 若 $a,b\in \mathbf{Z},d,m\in {\mathbf{N}}^{\ast },d\mid m$，则当 $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m)$ 成立时，有 $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}d)$。
• 若 $a,b\in \mathbf{Z},d,m\in {\mathbf{N}}^{\ast }$，则当 $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m)$ 成立时，有 $(a,m)=(b,m)$。若 $d$ 能整除 $m$ 及 $a,b$ 中的一个，则 $d$ 必定能整除 $a,b$ 中的另一个。