\(a, b\)の2つの正の整数が与えられたときに\(ax+by=\gcd(a, b)\)となるような整数\(x, y\)のうちの1つの組を計算するアルゴリズム
たとえば5リットルの入れ物と7リットルの入れ物を使って11リットルの水を汲む方法などが計算できる
昔こんなツイートをしてたようですがようやく理解できた気がします(遅すぎ。中国の剰余定理の方はまだ)
中国の剰余定理とか拡張ユークリッドの互除法とかわかってない(´・ω・｀)
— 無限猿(id:sucrose)@39月病 (@Scaled_Wurm) 2014年12月23日
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つの整数の最大公約数を求める方法
- コード上は必要ないが説明しやすくするため\(m = a, n = b\)と代入しておく
- \(m\)を\(n\)で割った余りを計算する。余りが\(0\)なら\(n\)が\(a, b\)の最大公約数
- 余りが\(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
拡張ユークリッドの互除法
- \(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)\)とする
- \(m\)を\(n\)で割った余りを計算する。余りが\(0\)なら\(n\)が\(a, b\)の最大公約数で\((x_2, y_2)\)が\(ax_2+by_2=\gcd(a,b)=n\)を満たす整数
- 余りが\(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\)を使えばよさそう)
