[婆茶留高校数学科☆HP] Top pageに戻る このページを閉じる

不定方程式ax+by=dの特殊解の求め方(互除法による)

Copyright (C) virtual_high_school, 2017

音声入り動画による説明


YouTubeにアップした動画
https://www.youtube.com/watch?v=PHimwyuja9E


パラパラ・マンガによる説明
パラパラまんが

自然数a と b に対し、その最大公約数を d とするとき
   $ ax+by=d $
の特殊解$x,y $の求め方。

アルゴリズム
まず、ユークリッドの互除法で2数の最大公約数(dになるわけだが)を求める。
その求め方は、別のページ http://www.virtual-hs.com/math/keisan011.html に書いた。
そうすると、割り算の上辺に商の列(左から) $ q_{1}, q_{2}, q_{3},\cdots, q_{n}$ が並ぶ。
この商に列に対して、以下のアルゴリズムを実行する。

  1. $q_{1}$ を 1 に置き換える。(これを「最初はグー」でなく「最初は1」と覚える。)
    すなわち $q_{1} :=1$
  2. 商の列の最も左にある3数に対し、たし算とかけ算を行う。すなわち
    $ q_{1} + q_{2} \times q_{3}$ を計算し、$q_{3}$ をこの数で置き換える。すなわち
    $q_{3} := q_{1} + q_{2} \times q_{3}$
  3. 「商の列の最も左にある3数」というのをすべて一つ右隣の数で置き換える。
    すなわち $ q_{3} := q_{i+3}, q_{2} := q_{i+2}, q_{1} := q_{i+1}$
  4. 2. に戻って、繰り返す。いつまで繰り返すかというと、「商の列の最も左にある3数」が一つずつ右にずれていって、$ q_{n-2}, q_{n-1}, q_{n}$ に到達するまでである。

商の列の、最後と最後から2番目の数$ q_{n-1}, q_{n}$ が特殊解から符号を除いたものである。
a,b とたすき掛けを行うと、
   $ a \times q_{n-1} - b \times q_{n} = \pm 1$
になるので、
   (ア) 1 ならば $x=q_{n-1},y=-q_{n}$
   (イ) -1 ならば $x=-q_{n-1},y=q_{n}$
が特殊解になる。


★「婆茶留高校」は架空の存在であり、実在の人物、団体とは関係ありません。
<-- クリックして婆茶留高校へメール送信 mailto: virtual_h_s@yahoo.co.jp 
婆茶留高校数学科HP http://www.virtual-hs.com/ Powered by   Copyright(c) virtual_high_school, 2001-2022