#数論知識
#

:raised_hands: 個人的な理解と思考のメモです。素数に関する部分は本を読むのがおすすめです。本の説明はかなり良く、細かく証明していない点もあります。特に Extened Chinese Remider Theroy の部分は個人的な思考まとめなので、参考程度にしてください。:raised_hands:

数論 pdf

#数論知識

#ベズーの等式（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 における解を構成できる。

この考え方は個別に書いておく必要があります。後の拡張中国剰余定理で使う重要な考え方だからです。さらに、ベズーの等式の考え方にも注目する必要があります。

$$ 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;
}

#数論知識#

#ベズーの等式（Bézout’s identity）#

#拡張ユークリッドの考え方解析：#

#拡張ユークリッド c++ コード#

#中国剰余定理（Chinese Remainder Theorem）#

#拡張中国剰余定理（Extened Chinese Remider Theroy）#

#拡張中国剰余定理コード実装：#

関連記事