# 同余

同余关系是一种在整数上的等价关系，为整数论的核心分析要素

取整数 $m$
若整数 $a,b$ 满足：$a-b$ 能被 $m$ 整除
则称 $a$ 与 $b$ 关于模 $m$ 同余 (Congruent modulo $m$)，记作

$$a \equiv b \pmod{m}$$

同余关系之间保有加法和乘法，即若 $a \equiv b \pmod{m},\ a' \equiv b' \pmod{m}$，则有

• $$a + a' \equiv b + b' \pmod{m}$$

• $$a a' \equiv b b' \pmod{m}$$

利用同余关系的性质，可以实现快速判断一个数字对 $9$ 或 $11$ 的同余关系
将整数 $a$ 写为十进制展开形式

$$a = a_n 10^n + a_{n-1} 10^{n-1} + \ldots + a_1 10 + a_0$$

由于 $10^k \equiv 1 \pmod{9}$，所以

$$a \equiv a_n + a_{n-1} + \ldots + a_1 + a_0 \pmod{9}$$

同理，由于 $10^k \equiv (-1)^k \pmod{11}$，所以

$$a \equiv \sum_{k=0}^{n} a_k (-1)^k \pmod{11}$$

# 同余方程

同余方程指的是形如

$$f(x) \equiv 0 \pmod{m}$$

的方程，其中 $f(x)$ 为整数系数多项式

解同余方程的本质是解出符合同余关系的整数 $x$

若 $x$ 是同余方程 $f(x) \equiv 0 \pmod{m}$ 的解，那么关于模 $m$ 的等价类也是解

通常来说，同余方程最主要的是考察一次形式的多项式，即线性同余方程

$$ax \equiv b \pmod{m}$$

针对线性同余方程，其解的存在性由以下命题给出

解线性同余方程实际上是在利用 Euclidean 算法

# 中国剩余定理

针对互质的不同模数所构成的联立同余方程组可以由以下中国剩余定理解出

令线性同余方程组

$$\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_r \pmod{m_r} \end{cases}$$

其中 $m_1, m_2, \ldots, m_r$ 两两互素
中国剩余定理指出该同余方程组有唯一解，且解关于模 $M = m_1 m_2 \ldots m_r$ 同余
令 $M_i = \frac{M}{m_i}$
由于 $\gcd(M_i, m_i) = 1$，所以存在整数 $y_i$ 使得

$$M_i y_i \equiv 1 \pmod{m_i}$$

则同余方程组的解为

$$x \equiv \sum_{i=1}^{r} a_i M_i y_i \pmod{M}$$