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

Copyright (C) virtual_high_school, 2017

【音声入り動画による説明】


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

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

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

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

商の列の、最後と最後から２番目の数$ 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}$
が特殊解になる。