ユークリッドの互除法（証明）

はじめに

ユークリッドの互除法に関しては、以前から割と苦手意識があります。
そこで今回はできるだけ丁寧に考えてみました。
もしかしたら間違いを含んでるかもしれません。
赤字は造語です。

準備

$a + b = c$ または $a - b = c$ の形の等式をabc等式とよぶことにする。

abc等式における最大公約数の保存

整数 $a$ 、 $b$ 、 $c$ について
$a + b = c ⟹ gcd (a, b) = gcd (b, c) = gcd (c, a)$
あるいは
$a - b = c ⟹ 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 + n b, b)$

$a + n b$ は初項 $a$ 、交差 $b$ の等差数列の項とみなせる。
よって、等差数列の任意の項と交差との最大公約数は一定。

$n = 0$ のとき自明。
$n > 0$ のとき、次の $n$ 本の等式を考える。
$\begin{aligned} a + b & = c_{1} \\ c_{1} + b & = c_{2} \\ c_{2} + b & = c_{3} \\ ⋮ \\ c_{n - 3} + b & = c_{n - 2} \\ c_{n - 2} + b & = c_{n - 1} \\ c_{n - 1} + b & = c_{n} \end{aligned}$
命題1より、各行で等式の約数は保存されたまま推移するので
$gcd (a, b) = gcd (b, c_{n})$
各行の等式を辺々足して整理すると
$c_{n} = a + n b$
これを先の式に代入して
$gcd (a, b) = gcd (a + n b, b)$

$n < 0$ のときは、等式の $+$ を $-$ に変えて同様の議論をすると示すことができる。

除法の原理

整数 $a$ 、 $b$ に対して
$a = b q + r 0 \leq r < | b |$
なる整数 $q$ 、 $r$ が一意に存在する。

整除法における最大公約数の保存

整数 $a$ を $b$ で割った、商を $q$ 、あまりを $r$ とすると
$a = b q + r$
このとき
$gcd (a, b) = gcd (b, r)$
が成立する。

与式を変形すると
$r = a - b q$
命題2より
$gcd (a, b) = gcd (a - q b, b) = gcd (r, b)$

互除法の証明

ユークリッドの互除法

$a > b$ である自然数 $a$ 、 $b$ について商とあまりを求める(商を $q$ 、あまりを $r$ とする)。
$a = b q + r$
算出された商 $q$ にとあまり $r$ について、さらに商とあまりを求める。
同様の操作を繰り返すと、最終的なあまりは $gcd (a, b)$ と一致する。

除数を被除数に、あまりを除数にして割り算を繰り返す。
いわゆるユークリッドアルゴリズムを実行する。
$\begin{aligned} a & = b q_{1} + r_{1} \\ b & = r_{1} q_{2} + r_{2} \\ r_{1} & = r_{2} q_{3} + r_{3} \\ ⋮ \\ r_{k - 2} & = r_{k - 1} \cdot q_{k} + r_{k} \\ ⋮ \\ r_{n - 3} & = r_{n - 2} \cdot q_{n - 1} + r_{n - 1} \\ r_{n - 2} & = r_{n - 1} \cdot q_{n} + 0 \end{aligned}$
命題4より
$gcd (a, b) = gcd (b, r_{1}) = gcd (r_{1}, r_{2}) = \dots = gcd (r_{k - 1}, r_{k}) = \dots$
また

$b > r_{1} > r_{2} > \dots > r_{k - 1} > r_{k} > \dots$

$gcd (a, b) = g$ とおくと、あまりの推移はこんな感じ

$b^{'} \cdot g > r_{1}^{'} \cdot g > r_{2}^{'} \cdot g > \dots > r_{k - 1}^{'} \cdot g > r_{k}^{'} \cdot g > \dots$

$r_{k}$ は「 $g$ の倍数」という条件を保ったまま小さくなっていく。
あまりは $0$ 以上であり、下限があるのでアルゴリズムが無限に続くことはない。
また $r_{k} > 0$ である限りアルゴリズムは継続するので、
最終的に、互除法のアルゴリズムはあまりが $0$ になって停止する。
このとき
$gcd (a, b) = gcd (r_{n - 1}, 0)$
したがって
互除法が停止する直前のあまり $r_{n - 1}$ は $gcd (a, b)$ である。

おわりに

最後のあまりが $g$ になることが納得しきれない時期がありました。
「 $0$ 以上の $g$ の倍数」という条件を保ったまま小さくなっていくとして
必ず $g$ を経由するのか、 $r_{n - 1} = 2 g$ とかになるケースはないのか、みたいな。
議論の正確さにはあまり自信がないので、間違いがあればご指摘お願いします。

投稿日：2023年10月21日

更新日：2024年6月6日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

tanu

18958

他の人のコメント

コメントはありません。

読み込み中

tanu

ユークリッドの互除法（証明）

はじめに
準備
互除法の証明
おわりに