#数論知識
#

:raised_hands: 個人的な理解と思考のメモです。素数に関する部分は本を読むのがおすすめです。本の説明はかなり良く、細かく証明していない点もあります。特に Extended Chinese Remainder Theorem の部分は個人的な思考のまとめなので、参考程度にしてください。: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 である。\\ したがって、逆元 t_i について 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 のとき、N_j は n_i を因数に含むため、a_j \cdot N_j \cdot t_j \equiv 0 \pmod{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 と x_2 を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 となる。 $$

中国剰余定理

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

中国剰余定理は、法が互いに素であることを前提とします。法が互いに素でない場合は、合同方程式系を直接解くか、法を互いに素な形へ変換してから中国剰余定理へ帰着します。前者ではベズーの等式、後者では中国剰余定理の構成法を利用します。

拡張中国剰余定理の考え方

拡張中国剰余定理を中国剰余定理へ変換する考え方

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

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）#

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

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

関連記事