こんにちは, @the_theorierです.
時間が出来たので拡張ユークリッドも書いていこうと思います.
昨日の通りで, 2つの正整数 a, b を使って a = bq + r と分解する行為を繰り返すことで, a, b の最大公約数を得るのがユークリッドの互除法でした.
拡張ユークリッドではここで使った式変形を利用します.
上にある式たちを, 最後だけ除いてすべて r = ~ の形にします.
こんな感じです.
ここで右側の最後の式を, その上の式に代入して整理します.
余りの列 を変数, を定数と見做して扱うのがポイントです.
ここで
とでも置けば, 二つはやはり定数であり, 上の等式は
と書けます.
はじめの の時点では, は「 と の線形和」で表されていますが, 上では「 と の線形和」で表されていますね.
同じことを今度は最後から3つめの式を代入すれば, 今度は と の線形和になることはもう明らかです.
これをどんどん繰り返せば, 最終的に a と b の線形和になるわけです, つまりある定数 が存在して
となるわけです.
この の組は一次不定方程式 の解の一つに他なりません, 一般的にこのようにして得られた解は「特殊解」と呼ばれます.
あとは一般解を求めるだけです, つまり特殊解は元々の不定方程式の解の一つですから,
を満たしています.
これと元の一次不定方程式 から辺々引いて整理すると,
…となりますね.
これはつまり,
- は b の倍数
- は a の倍数
を意味しています, 従って上の2つは整数 k を用いて
と書きかえることができます, これを整理して
となります, は特殊解だったのでなんらかの定数です.
こうして特殊解 から一般解 を得ることが出来ました.