2021/02/18 数式を修正しました
拡張ユークリッド互除法とは
注意
書いた後で、概ね同じ内容を説明している記事を見つけました。分かりやすさには個人差があると思うので、本記事にも需要ありと信じて公開します。
本記事内で説明に使用しているコードは、コーナーケースやオーバーフロー、速度の定数倍、行儀などを一切考慮していません。
ユークリッド互除法 (非再帰)
int gcd(int a, int b) { s = a, t = b; while (s % t != 0) { int u = s % t; s = t; t = u; } return t; }
単純に言えば、最初 として、
を
に置き換えることを繰り返すアルゴリズムです。
拡張ユークリッド互除法
さて、ユークリッド互除法における と同時に「
の解
,
の解
」を管理することにしてみます。
初期条件は何でしょうか?
なので、
です。同様に、
となります。
std::pair<int, int> extgcd(int a, int b) { int s = a, xs = 1, ys = 0, t = b, xt = 0, yt = 1; ~略~
さて、後は として
が求まればユークリッド互除法と同様の繰り返しで求める
が得られます。
このままでは難しいので、式を書き換えます。
\begin{align}
u &= s \bmod t \\
\Leftrightarrow u &= s - t \left\lfloor \frac{s}{t} \right\rfloor \quad \text{剰余の定義} \\
\Leftrightarrow \left( ax_u + by_u \right) &=
\left( ax_s + by_s \right) - \left( ax_t + by_t \right) \left\lfloor \frac{s}{t} \right\rfloor
\quad s, t, u\text{を置換}
\end{align}
ここで最後の式を分解すると
\begin{align}
x_u &= x_s - x_t \left\lfloor \frac{s}{t} \right\rfloor \\
y_u &= y_s - y_t \left\lfloor \frac{s}{t} \right\rfloor
\end{align}
としてやれば条件を満たすことが分かります ( は共に整数になります)。
int temp = s / t; // floor(s / t) int u = s - t * temp; int xu = xs - xt * temp; int yu = ys - yt * temp;
後は前述のコードと全く同様に、 を
に置き換えていけば完成します。
std::pair<int, int> extgcd(int a, int b) { int s = a, xs = 1, ys = 0, t = b, xt = 0, yt = 1; while (s % t != 0) { int temp = s / t; int u = s - t * temp; int xu = xs - xt * temp; int yu = ys - yt * temp; s = t; xs = xt; ys = yt; t = u; xt = xu; yt = yu; } return {xt, yt}; }
*1:定義揺れはご了承ください