検索用コード
この型は,\ 整数分野の最重要テーマの1つであり,\ 非常に奥深い理論がある. \\  ここでは,\ 単なる不定方程式の1つと考え,\ 解を求める手順だけを確認する. \\\\  まず,\ 「$\bm{\textcolor{blue}{aX=bY型\ (a,\ bは互いに素)}}$」の解法を確認する. \\ aとbが互いに素\ (\pm1以外の共通の約数を持たない)}}がポイントになる.$ \\  最も簡単な例として,\ $\bm{\textcolor{magenta}{2X=3Y}}の解を考えてみよう.$ \\  この等式が成立するには,\ $Xは3の倍数,\ Yは2の倍数でなければならない.$ \\  これらは無数あるので,\ $\bm{\textcolor{magenta}{X=3k,\ Y=2k\ (k:整数)}}\ と答えることになる.$ \\\\\\  次は整数分野で最も重要な定理の1つである.\ $a,\ b,\ x,\ yは整数とする.$ \\[.3zh] \centerline{$\bm{「\textcolor{red}{a,\ bが互いに素であるとき,\ ax+by=1を満たすx,\ yが存在する}」}$} \\[.3zh]  証明も重要だが,\ ここで扱う余裕がないので,\ とりあえず認めて欲しい. \\  これは,\ (1)のような不定方程式は,\ 必ず整数解を持つことを意味している. \\  さらに,\ $\bm{\textcolor{cyan}{ax+by=1の両辺をc倍}}すると,  よって,\ $\bm{\textcolor{red}{aX+bY=c型も,\ 必ず整数解(cx,\ cy)を持つ}}といえる.$ \\  なお,\ $a,\ bが互いに素ではない場合,\ 解が存在するとは限らない.$ \\  例えば,\ $4x+6y=1は,\ 2(2x+3y)=1であり,\ (偶数)=1より矛盾である.$ \\\\\\  以上を踏まえて,\ $\bm{\textcolor{blue}{ax+by=c型\ (a,\ bは互いに素)の解法}}$を確認する. \\  まず,\ \textbf{\textcolor{red}{何とかして整数解を1組見つける.}}\ 上の定理で存在は保証されている. \\  難しそうに思われるが,\ 実は次の事実がある.\ 証明抜きで認めて欲しい. \\  必ず$\bm{\textcolor{cyan}{0\leqq x\leqq b-1または0\leqq y\leqq 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組の整数解を\textcolor{cyan}{(\alpha,\ \beta)}とする.$ \\  次のように,\ $\bm{\textcolor{red}{元の式から,\ (x,\ y)に(\alpha,\ \beta)を代入した式を引く.aX=bY型に帰着.}}    特殊解型の漸化式の解法と同様の手法であり,\ この$(\alpha,\ \beta)$も\textbf{\textcolor{cyan}{特殊解}}という. \\  引き算の筆算は,\ 答案に書かなてくもよい(別に書いても何ら問題はない). 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ですら特殊解が見つけにくい場合の対処法はここでは扱わない.