ユークリッドの互除法 (Euclidean algorithm) といえば最小公倍数 (GCD) を計算するためのアルゴリズムですけれども、拡張することでモジュラー逆元、有理数復元などなど便利なことができることはみなさまご存知。ご存知…… アッ、じゃあこの記事いらないですね。
お疲れ様でした。
というわけで本文です。
1. 普通のユークリッドの互除法 (GCD の計算)
まあこのへんはみなさまご存知でしょうし軽く流しましょう。
- 入力
- 正整数 $x \ge y > 0$
- 出力
- $\mathrm{gcd}(x, y)$
- アルゴリズム
- 数列 $\left( r _ i \right) _ { i = 0 } ^ d$ を次のように定めます。 $$ \begin{cases} r _ 0 = x, \ r _ 1 = y, \\\\ r _ { i + 2 } = r _ i \mathop{\mathrm{rem}} r _ { i + 1 } & (i \ge 0 , \ r _ { i + 1 } \neq 0) \end{cases} $$ ただし $r _ { i + 1 } = 0 $ のときは $r _ { i + 2 }$ は未定義として、そこで数列終了です。
- 例: $x = 88, \ y = 52$ のとき
- $ r = \left ( 88, 52, 36, 16, 4, 0 \right), \ d = 5 $
初期値によらず、この数列はいつかは $0$ に到達し、その直前 $r _ { d - 1 }$ が $\mathrm{gcd}(x, y)$ に一致しますね。
2. ベズー (Bézout) 係数
以降、$\mathrm{gcd}(x, y) = 1$ を仮定します。（視聴者の声: だってダルいではありませんか）
このとき、次の式を満たす整数 $s, \ t$ が存在します。（うれしい！）
$$ s \cdot x + t \cdot y = 1 $$
- Q:
- これって一意なのですか？
- A:
- なわけあるかーい！（ベシーン！） $$ (s + ky, \ t - kx) \ (k \in \mathbb{Z}) $$ の形のものも全て解になりますね。（逆に、これだけです）
さて、$x = 7, \ y = 5$ を例に図示してみましょう。($y = 1$ のときは境界が解でしたねそういえば。)
はい逗子終わり。次は新木場です。
3. ユークリッドの拡張互除法 (Extended Euclidean algorithm) で Bézout 係数を求める
ライブラリだけはお持ちの方が多いのではないでしょうか。
さて、あまりだけでなく商のほうも見てみましょうかね。次のように商 $\left( q _ i \right) _ { i = 0 } ^ { d - 2 }$ を定義します。
$$ r _ { i + 2 } = r _ i - q _ i \cdot r _ { i + 1 } \ ( 0 \le i \le d - 2 ) $$
漸化式もどきですね。これの初項だけ変更した次の数列 $\left( s _ i \right) _ { i = 0 } ^ d, \ \left( t _ i \right) _ { i = 0 } ^ d$ を導入しましょう。
$$ \begin{gather} ( s _ 0, \ s _ 1 ) = ( 1, \ 0 ), & s _ { i + 2 } = s _ i - q _ i \cdot s _ { i + 1 } \\ ( t _ 0, \ t _ 1 ) = ( 0, \ 1 ), & t _ { i + 2 } = t _ i - q _ i \cdot t _ { i + 1 } \end{gather} $$
フッフッフ、実はこれがすごくｔ……ってアアッ！ 変数名がネタバレではありませんか。全くもう……
一般的でない用語ですが、これを部分 Bézout 係数 (partial Bézout coefficient) と呼んでおきましょうか。
例です。手書き楽ですね。
楽すぎてもう一個書いてしまいます。
あれ、なんか紙にまでネタバレが…… まあいいです。眺めるといろいろな性質が見えてきますね。それ、だいたい成り立ちます！
まずは最後の方の値の性質をば。
- $\left(s _ { d - 1 }, \ t _ { d - 1 } \right)$ は Bézout 係数で、絶対値がそれぞれ $y, \ x$ 未満
- $\left(s _ d, \ t _ d \right)$ は絶対値がそれぞれ $y, \ x$ で、異符号
もう少し一般的なことを言うと？ (↑が↓の特別な場合であることをチェックしてみてくださいね)
- $\left( s _ i \right) _ { i = 0 } ^ d, \ \left( t _ i \right) _ { i = 0 } ^ d$ の符号 ($0$ は負の仲間) は、市松模様になっている
- $\left( s _ i \right) _ { i = 0 } ^ d, \ \left( t _ i \right) _ { i = 0 } ^ d$ は、$i \ge 2$ において、絶対値が狭義単調増加
- 等式 $s _ i x + t _ i y = r _ i \ ( 0 \le i \le d )$ が成り立つ
- $\mathrm{det}\begin{pmatrix} s _ i & s _ { i + 1 } \\ t _ i & t _ { i + 1 } \end{pmatrix} = (-1) ^ i$
- 絶対値の上界 $\left| s _ i \right| \cdot r _ i < y, \ \left| t _ i \right| \cdot r _ i < x \ (i \ge 2)$ が成り立つ
下 $3$ つはちょっと難しいですが、上 $2$ つはすぐにわかります。市松模様状に $-1$ 倍したものを $\left( s' _ i \right) _ { i = 0 } ^ d, \ \left( t' _ i \right) _ { i = 0 } ^ d$ と置くと漸化式もどきが $s' _ { i + 2 } = s ' _ i + q _ i \cdot s' _ { i + 1 } , \ t' _ { i + 2 } = t' _ i + q _ i \cdot t' _ { i + 1 }$ となり、この形ならば正であることの保存と、単調増加性もすぐわかりますね。
4. 理論( ᐛ👐)パァと
遷移を行列で書きましょう。$R _ { q _ i } = \begin{pmatrix}0 & 1 \\ 1 & - q _ i\end{pmatrix}$ とおくと、次のようになります。(ところでこの行列 $R _ { q _ i }$ は行列式が $-1$ ですね。これが $+1$ でないのが面倒な偶奇性の源と言っても過言ではありませんね。)
$$ \begin{pmatrix} r _ { i + 1 } & r _ { i + 2 } \\ s _ { i + 1 } & s _ { i + 2 } \\ t _ { i + 1 } & t _ { i + 2 } \end{pmatrix} = \begin{pmatrix} r _ i & r _ { i + 1 } \\ s _ i & s _ { i + 1 } \\ t _ i & t _ { i + 1 } \end{pmatrix} \cdot R _ { q _ i } $$
初期値から全部累積したらこうです。
$$ \begin{pmatrix} r _ i & r _ { i + 1 } \\ s _ i & s _ { i + 1 } \\ t _ i & t _ { i + 1 } \end{pmatrix} = \begin{pmatrix} x & y \\ 1 & 0 \\ 0 & 1 \end{pmatrix} \cdot R _ { q _ 0 } \cdot R _ { q _ 1 } \cdot \dots \cdot R _ { q _ { i - 1 } } $$
等式パート
目標は次の $2$ つです:
- $\mathrm{det}\begin{pmatrix} s _ i & s _ { i + 1 } \\ t _ i & t _ { i + 1 } \end{pmatrix} = (-1) ^ i \ (0 \le i \le d)$
- $s _ i x + t _ i y = r _ i \ (0 \le i \le d)$
行列形の漸化式もどきの下 $2$ 行を見ると？
$$ \begin{pmatrix} s _ i & s _ { i + 1 } \\ t _ i & t _ { i + 1 } \end{pmatrix} = R _ { q _ 0 } \cdot R _ { q _ 1 } \cdot \dots \cdot R _ { q _ { i - 1 } } $$
ちなみにこれで $\mathrm{det}\begin{pmatrix} s _ i & s _ { i + 1 } \\ t _ i & t _ { i + 1 } \end{pmatrix} = (-1) ^ i$ もわかりましたね。
そしてこれを元の式に再代入して、上 $1$ 行を見ると？
$$ \begin{pmatrix} r _ i & r _ { i + 1 } \\ \end{pmatrix} = \begin{pmatrix} x & y \\ \end{pmatrix} \begin{pmatrix} s _ i & s _ { i + 1 } \\ t _ i & t _ { i + 1 } \end{pmatrix} $$
そして左 $1$ 列を見ると、$s _ i x + t _ i y = r _ i$ もわかりましたね。
不等式パート
さてさて、これで等式系の性質は一通り示しましたけれども、難しいのはここからです。不等式系の性質を示していきましょう。
目標は次の $2$ つです:
- $\left(s _ { d - 1 }, \ t _ { d - 1 } \right)$ は Bézout 係数で、絶たちがそれぞれ $y, \ x$ 未満
- $\left(s _ d, \ t _ d \right)$ は絶対値がそれぞれ $y, \ x$ で、異符号
- 絶対値の上界 $\left| s _ i \right| \cdot r _ i < y, \ \left| t _ i \right| \cdot r _ i < x (i \ge 2)$ が成り立つ
あ $3$ つでした。コピペはよくないですね。
まずは簡単な最後尾から。
$$ \begin{pmatrix} x & y \end{pmatrix} \begin{pmatrix} s _ { d - 1 } & s _ d \\ t _ { d - 1 } & t _ d \end{pmatrix} = \begin{pmatrix} 1 & 0 \end{pmatrix} $$
パズルで特定していきましょう。まずは右の $1$ 列から。
$$ \begin{pmatrix} s _ d \\ t _ d \end{pmatrix} = k \cdot \begin{pmatrix} y \\ -x \end{pmatrix} \ ( k \in \mathbb{Z}) $$
なわけですが、行列式の条件から $k = \pm 1$ ですね。もっと言うと部分 Bézout 係数の符号の市松模様定理（しれっと命名）から $k = (-1) ^ i$ もわかりますね。
次に左の $1$ 列をば。$s _ { d - 1 }, \ t _ { d - 1 }$ が Bézout 係数であることは式を見れば明らかですね。さらに部分 Bézout 係数の絶対値の単調性定理より、$\left| s _ { d - 1 } \right| < y, \ \left| t _ { d - 1 } \right| < x$ もわかります。
さて、ラスボスです。部分 Bézout 係数の絶対値の上界を与えましょう。そこで、漸化式もどから $2$ 行に着目しましょう。
$$ \begin{align} \begin{pmatrix} r _ i & r _ { i + 1 } \\ s _ i & s _ { i + 1 } \end{pmatrix}&= \begin{pmatrix} x & y \\ 1 & 0 \end{pmatrix} \cdot R _ { q _ 0 } \cdot R _ { q _ 1 } \cdot \dots \cdot R _ { q _ { i - 1 } } \\ \begin{pmatrix} r _ i & r _ { i + 1 } \\ t _ i & t _ { i + 1 } \end{pmatrix}&= \begin{pmatrix} x & y \\ 0 & 1 \end{pmatrix} \cdot R _ { q _ 0 } \cdot R _ { q _ 1 } \cdot \dots \cdot R _ { q _ { i - 1 } } \\ \end{align} $$
てことは、行列式がわかりますね。$\mathrm{det}$ って書くの疲れましたし開いておきましょう。
$$ \begin{cases} r _ i s _ { i + 1 } - r _ { i + 1 } s _ i = (-y) \cdot ( -1 ) ^ i \\ r _ i t _ { i + 1 } - r _ { i + 1 } t _ i = x \cdot ( -1 ) ^ i \end{cases} $$
市松模様定理より、左辺の $2$ 項は同符号なので、正の数ばかりの式がつくれますね。
$$ \begin{cases} r _ i \left| s _ { i + 1 } \right| + r _ { i + 1 } \left| s _ i \right| = y \\ r _ i \left| t _ { i + 1 } \right| + r _ { i + 1 } \left| t _ i \right| = x \end{cases} $$
はい仕上げです。片方の項だけをとって、あとは単調性定理です。単調性定理を使えるように、$i \ge 2$ を仮定しましょう。
$$ \begin{cases} y = r _ i \left| s _ { i + 1 } \right| + r _ { i + 1 } \left| s _ i \right| \ge r _ i \left| s _ { i + 1 } \right| \ge r _ i \left| s _ i \right| \\ x = r _ i \left| t _ { i + 1 } \right| + r _ { i + 1 } \left| t _ i \right| \ge r _ i \left| t _ { i + 1 } \right| \ge r _ i \left| t _ i \right| \end{cases} $$
これで $\left| s _ i \right| \cdot r _ i < y, \ \left| t _ i \right| \cdot r _ i < x \ (i \ge 2)$ もわかりましたね。(厳密には $i = d$ の場合は示せていませんが $r _ d = 0$ より明らかです。）
ちなみにこれ証明を工夫すると、もうちょっとだけ強い主張に出来ます！
$$ \begin{align} 1 \le \forall b < y \ & : \ 2 \le \exists i \le d \ : \ r _ i < b \land \left| s _ i \right| < \frac{y}{b} \\ 1 \le \forall a < x \ & : \ 2 \le \exists i \le d \ : \ r _ i < a \land \left| t _ i \right| < \frac{x}{a} \end{align} $$
証明は似たような感じです。１つ目の定理だけ示しますね。まずは $r _ i < b$ が成り立つ最小の $2 \le i < d$ を取ります。すると $b \le r _ { i + 1 }$ が成り立ちますから、次のようになりますね。なお途中の不等式を strict にするのには $i \neq d$ を使っています。)
$$ \begin{align} y = r _ i \left| s _ { i + 1 } \right| + r _ { i + 1 } \left| s _ i \right | \gt r _ { i + 1 } | s _ i | \ge b \left| s _ i \right| \end{align} $$
というわけで、$b < y / s _ i$ です。
5. モジュラー演算への応用
素数 $p$ に関する $x \in [0, p[$ のモジュラー逆元を求めましょう。そのためには $x, \ y$ の代わりに $p, \ x$ を考えればよいです。すると Bézout 係数の等式は
$$ s p + t x = 1 $$
となります。両辺 $\bmod p$ をとることで、 Bézout 係数が $x$ のモジュラー逆元になりますね。さらに絶対値も $p$ 未満であることがわかります。（これ証明なしで使っているみなさま～～～）
次に有理数復元です。同じことを部分 Bézout 係数についてやりましょう。
$$ s _ i p + t _ i x = r _ i $$
これも $\bmod x$ することで $x = r _ i / t _ i$ がわかります…… が！ こういうのは絶対値を抑えてこそですよね！
$$ \begin{gather} x = \frac { r _ i } { t _ i }, & r _ i \left| t _ i \right| < p \ \ (2 \le \forall i \le d) \end{gather} $$
もちろん先に $b$ を決めて $r _ i < b$ を課して…… というあれもできます。つまり $\mathbb{Z} / 998244353 \mathbb{Z}$ の任意の元を分母・分子ともに $\lfloor\sqrt{998244353}\rfloor$ 以下になるように有理数で表す、みたいなこともできるわけです。
はい。（終わりのごあいさつ）
