不定方程式の特殊解の求め方いろいろ

Copyright (C) virtual_high_school, 2015

不定方程式、例えば　105 x + 38 y = 1 (係数は互いに素) を満たす整数解 x , y を1組(特殊解と言う)求める方法にはいろいろあるので、それらを紹介しよう。
いずれの方法もまずユークリッドの互除法で、商の系列 { 2, 1, 3, 4, 2 } を求める。

上のＥｘｃｅｌファイルをダウンロードするにはここをクリック。

【１】 連分数を使う方法
『ガウス整数論』(邦訳本 p. 20) に紹介されている方法である。
(1) 互除法の結果から、分数 38/105 は次のように連分数表示される。

(2) 連分数の中で最後に出てくる分数 (今の例だと 1/2 ) を 0 とおいて

のように分数に戻して、17/47 を得る。
(3) 解は 38/105 と 17/47 のたすき掛けになる。
　　　105 × 17 = 1785,
　　　38 × 47 = 1786
なので、17 の方に負号を付けて
　　　x = -17, y = 47
が特殊解となる。

【２】 婆茶留高校推奨の方法
上記の方法にヒントを得て開発したアルゴリズムがこれである。(当サイトの「不定方程式の特殊解」参照。)

商の系列を逆順に見て、 { 2, 4, 3, 1, 2 } に対し、次の作業を施す。
(1) 「はじめはイチ」、すなわち 最左端の数字（今の場合 2） は必ず 1 に書き換える。(赤丸で囲った数字が書き換えた数字である。)
(2) あとは「たし算とかけ算で右に進む」、すなわち
　　　1 ＋ 4 × 3　＝ 13,
　　　4 ＋13 × 1 ＝ 17,
　　　13 ＋17× 2 ＝ 47
(3) 38, 105 と、その真上にある赤丸数字の 17, 47 をたすき掛けすれば特殊解が得られる。

【３】 一松信『数の世界』(丸善出版サイエンス・パレット)p.73 の方法

本稿冒頭で紹介したＥｘｃｅｌファイルはこれを元にしたものです。このファイルを見るにはここをクリック。

(1) x の列には右から 1, 0 を書き込み、y の列には右から 0, 1 を書き込む。
(2) あとは右から左へ向かって数列を計算する。その方法は例えば青い部分を取り上げて説明すると
　　　1 − (-1) × 3 ＝ 4
のように引き算とかけ算で、順次左の数字を求めていくのである。逐次すべて述べると、
x の数列は
　　　1 - 0 × 2 = 1,
　　　0 - 1 × 1 = -1,
　　　1 - (-1) × 3 = 4 (上に取り上げて説明した),
　　　-1 - 4 × 4 = -17.
y の数列は
　　　0 - 1 × 2 = -2,
　　　1 - (-2) × 1 =3,
　　　-2 - 3 × 3 =-11,
　　　3 - (-11) × 4 = 47.
(3) 最後のx, y が特殊解である。

【４】 銀林浩『初等整数論入門』(ちくま学芸文庫)p.69〜74 の方法

(1) p の列には右から 1 と最初の商(今の場合は2) を書き込み、q の列には右から 0 と 1 を書き込む。
(2) あとは右から左へ向かって数列を計算する。その方法は例えば青い部分を取り上げて説明すると
　　　4 × 11 + 3 ＝ 47
のようにかけ算とたし算で、順次左の数字を求めていくのである。逐次すべて述べると、
p の数列は
　　　1 × 2 + 1 = 3,
　　　3 × 3 + 2 = 11,
　　　4 × 11 + 3 = 47 (上に取り上げて説明した),
　　　2 × 47 + 11 = 105.
q の数列は
　　　1 × 1 + 0 =1,
　　　3 × 1+ 1 = 4,
　　　4 × 4 + 1 = 17,
　　　2 × 17 + 4 = 38.
(3) 最左端の2列の4つの数字105, 38 と 47, 17 をたすき掛けすれば特殊解である。