#数论知识#
:raised_hands:一些个人理解和思考（素数的一些建议看书，书本讲得不错，虽然有些点不加以细证），尤其Extened Chinese Remider Theroy那里，是个人思考总结的，仅供参考。:raised_hands:
#贝祖定理（Bézout’s identity）#
用贝祖定理求出一个方程：ax + by = c 的解
x = x0 + b/gcd(a, b) * t
y = y0 - a/gcd(a, b) * t贝祖定理的右边c改为1，就是求解模逆元的公式。所以，我才说，这个扩展欧几里得，本质上就是用贝祖定理。
贝祖定理的证明
#扩展欧几里得思路解析：#
其实这个扩展欧几里得，我觉得本质上就是用贝祖定理
扩展点就是：能够实现自验证；最有用的点就是在运算过程中，找到贝租系数，从而就求解模逆元
看一下wiki就可以了
手稿
#扩展欧几里得c++代码#
#include <iostream>
using namespace std;
int extgcd(int a, int b, int &x, int &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
int d = extgcd(b, a % b, x, y);
int t = x;
x = y;
y = t - a / b * y;
return d;
}
/*
另一种写法，更接近数学表达
struct EuclidResult
{
int d, x, y;
};
int extgcd(int a, int b)
{
int x_0 = 1, y_0 = 0, x_1 = 0, y_1 = 1;
while (b)
{
int temp;
int q = a / b;
temp = a- q * b;
a = b;
b = temp;
temp = x_0 - q * x_1;
x_0 = x_1;
x_1 = temp;
temp = y_0 - q * y_1;
y_0 = y_1;
y_1 = temp;
}
return EuclidResult{a, x_0, y_0};
}
*/这个x和y就是贝祖系数，一组解。
#中国剩余定理（Chinese Remainder Theorem）#
大致阐述：一个数x对于模数n1,n2,n3...nr的余数分别为r1,r2,r3...rn，且n1,n2,n3...nr两两互质，则x对于模数n1*n2*n3...*nr的余数为r1,r2,r3...rn的解。
这个思路还是要单独写一下，因为这个思路是很重要的，在后面的扩展中国剩余定理中会用到。其次要关注一下贝祖定理的思路分析
$$ S : \left\{ \begin{array}{ll} x \equiv r_1 \pmod{a_1} \\ x \equiv r_2 \pmod{a_2} \\ % \cdots \\ \vdots \\ x \equiv r_n \pmod{a_n} \\ \end{array} \right. $$模逆元求解使用到了扩展欧几里得算法，看下方tips
$$ N = n_1 \cdot n_2 \cdot n_3 \cdots n_i \cdots n_n \\ 记N_i = \frac{N}{n_i} = n_1 \cdot n_2 \cdots n_{i-1} \cdot n_{i+1} \cdots n_n \\ 可得 N_i 和 n_i 互质 即 gcd(N_i, n_i) = 1 \\ 所以 模逆元 N_i \cdot t_i \equiv 1 \pmod{n_i} \\ 即 a_i \cdot N_i \cdot t_i \equiv a_i \pmod{n_i} \\ 可得：当j \neq i时，a_j \cdot N_j \cdot t_j \equiv 0 \pmod{n_i} \text{因为}N_j包含了n_i \\ $$$$ \begin{align} x&=a_1 \cdot N_1 \cdot t_1 + a_2 \cdot N_2 \cdot t_2 + \cdots + a_n \cdot N_n \cdot t_n \\ &= a_i \cdot N_i \cdot t_i + \sum_{j \neq i} a_j \cdot N_j \cdot t_j \\ &\equiv a_i \pmod{n_i} \end{align} $$
$$ 所以可以得到：x的一个解为：a_1 \cdot t_1 \cdot N_1 + a_2 \cdot t_2 \cdot N_2 + \cdots + a_n \cdot t_n \cdot N_n \\ 记x_1 and x_2 为两个解，可得：\\ x_1 \equiv a_i \pmod{n_i} \\ x_2 \equiv a_i \pmod{n_i} \\ x_1 - x_2 \equiv 0 \pmod{n_i} \\ 所以可得：n_i | x_1 - x_2 \\ 因为任何一个i都成立，所以可得：n_1 \cdot n_2 \cdots n_i \cdots n_n | x_1 - x_2 \\ 即：N | x_1 - x_2 \\ => x_2 = x_1 + kN \\ 则x_2 和 x_1 差kN 所以最终的解为：x=a_1 \cdot t_1 \cdot N_1 + a_2 \cdot t_2 \cdot N_2 + \cdots + a_n \cdot t_n \cdot N_n + kN $$
中国剩余定理
#扩展中国剩余定理（Extened Chinese Remider Theroy）#
一些分析：我们可以看到，中国剩余定理的前提是模数两两互质，那么如果模数不互质，有一些思路提供参考：一：我们直接将这个同余方程组硬求解，利用到贝祖定理和中国剩余定理的思路；二：我们将其转化为中国剩余定理，即将模数变为两两互质，从而转换解的求解
扩展中国剩余定理的思路思考
扩展中国剩余定理转为中国剩余定理的思路
#扩展中国剩余定理代码实现：#
int exCRT(int n, int *a, int *m)
{
int M = 1;
for (int i = 0; i < n; i++)
M *= m[i];
int ans = 0;
for (int i = 0; i < n; i++)
{
int Mi = M / m[i];
ans = (ans + a[i] * Mi % M * mod_inv(Mi, m[i])) % M;
}
return (M + ans % M) % M;
}