中国剩余定理是一个数学原理，它通过从除法的余数中寻找唯一解来解决模方程组。它被广泛应用于密码学和计算机科学领域，以实现高效的计算。
根据该定理，如果在给定的一组方程中，每个方程都有一个不同的数（假设为 n1, n2, …, nk），且这些数两两互质（relatively prime），同时还有一些数（假设为 a1, a2,…, ak），那么存在一个唯一解（我们称之为 x）可以同时满足所有方程。
这个解是在所有数的乘积（N = n1 · n2 ·…· nk）模下找到的。因此，x 满足每个方程，即在除以对应的数时，余数与给定的数相同。
简单来说，该定理表明：
> "如果一个数被几个没有公因数的其他数除，我们可以找到该数除以这些数的乘积时的余数。"
该解在模 N 下是唯一的，这意味着任何其他解在模 N 下都同余于原解。
中国剩余定理指出，由两两互质的正整数 (n1, n2,…., nk) 和任意整数 (a1, a2,…., ak) 定义的同余方程组，例如：
> x ≡ a1 (mod n1)
>
> x ≡ a2 (mod n2)
>
> ⦙
>
> x ≡ ak (mod nk)
存在一个模 (N = n1 n2 …. nk) 的唯一解 x，它同时满足所有同余方程。
为了证明中国剩余定理，让我们找到一个整数，使其满足：对于每个，都有 x ≡ ai (mod ni)。
我们定义 (Ni = N/ni)。
由于 (ni) 和 (Ni) 是互质的，根据裴蜀定理，存在整数 (si) 和 (ti) 使得：
si·ni + ti·Ni = 1
我们设 (yi = ti·Ni)。
现在，让我们如下构造 (x)：
x = \sum{i=1}^k ai \cdot y_i
这个解满足所有同余方程，即对于每个，都有 x ≡ ai (mod ni)。为了验证这一点，我们观察：
x ≡ ai·yi ≡ ai·ti·Ni ≡ ai·1 ≡ ai
因此，(x) 是该同余方程组的一个解。
唯一性：
假设 (x) 和 (x‘) 是同余方程组的两个解。我们要证明 x ≡ x‘ (mod N)。
设 (m = x‘ – x)。由于 (x) 和 (x‘) 都满足所有同余方程，(m) 必定也满足它们。因此，(m) 能被每个模数 (n1, n2,…., nk) 整除。
根据定义，(N = n1 · n2 ·….· nk)。由于 (m) 能被每个 (ni) 整除，它也能被 (N) 整除，即 m ≡ 0 (mod N)。
因此，x ≡ x‘ (mod N)，这就确立了唯一性。
为了使中国剩余定理成立，我们作为除数的数必须不能有任何公因数。所以，如果有两个数作为除数，比如 (mi) 和 (mj)，那么除了 1 以外它们不能有公因数。这意味着它们的最大公因数是 1。
> GCD(mi, mj) = 1
这个条件确保了同余方程组是相容的，并且由中国剩余定理提供的解在模数的乘积下是唯一的。如果模数不是两两互质的，那么该定理可能无法产生解，或者解可能不是唯一的。因此，两两互质性是应用中国剩余定理的基本要求。
中国剩余定理为涉及两个模数的同余方程组提供了解决方案。给定两个两两互质的模数 (m1) 和 (m2)，以及它们各自的余数 (a1) 和 (a2)，该定理指出，对于同余方程组：
x ≠ a1 mod m1
x ≠ a2 mod m2
存在一个模 (m1 × m2) 的唯一解。
我们可以使用以下公式找到解：
x = a1 + m1 \left( \frac{{a2 – a1}}{{m1}} \right) \left( \frac{{m1^{-1}}}{{m2}} \right) \ (\text{mod}\ (m1 \times m_2))
其中 (m1-1) 表示 (m1) 模 (m2) 的模乘法逆元。这个逆元可以使用扩展欧几里得算法等方法找到。
扩展欧几里得算法：计算两个整数 a 和 b 的 gcd，以及满足 a·x+b·y=gcd(a,b) 的整数 x 和 y（称为裴蜀系数）。其中，
- 两个整数 a 和 b (a>b)。
- gcd(a, b)：最大公因数。
- x, y：满足 a·x + b·y = gcd(a, b) 的整数。
它被广泛用于寻找模逆元（在密码学中至关重要）。
中国剩余定理…