基本的なax+by=c型の不定方程式(aX=bY型の不定方程式)

この型は,\ 整数分野の最重要テーマの1つであり,\ 非常に奥深い理論がある.  ここでは,\ 単なる不定方程式の1つと考え,\ 解を求める手順だけを確認する.  まず,\ 「${aX=bY型\ (a,\ bは互いに素)$」の解法を確認する. aとbが互いに素\ (1以外の共通の約数を持たない)がポイントになる.$  最も簡単な例として,\ ${2X=3Yの解を考えてみよう.$  この等式が成立するには,\ $Xは3の倍数,\ Yは2の倍数でなければならない.$  これらは無数あるので,\ ${X=3k,\ Y=2k\ (k:整数)\ と答えることになる.$  次は整数分野で最も重要な定理の1つである.\ $a,\ b,\ x,\ yは整数とする.$ ${「a,\ bが互いに素であるとき,\ ax+by=1を満たすx,\ yが存在する}」}$}  証明も重要だが,\ ここで扱う余裕がないので,\ とりあえず認めて欲しい.  これは,\ のような不定方程式は,\ 必ず整数解を持つことを意味している.  さらに,\ ${ax+by=1の両辺をc倍すると,  よって,\ ${aX+bY=c型も,\ 必ず整数解(cx,\ cy)を持つといえる.$  なお,\ $a,\ bが互いに素ではない場合,\ 解が存在するとは限らない.$  例えば,\ $4x+6y=1は,\ 2(2x+3y)=1であり,\ (偶数)=1より矛盾である.$  以上を踏まえて,\ ${ax+by=c型\ (a,\ bは互いに素)の解法$を確認する.  まず,\ 何とかして整数解を1組見つける.\ 上の定理で存在は保証されている.  難しそうに思われるが,\ 実は次の事実がある.\ 証明抜きで認めて欲しい.  必ず${0 x b-1または0 y a-1を調べると,\ 解が1つ見つかる.$  よって,\ $a,\ bの値の小さい方に着目して1つずつ調べていけばよい.$  例えば,\ $a=3,\ b=5ならば,\ y=0,\ 1,\ 2を代入してみると必ず見つかる.$  $b=5に着目すると,\ x=0,\ 1,\ 2,\ 3,\ 4を代入する必要があり,\ 面倒である.$  こうして1組見つけることさえできれば,\ 次の機械的な作業で解が求まる.  $ax+by=cの1組の整数解を(α,\ β)}とする.$  次のように,\ ${元の式から,\ (x,\ y)に(α,\ β)を代入した式を引く.aX=bY型に帰着.    特殊解型の漸化式の解法と同様の手法であり,\ この$(α,\ β)$も特殊解という.  引き算の筆算は,\ 答案に書かなてくもよい(別に書いても何ら問題はない). 3x-5y=1\ の1組の整数解は y=0,\ 1,\ 2を代入するだけであるから,\ 特殊解はすぐに見つかる. 後は,\ 基本手順に従ってaX=bY型に帰着させるだけである. 整数解の特殊解は  49x+24y=19は,\ 係数の値が大きく,\ 特殊解を見つけることが容易ではない. もちろん,\ x=0~23を代入すると必ず見つかるはずではあるが,\ 相当面倒である. 結果を見る限り,\ (19,\ -38),\ (-5,\ 11),\ (-29,\ 60)等を代入して初めて見つかる. このような場合,\ まずax+by=1の特殊解を求めよう. その後,\ 両辺をc倍することによって,\ ax+by=cの特殊解を作り出せばよい. 49x+24y=1の特殊解ならば,\ 少しカンを働かせると容易に見つかるだろう. ax+by=1ですら特殊解が見つけにくい場合の対処法はここでは扱わない.
タイトルとURLをコピーしました