Keywords: Euclid の互除法, ユークリッドの互除法
$a$, $b$ を整数とし, $0<b<a$ であるとする. $$ r_{0} = a,\quad r_{1} = b $$ とおき, $n\geq 2$ に対して, $r_{n-1}>0$ である限り, $r_{n}$を $$ r_{n-2} = r_{n-1}q_{n-1}+r_{n},\quad 0\leq r_{n}<r_{n-1} $$ によって定義する. このとき, ある番号 $m$ が存在して, $$ r_{m} = 0,\quad r_{m-1}=\gcd(a,\,b) $$ が成り立つことを証明せよ.
解答例 1
まず, $r_{m}=0$ となる番号 $m$ が存在することを背理法で証明する.
$r_{m}=0$ となる番号 $m$ が存在しないと仮定すると, $r_{n}$の定め方から, 無限に続く減少列 $$ a=r_{0}>r_{1}>r_{2}>\cdots >r_{n-2}>r_{n-1}>r_{n}>\cdots >0 $$ が得られる. ところがこれは, $a$ 以下の正の整数が有限個しかないことに反する. したがって, $r_{m}=0$ となる番号 $m$ は存在する.
さらに, 任意の整数 $a$, $b$, $q$, $r$ に対して, $a=bq+r$ ならば $\gcd(a, b)=\gcd(b, r)$ が成り立つ. このことを繰り返し用いると, \begin{align*} r_{m-1} &= \gcd(r_{m-1},\,r_{m}) \\ &= \gcd(r_{m-2},\,r_{m-1}) \\ &= \cdots\cdots \\ &= \gcd(r_{0},\,r_{1}) \\ &= \gcd(a,\,b). \end{align*}
最終更新日：2011年11月02日