ここでは ax+by=c型の不定方程式 の応用問題を取り扱う。

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