Part 1：前置知识
- 扩展欧几里得算法（不会的点这里）
Part 2：求解线性同余方程
1、定义
-
给定整数 \(a,b,m\)，求一个整数 \(x\) 满足 \(a*x \equiv b \pmod m\)，或者给出无解。
-
因为未知数的指数为 \(1\)，所以我们称之为一次同余方程，也称线性同余方程。
2、求解
-
\(a*x\equiv b\pmod m\) 等价于 \(a*x-b\) 是 \(m\) 的倍数，不妨设为 \(-y\) 倍。于是，该方程可以改写为 \(a*x+m*y=b\)
-
根据 \(Bezout\) 定理，该方程有解当且仅当 \(\gcd(a,m)\mid b\)
-
在有解时，我们就可以使用扩展欧几里得算法求出方程的一组特解：
\[x=x_0*b/\gcd(a,m) \]其中 \(x_0\) 为方程 \(a*x_0+b*y_0=\gcd(a,m)\) 的一个解
-
方程的通解则是所有模 \(m/\gcd(a,m)\) 与 \(x\) 同余的整数，即
Part 3：中国剩余定理
1、简述
-
设 \(m_1,m_2,~...~,m_n\) 是两两互质的整数，\(m=\prod_{i=1}^n{m_i}\)，\(M_i=m/m_i\)，\(t_i\) 是线性同余方程 \(M_it_i\equiv 1 \pmod {m_i}\) 的一个解。对于任意的 \(n\) 个整数 \(a_1,a_2,~...~,a_n\)，方程组
\[\begin{cases}x\equiv a_1\pmod {m_1} \\ x\equiv a_2 \pmod {m_2} \\ \quad \quad \quad \dots \\ x \equiv a_n \pmod {m_n} \end{cases} \]有整数解，解为 \(x=\sum_{i=1}^n{a_iM_it_i}\)
-
由这组特解可推出方程组的通解为 \(x+km\; (k \in \mathbb{Z})\)
-
方程组的最小非负整数解为 \((x \bmod m+m)\bmod m\)
2、证明
-
因为 \(M_i=m/m_i\) 是除了 \(m_i\) 之外所有模数的倍数，所以 \(\forall k \ne i,\;a_iM_it_i \equiv 0 \pmod {m_k}\)
-
又因为 \(a_iM_it_i \equiv a_i \pmod {m_i}\)，所以代入 \(x=\sum_{i=1}^n{a_iM_it_i}\)，原方程组成立。