唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

拡張ユークリッドの互除法

\(a, b\)の2つの正の整数が与えられたときに\(ax+by=\gcd(a, b)\)となるような整数\(x, y\)のうちの1つの組を計算するアルゴリズム
たとえば5リットルの入れ物と7リットルの入れ物を使って11リットルの水を汲む方法などが計算できる

昔こんなツイートをしてたようですがようやく理解できた気がします(遅すぎ。中国の剰余定理の方はまだ)

Wikipediaの説明を読んだらよくわからなくて？？？となったがいろいろググってなんとか理解した
\(a, b\)の2つの整数についてユークリッドの互除法をやるときに、\(ax_1+by_1=a\)と\(ax_2+by_2=b\)みたいに両辺がある形で考えて\(a(x_1 - 3x_2)+b(y_1-3y_2)=a - 3b\)みたいに両辺とも引き算していきながらユークリッドの互除法をやればよいらしい

ユークリッドの互除法

\(a, b\)の2つの整数の最大公約数を求める方法

  1. コード上は必要ないが説明しやすくするため\(m = a, n = b\)と代入しておく
  2. \(m\)を\(n\)で割った余りを計算する。余りが\(0\)なら\(n\)が\(a, b\)の最大公約数
  3. 余りが\(0\)でないなら\(m\)に\(m\)を\(n\)で割った余りを代入する。\(m\)と\(n\)を入れ替えて2.の処理に戻る
def euclid(a, b):
    assert a > 0
    assert b > 0
    
    m, n = a, b
    while m % n != 0:
        q = m / n
        m, n = n, m - q * n
    
    return b

拡張ユークリッドの互除法

  1. \(ax_1+by_1=m\)と\(ax_2+by_2=n\)の形の式2つを使って計算していく。ただし最初は\((x_1, y_1, m)=(1, 0, a), (x_2, y_2, n)=(0, 1, b)\)とする
  2. \(m\)を\(n\)で割った余りを計算する。余りが\(0\)なら\(n\)が\(a, b\)の最大公約数で\((x_2, y_2)\)が\(ax_2+by_2=\gcd(a,b)=n\)を満たす整数
  3. 余りが\(0\)でないなら通常のユークリッドの互除法で\(m\)を\(n\)で割った余りを代入したのと同様の計算を両辺についてする。つまり\(m\)を\(n\)で割ったときの商が\(q\)なら\(ax_1+by_1- q(ax_2+by_2)=m-qn\)、整理すると\(a(x_1-qx_2)+b(y_1-qy_2)=ax'_1+by'_1=m-qn =m'\)となる。通常のユークリッドの互除法と同様に\((x'_1, y'_1, m')\)と\((x_2, y_2, n)\)の変数を入れ替えて2.の処理に戻る
def extended_euclid(a, b):
    assert a > 0
    assert b > 0
    
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q = m / n
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, m - q * n
    
    return (x2, y2, n)

ベズーの等式

\(a, b\)が\(0\)でない整数の時\(ax+by=\gcd(a, b)\)となる\(x, y\)が存在するらしい
また\(ax+by=c\)が整数となるような\(c\)は\(\gcd(a, b)\)の倍数に限られる
拡張ユークリッドの互除法で得られる\(x,y\)の組は解の一つであり、すべての組は\((x+k\frac{b}{\gcd(a,b)}, y+k\frac{a}{\gcd(a,b)})\)で表される(ただし\(k\)は任意の整数)

合同式(modの計算)の逆元

また拡張ユークリッドの互除法を使って\(a, b\)が素数(または互いに素)であるときに\(ax \equiv 1 \pmod {b}\)となるような\(x\)を計算することができます。このような\(x\)は\(a\)で割り算をしたいときに代わりに使えるのでとても重要です
拡張ユークリッドの互除法によって\(ax+by=1\)となるような\(x, y\)が求められます
\(ax+by=1\)の両辺を\(\pmod {b}\)であると考えると\(ax \equiv 1 \pmod {b}\)となるので、拡張ユークリッドの互除法で求められた\(x\)が求めたい値になります(ちなみに負の数になった場合は\(b+x\)を使えばよさそう)

参考

d.hatena.ne.jp
topcoder.g.hatena.ne.jp