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

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

Copyright (C) virtual_high_school, 2015


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



上のExcelファイルをダウンロードするにはここをクリック




【1】 連分数を使う方法

『ガウス整数論』(邦訳本 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】 婆茶留高校推奨の方法
上記の方法にヒントを得て開発したアルゴリズムがこれである。(当サイトの「不定方程式の特殊解」参照。)





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

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



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



(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 が特殊解である。

【4】 銀林浩『初等整数論入門』(ちくま学芸文庫)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 をたすき掛けすれば特殊解である。


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