2元1次不定方程式 ax+by=c の整数解

最も基本的なものは以下で扱っているので、本項ではやや応用的なものを取り上げる。

cの値が大きいときの}$特殊解の見つけ方    ${ax+by=1の特殊解(p,\ q)を求め,\ {両辺をc倍する.$    ${a(cp)+b(cq)=c\ と考えると {特殊解(cp,\ cq)$  $$${a,\ bの値が大きいときの}$特殊解の見つけ方    ${除法による係数下げを繰り返し,\ 係数が小さい方程式に帰着させる. 5x+7y=1\ の整数解を1つ探して131倍すると,\ 5x+7y=131\ の整数解となる. ここでは,\ 5x+7y=1\ の整数解を\ (x,\ y)=(-4,\ 3)\ として計算した. (x,\ y)=(3,\ -2)\ など,\ 無数にあるので最初に見つけたものでよい. 下に示したように,\ 元の式から見つけた整数解を代入した式を引く. 一方を移項すると,\ {aX=bY\ (a,\ b:互いに素)}\ に帰着する. a,\ bが互いに素であるから,\ Xはbの倍数,\ Yはaの倍数である. よって,\ {X=bk,\ Y=ak\ (k:整数)}\ とおいて解けばよい. {ax+byのa,\ bの大きい方を小さい方で割る.} 5319=215\ を除法に関する等式で表すと 53=192+15 これを代入して,\ 19を因数にもつ部分をまとめ,\ 文字で置き換える. すると,\ より係数が小さい方程式\ 15x+19a=1\ に帰着する. {余りが必ず割る数より小さくなる}ことを利用するわけである. これを繰り返し,\ {特殊解が求まるくらいまで係数を小さくする.} 15x+19a=1で整数解が見つかればそれでよいが,\ ここではさらに係数を下げた. 4a+15b=1\ の整数解は割と容易に見つかる. 後は,\ 2x+y=a,\ 15x+19a=1,\ x+a=bで,\ 53x+19y=1の整数解が求まる.
タイトルとURLをコピーしました