📂整数論

拡張ユークリッドの定理の証明

定理 ¹

二つの整数 $a,b$ に対して、$ax + by = \gcd (a,b)$ は必ず整数解を持つ。

説明

この定理は、$\gcd (a,b)$ が $a$ と $b$ を含む線形式で表現できることを意味しているため、線形合同定理とも呼ばれる。

見た目が少し複雑で存在性のみを論じるため、直接使用することは難しいかもしれないが、意外と広く使用される。具体的な解 $(x,y)$ を提供するわけではないが、$a$ と $b$ の関係式から出発できるというだけでも大きな収穫である。実際 $x$ や $y$ が何であるか知らないときには非常に便利に使用できる。

証明

初等的な証明

戦略：名前の通り、拡張ユークリッド定理はユークリッドの互除法を繰り返す。そのため、拡張ユークリッドアルゴリズムとも呼ばれる。

---

ユークリッドの互除法：$r_i<r_{i+1}$ に対して、漸化式 $r_{i-1} = q_{i+1} \cdot r_{i} + r_{i+1}$ を満たす$a: = r_{-1}$ と$b:=r_{0}$ を定義しよう。$r_{n+1} = 0$ を満たす$n$ に対して、$r_{n} = \gcd (a,b)$

ユークリッドの互除法によれば $r_{1}$ は $$r_{1} = a - q_{1} b$$ すなわち、$a$ と $b$ の線形結合として表せる。一方で $$r_{2} = b - q_{2} r_{1}$$ であり、直上の $r_{1} = a - q_{1} b$ を代入すると $$\begin{align*} r_{2} =& b - q_{2} r_{1} \\ =& b - q_{2} ( a - q_{1} b ) \\ =& -q_{2} a + ( 1 + q_{1} q_{2} ) b \end{align*}$$ となり、$r_{2}$ も $a$ と $b$ の線形結合として表せる。これを$n$ 回繰り返すと、$r_{n}$ はある$x,y \in \mathbb{Z}$ に対して $$r_{n} = x a + y b$$ と表されるだろう。ユークリッドの互除法では $r_{n} = \gcd (a,b)$ だから、$(x,y)$ は $ax + by = \gcd (a,b)$ の解として存在する。

■

代数的な証明

整数環 $\mathbb{Z}$ は PIDであるため、ベズー領域である。

■

関連項目

一般化：ベズー領域

代数的証明で指摘したように、ある領域がベズー領域であれば、その場所がどこであっても拡張ユークリッド定理が成立する。