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

不定方程式の特殊解

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個のときは解は簡単に求まって、本アルゴリズムは必要でないことを述べよう。

【0】 商の個数=1のとき

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

【1】 商の個数=2のとき

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



【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参照。


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