もう一人のY君

読者です 読者をやめる 読者になる 読者になる

もう一人のY君

iPhoneアプリのレビューやアップデートレビューなどを書いています. たまに数学の記事も書きます.

もう一人のY君 MENU

拡張ユークリッドのアルゴリズム

数学

スポンサーリンク


 こんにちは, @the_theorierです.

 

 時間が出来たので拡張ユークリッドも書いていこうと思います.

 

 130222_03

  昨日の通りで, 2つの正整数 a, b を使って a = bq + r と分解する行為を繰り返すことで, a, b の最大公約数を得るのがユークリッドの互除法でした.

 

thetheorier.hatenablog.com

 

  拡張ユークリッドではここで使った式変形を利用します.

 

 上にある式たちを, 最後だけ除いてすべて r = ~ の形にします.

 

 130222_04

  こんな感じです.

 

 ここで右側の最後の式を, その上の式に代入して整理します.

 

{ \displaystyle r_{n} = r_{n-2} + \{ r_{n-3} + r_{n-2} (-q_{n-1})\}\times (-q_{n}) }

{ \displaystyle ⇔ r_{n} = r_{n-3}(-q_{n-1}) + r_{n-2}(1+q_{n-1}q_{n}) }

 

 余りの列 { \displaystyle r_{n} } を変数, { \displaystyle q_{n} } を定数と見做して扱うのがポイントです.

  ここで

 

{ \displaystyle A = -q_{n-1} }

{ \displaystyle B = 1+q_{n-1}q_{n} }

 

とでも置けば, 二つはやはり定数であり, 上の等式は

 

 { \displaystyle r_{n} = r_{n-3}A + r_{n-2}B }

 

と書けます.

 

  はじめの { \displaystyle r_{n} = r_{n-2} + r_{n-1}(-q_{n}) } の時点では, { \displaystyle r_{n} } は「{ \displaystyle r_{n-2} } と { \displaystyle r_{n-1} } の線形和」で表されていますが, 上では「{ \displaystyle r_{n-3} } と { \displaystyle r_{n-2} } の線形和」で表されていますね.

 

  同じことを今度は最後から3つめの式を代入すれば, 今度は { \displaystyle r_{n-3} } と { \displaystyle r_{n-2} } の線形和になることはもう明らかです.

 

  これをどんどん繰り返せば, 最終的に a と b の線形和になるわけです, つまりある定数 { \displaystyle x_{0}, y_{0} } が存在して

 

{ \displaystyle ax_{0} + by_{0} = r_{n} }

 

 となるわけです.

  この { \displaystyle x_{0}, y_{0} } の組は一次不定方程式 { \displaystyle ax + by = r_{n} } の解の一つに他なりません, 一般的にこのようにして得られた解は「特殊解」と呼ばれます.

 

  あとは一般解を求めるだけです, つまり特殊解は元々の不定方程式の解の一つですから, 

{ \displaystyle ax_{0} + by_{0} = r_{n} }

 を満たしています.

  これと元の一次不定方程式 { \displaystyle ax + by = r_{n} } から辺々引いて整理すると,

 

{ \displaystyle (ax + by) - (ax_{0} + by_{0}) = r_{n} - r_{n} }

{ \displaystyle ⇔ a(x - x_{0}) + b(y - y_{0}) = 0 }

{ \displaystyle ⇔ a(x - x_{0}) = b(y_{0} - y) }

 

 …となりますね.

  これはつまり,

 

  • { \displaystyle x - x_{0} } は b の倍数
  • { \displaystyle y_{0} - y } は a の倍数

 

 を意味しています, 従って上の2つは整数 k を用いて

 

{ \displaystyle x - x_{0} = bk }

{ \displaystyle y_{0} - y = ak }

 

と書きかえることができます, これを整理して

 

{ \displaystyle x = bk + x_{0} }

{ \displaystyle y = -ak + y_{0} }

 

となります, { \displaystyle x_{0}, y_{0} } は特殊解だったのでなんらかの定数です.

 

 こうして特殊解 { \displaystyle (x, y) = (x_{0}, y_{0}) } から一般解 { \displaystyle (x, y) = (bk+x_{0}, -ak+y_{0}) } を得ることが出来ました.