不定方程式の特殊解

Copyright (C) virtual_high_school, 2015

【要約】
整数$a, b$ の最大公約数を$d$とするとき、不定方程式

                            $ax+by=d$

を満足する整数解$x,y$が無数組存在し、そのうちの1組の解(特殊解)をユークリッドの互除法により求めることができる。そこで、特殊解の求め方(アルゴリズム)を紹介する。

【例題】
$x,y$の係数の最大公約数を$d$とするとき、

                            $106128x+13520y=d$

の整数解$x,y$を1組求めよ。

【解】

【1】  ユークリッドの互除法を実行する。(下図はExcelを使用)互除法のExcelファイル(Download)

【2】 商の列 4, 1, 7, 1, 1, 1, 5, 1, 7 に対し、以下のアルゴリズムを実行する。

 商を左から右へ見ていく。
(1)　一番左の商 "4" の真上に ① と書く。
(2)　a, b, c に対し、a＋b×c を計算し、c の真上に○数字で書く。
(3)　あとは(2)の繰り返し。(○数字があるときはそれを利用する。)

右側2つの商 13520, 106128 の真上の○数字 173, 1358 をたすき掛けしたものが解になる。 

 【3】 たすき掛けにはα(アルファ)型とχ(エックス)型があるが、どちらになるかは商の個数によって決まる。

 A. 商の個数が奇数個のときα型(αの書き順に注意)

B. 商の個数が偶数個のときχ型(χの書き順に注意) 

【4】 実際には、たすき掛けを実行してみて、どっちからどっちを引くと d になるかを考えるのが簡明。

今の例題だと、商の個数＝9(奇数)なので
ア＝ 1358 × 13520 = 18360160
イ＝ 173 × 106128 = 18360144

だから、ア－イ＝ 16 (= d) である。
よって
106128×(-173) + 13520 × 1358 = 16  (= d)

これは

x = -173, y = 1358　……(答)

であることを意味する。

【本アルゴリズムが正しいことの証明】

 このアルゴリズムを発見したのは、ラグランジュ(フランス人、18世紀)である。
証明は、商の個数(左側から個数を数える)についての数学的帰納法による。
証明に先立って、商の個数が1個のときは解は簡単に求まって、本アルゴリズムは必要でないことを述べよう。

【０】 商の個数＝1のとき

$GCM=b$だから$0a+1b=d$で特殊解は$x=0,y=1$である。

【１】 商の個数＝2のとき

$a-bq_{2}=d$だから$1a+(-q_{2})b=d$で特殊解は$x=1,y=-q_{2}$である。

【２】 商の個数＝$k(k \geq 2)$のとき成り立つと仮定すれば、商の個数＝$k+1$のときに成り立つことを示す。

仮定より$x_{0}b-y_{0}c=\pm 1$であり、$a-bq_{3}=c$だから、
$y_{0}a-(x_{0}+y_{0}q_{3})b= y_{0}(bq_{3}+c)-(x_{0}+y_{0}q_{3})b=y_{0}c-x_{0}b =\mp 1$
よって$x=\pm y_{0}a,y= \mp (x_{0}+y_{0}q_{3})$である。

【注】
上記以外にも特殊解を求める方法がある。例えば、一松信著『数の世界-概念の形成と認知-』丸善出版,サイエンス・パレット,2015 のp.73参照。