ユークリッドの互除法
定理
整数環$ \mathbb{Z}とその元$ a, b \in \mathbb{Z} \setminus \{0\}について、$ a, bの最大公約数を$ dとする $ A, B \in \mathbb{Z}が存在して、$ d = Aa + Bbとなる
拡張
証明
補題：割り算によって、$ a = qb + rと書くとき、$ d = \gcd(a, b) = \gcd(b, r) $ d' = \gcd(b, r)と書き、$ d = d'を示す
$ d | d'と$ d' | dを示せば良い
$ a = qb + rより、$ d' | aと$ d | rがわかる
よって、$ d, d'はともに、$ \gcd(a, b, r)と等しいので$ d = d'
前処理
$ a, bを正の整数としてよい
$ a < 0ならば、$ -aで考えて$ A \mapsto -Aとすれば良い
同様に、$ bも正の整数として良い
$ a > bとしてよい
$ b < aならば、これらを入れ替えればよい
本題：$ A, B \in \mathbb{Z}が存在して、$ d = Aa + Bb
$ a_0 = a, \quad b_0 = bとする
以下の再帰的な処理により、数列$ \{a_i\}, \{b_i\}を作る
$ a_i \div b_iをかんがえ、割り算の原理から以下を満たす$ q_i, r_i \in \mathbb{Z}^+が存在する $ a_i = q_i b_i + r_i, \quad 0 \leq r_i < b_i
$ a_{i+1} = b_i, b_{i+1} = r_iとする
終了条件：$ b_i = r_{i-1} = 0になったときに終了する
$ 0 \leq b_{i+1} = r_i < b_iより、$ b_iは下限をもち真に降下する数列である
よって、$ b_i=0となる$ iが存在する
命題：この数列について、$ \gcd(a, b) = \gcd(a_i, b_i)が成り立つ
上の補題より、$ \gcd(a_i, b_i) = \gcd(b_i, r_i) = \gcd(a_{i+1}, b_{i+1})
$ \gcd(a, b) = \gcd(a_0, b_0)より、すべての$ iについて$ \gcd(a, b) = \gcd(a_0, b_0) = \gcd(a_i, b_i)
最大公約数
$ b_{N+1} = r_N = 0となり、終了したとする
$ a_N = q_N b_N
このとき、$ \gcd(a, b) = \gcd(a_N, b_N) = \gcd(q_Nb_N, b_N) = b_Nより、$ b_Nは$ a, bの最大公約数 $ N-1回目を考えると
$ a_{N-1} = q_{N-1} b_{N-1} + r_{N-1} = q_{N-1} b_{N-1} + b_N = q_{N-1} b_{N-1} + d
より、
$ d = a_{N-1} - q_{N-1}b_{N-1}
$ a_{N-1} = b_{N-2},\ b_{N-1} = r_{N-2} = a_{N-2} - q_{N-2}b_{N-2}より
$ d = b_{N-2} - q_{N-1}(a_{N-2} - q_{N-2}b_{N-2}) = q_{N-1}a_{N-2}+b_{N-2}(1+q_{N-2})
これを繰り返せば、$ d = Aa_0 + Bb_0 = Aa + Bbとかける