【南外夏令营】线性同余方程

Part 1：前置知识

• 扩展欧几里得算法（不会的点这里）

Part 2：求解线性同余方程

1、定义

• 给定整数 $a,b,m$，求一个整数 $x$ 满足 $a\ast x\equiv b(\mathrm{mod}m)$，或者给出无解。

• 因为未知数的指数为 $1$，所以我们称之为一次同余方程，也称线性同余方程。

2、求解

• $a\ast x\equiv b(\mathrm{mod}m)$ 等价于 $a\ast x-b$ 是 $m$ 的倍数，不妨设为 $-y$ 倍。于是，该方程可以改写为 $a\ast x+m\ast y=b$

• 根据 $Bezout$ 定理，该方程有解当且仅当 $\gcd (a,m)\mid b$

• 在有解时，我们就可以使用扩展欧几里得算法求出方程的一组特解：
  $$x=x_0\ast b/\gcd (a,m)$$
  其中 $x_0$ 为方程 $a\ast x_0+b\ast y_0=\gcd (a,m)$ 的一个解

• 方程的通解则是所有模 $m/\gcd (a,m)$ 与 $x$ 同余的整数，即
  $$x^{\prime }=x+k\frac{m}{\gcd (a,m)}(k\in \mathbb{Z})$$

Part 3：中国剩余定理

1、简述

• 设 $m_1,m_2,...,m_n$ 是两两互质的整数，$m={\prod }_{i=1}^n{m}_i$，$M_i=m/m_i$，$t_i$ 是线性同余方程 $M_i{t}_i\equiv 1(\mathrm{mod}{m}_i)$ 的一个解。对于任意的 $n$ 个整数 $a_1,a_2,...,a_n$，方程组
  $$\{\begin{array}{l}x\equiv a_1(\mathrm{mod}{m}_1)\\ x\equiv a_2(\mathrm{mod}{m}_2)\\ \dots \\ x\equiv a_n(\mathrm{mod}{m}_n)\end{array}$$
  有整数解，解为 $x={\sum }_{i=1}^n{a}_i{M}_i{t}_i$

• 由这组特解可推出方程组的通解为 $x+km(k\in \mathbb{Z})$

• 方程组的最小非负整数解为 $(x\mathrm{mod}m+m)\mathrm{mod}m$

2、证明

• 因为 $M_i=m/m_i$ 是除了 $m_i$ 之外所有模数的倍数，所以 $\forall k\ne i,a_i{M}_i{t}_i\equiv 0(\mathrm{mod}{m}_k)$

• 又因为 $a_i{M}_i{t}_i\equiv a_i(\mathrm{mod}{m}_i)$，所以代入 $x={\sum }_{i=1}^n{a}_i{M}_i{t}_i$，原方程组成立。