ユークリッドの互除法（証明）
はじめに
ユークリッドの互除法に関しては、以前から割と苦手意識があります。
そこで今回はできるだけ丁寧に考えてみました。
もしかしたら間違いを含んでるかもしれません。
赤字は造語です。
準備
$a+b=c$ または $a-b=c$ の形の等式をabc等式とよぶことにする。
整数$a$、$b$、$c$について
$a+b=c \implies \gcd(a,b)=\gcd(b,c)=\gcd(c,a)$
あるいは
$a-b=c \implies \gcd(a,b)=\gcd(b,c)=\gcd(c,a)$
この最大公約数をabc等式の約数とよぶことにする。
２つのabc等式について考える。
$a+b=c$
$a'-b'=c'$
$\{a,b,c\}$と$\{a',b',c'\}$で2個以上の要素が共通するならば、2つのabc等式の約数は等しい。
整数$a$、$b$について、$n$を整数として以下が成り立つ
$\gcd(a,b)=\gcd(a+nb,b)$
$a+nb$は初項$a$、交差$b$の等差数列の項とみなせる。
よって、等差数列の任意の項と交差との最大公約数は一定。
$n=0$のとき自明。
$n\gt0$のとき、次の$n$本の等式を考える。
\begin{align}
a+b &= c_{1} \\
c_{1}+b &= c_{2} \\
c_{2}+b &= c_{3} \\
&\vdots \\
c_{n-3}+b &= c_{n-2} \\
c_{n-2}+b &= c_{n-1} \\
c_{n-1}+b &= c_{n} \\
\end{align}
命題1より、各行で等式の約数は保存されたまま推移するので
$\gcd(a,b)=\gcd(b,c_n)$
各行の等式を辺々足して整理すると
$c_n=a+nb$
これを先の式に代入して
$\gcd(a,b)=\gcd(a+nb,b)$
$n\lt0$のときは、等式の$+$を$-$に変えて同様の議論をすると示すことができる。
整数$a$、$b$に対して
$a=bq+r \qquad 0 \leq r \lt |b| $
なる整数$q$、$r$が一意に存在する。
整数$a$を$b$で割った、商を$q$、あまりを$r$とすると
$a=bq+r$
このとき
$\gcd(a,b)=\gcd(b,r)$
が成立する。
与式を変形すると
$r=a-bq$
命題2より
$\gcd(a,b)=\gcd(a-qb,b)=\gcd(r,b)$
互除法の証明
$a \gt b$である自然数$a$、$b$について商とあまりを求める(商を$q$、あまりを$r$とする)。
$a=bq+r$
算出された商$q$にとあまり$r$について、さらに商とあまりを求める。
同様の操作を繰り返すと、最終的なあまりは$\gcd(a,b)$と一致する。
除数を被除数に、あまりを除数にして割り算を繰り返す。
いわゆるユークリッドアルゴリズムを実行する。
\begin{align}
a&=bq_{1}+r_{1} \\
b&=r_{1}q_{2}+r_{2} \\
r_{1}&=r_{2}q_{3}+r_{3} \\
&\vdots \\
r_{k-2}&=r_{k-1} \cdot q_{k}+r_{k} \\
&\vdots \\
r_{n-3} &= r_{n-2} \cdot q_{n-1}+r_{n-1} \\
r_{n-2} &= r_{n-1} \cdot q_{n} +0\\
\end{align}
命題4より
$\gcd(a,b)=\gcd(b,r_{1})=\gcd(r_{1},r_{2})= \cdots=\gcd(r_{k-1},r_{k})=\cdots$
また
$b \gt r_{1} \gt r_{2} \gt \cdots \gt r_{k-1} \gt r_{k} \gt \cdots$
$\gcd(a,b)=g$とおくと、あまりの推移はこんな感じ
$ b' \cdot g \ \gt\ r'_{1} \cdot g \ \gt\ r'_{2} \cdot g \ \gt\ \cdots \ \gt\ r'_{k-1} \cdot g \ \gt\ r'_{k} \cdot g \ \gt\ \cdots$
$r_k$は「$g$の倍数」という条件を保ったまま小さくなっていく。
あまりは$0$以上であり、下限があるのでアルゴリズムが無限に続くことはない。
また $r_k \gt0$ である限りアルゴリズムは継続するので、
最終的に、互除法のアルゴリズムはあまりが$0$になって停止する。
このとき
$\gcd(a,b)=\gcd(r_{n-1},0)$
したがって
互除法が停止する直前のあまり$r_{n-1}$は$\gcd(a,b)$である。
おわりに
最後のあまりが$g$になることが納得しきれない時期がありました。
「$0$以上の$g$の倍数」という条件を保ったまま小さくなっていくとして
必ず$g$を経由するのか、$r_{n-1}=2g$とかになるケースはないのか、みたいな。
議論の正確さにはあまり自信がないので、間違いがあればご指摘お願いします。
