#数论知识

:raised_hands:一些个人理解和思考（素数的一些建议看书，书本讲得不错，虽然有些点不加以细证），尤其Extened Chinese Remider Theroy那里，是个人思考总结的，仅供参考。:raised_hands:

• 数论pdf

---

• #数论知识
  • #贝祖定理（Bézout's identity）
  • #扩展欧几里得思路解析：
    • #扩展欧几里得c++代码
  • #中国剩余定理（Chinese Remainder Theorem）
  • #扩展中国剩余定理（Extened Chinese Remider Theroy）
    • #扩展中国剩余定理代码实现：

---

#贝祖定理（Bézout's identity）

用贝祖定理求出一个方程：ax + by = c 的解

x = x0 + b/gcd(a, b) * t
y = y0 - a/gcd(a, b) * t

贝祖定理的右边c改为1，就是求解模逆元的公式。所以，我才说，这个扩展欧几里得，本质上就是用贝祖定理。

贝祖定理的证明 -

---

#扩展欧几里得思路解析：

其实这个扩展欧几里得，我觉得本质上就是用贝祖定理

扩展点就是：能够实现自验证；最有用的点就是在运算过程中，找到贝租系数，从而就求解模逆元

看一下wiki就可以了 - extgcd 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的解。

这个思路还是要单独写一下，因为这个思路是很重要的，在后面的扩展中国剩余定理中会用到。其次要关注一下贝祖定理的思路分析

模逆元求解使用到了扩展欧几里得算法，看下方tips

---

---

中国剩余定理

• 

  中国剩余定理

---

#扩展中国剩余定理（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;
}