ax+by=c型1次不定方程式（ユークリッドの互除法の利用）

基本的な$ax+by=c$型の不定方程式の扱いについては,\ 別項で詳しく述べた. 　　特殊解さえ見つけることができれば,\ 後は機械的に整数解を求められるのであった. 　　本項では,\ $a,\ b$の値が大きく,\ 単純には特殊解が見つからないタイプを取り扱う. 　　$a,\ b$の値が大きくても,\ 確実に特殊解を見つけることができる方法が次である. $aとbの最大公約数をユークリッドの互除法で求める過程を逆に辿る.$} 　　これについては,\ 実際に問題を解きながらでなければ理解することができないだろう. 　　本項では,\ 次の整数分野の最重要定理をとりあえず認めるものとする(証明は別項). $a,\ b$を0でない整数とする. 　$a,\ bが互いに素}\ ⇔\ ax+by=1を満たす整数x,\ yが存在する$ 初学者の多くは,\ この暗号のような解答を見てかなり戸惑うことだろう. 本問で最も大事なことは,\ 理解ではなく反復練習による慣れ}である. 他人が作成した解答をただ見ているだけでは,\ いつまでたっても習得することができない. とにかく,\ まずは紙の上で自分の手を動かしてみることである. 結局同じことを繰り返しているだけで,\ 大したことはやっていないことに気付く. 人にもよるが,\ 多くても5\,～\,10問程度やれば当初思っていたよりは楽に習得できるはずである. 改めて確認すると,\ 当面の目的は52x+19y=1を満たす整数(x,\ y)の組を1つ求めることである. 係数が52,\ 19と大きいので,\ 勘だけで見つけることは困難である. そこで,\ 何とかして52･○+19･□=1\ (○,\ □は整数)の形の式を作成することを考える. この式は,\ 52と19の最大公約数をユークリッドの互除法で求める過程を逆に辿る}と作成できる. まず,\ 最大公約数を求めるときと同様にして,\ 余りが1になるまで割り算を繰り返す.} a,\ bが互いに素のとき,\ 必ずいつかは余りが1になる理由を簡単に示しておく. a=bq+rという式に対して,\ g(a,\ b)=g(b,\ r)が成り立つのであった(互除法の原理). a,\ bに対してユークリッドの互除法を適用する.\ 4回目で割り切れたとすると以下のようになる. なお,\ g(a,\ b)はaとbの最大公約数のことである. a,\ bが互いに素のとき,\ g(a,\ b)=1である. つまり,\ a,\ bが互いに素のとき,\ 割り切れる直前の余り(ここではr_3)は必ず1になる. 次に,\ すべての式を=(余り)の形に書き換える}(①\,～\,④). その後,\ 大まかな流れは,\ ④に③を代入して整理,\ ②を代入して整理,\ ①を代入して整理}である. このようにして逆に辿っていくと,\ 52･○+19･□=1の形が出来上がる. ④の4に③をそのままの形で代入し,\ 展開すると　5-14･1+5･2=1 このとき,\ 5-14+10=1のようにすべての積を計算してしまってはならない. 積の形のまま,\ 5･3-14･1=1と整理する. 同じことを①を代入するところまで繰り返していくと,\ 52と19で整理できる. 必要ならば,\ 問題の式と同じ形になるように変形して,\ 特殊解が求められる. 特殊解さえ求まれば,\ 後は基本的なax+by=c型の不定方程式と同様にして一般解を求めればよい. 元の式から特殊解を代入した式を引いて一方を移項すると,\ aX=bY\ (a,\ b:互いに素)}に帰着. a,\ bは互いに素であるから,\ Xはbの倍数,\ Yはaの倍数である. よって,\ X=bk,\ Y=ak\ (k:整数)}\ と求められる. 記述試験では,\ 特殊解を求める過程を答案に書く必要はない. 整数解を求めよというだけならば,\ いきなり52(x+4)=-\,19(y-11)から書いても問題ない. 本解がどうしてもわかりにくいという人には,\ わかりやすい別解がある. しかし,\ 問題で誘導されることもあるので,\ 標準解法である本解の方法に慣れておくべきである. a,\ bのうち大きい方を小さい方で割った式を代入して整理し,\ 括弧内を別の文字で置き換える.} すると,\ より係数が小さい不定方程式に帰着するので,\ 特殊解が求まるまで繰り返す.} 本質的には本解と同じだが,\ 文字を用いることで視覚的にわかりやすくなる. また,\ 逆に辿った本解とは異なり,\ 順番に変形していけるのもわかりやすい. さらに,\ 特殊解が求まるところでやめてよく,\ 限界まで繰り返す必要がないというメリットもある. 14x+19s=1\,で(x,\ s)=(-\,4,\ 3)などの特殊解に気付けるならば,\ それ以上変形する必要はない. まだ少し難しいので,\ 今回はもう一段階係数を小さくした. 一方の係数が一桁になれば,\ 特殊解は割と容易に見つかるはずである. ax+by=cは,\ 0≦ x≦ b-1\ \dot{ま}\dot{た}\dot{は}\ 0≦ y≦ a-1\ を満たす特殊解を必ず1組もつのであった. 5s+14t=1の0≦ t≦5-1を満たす特殊解を探すと,\ (s,\ t)=(-\,11,\ 4)を見つけることができる. s,\ tが求まれば,\ 2x+y=s,\ x+s=t\,より,\ 52x+19y=1の特殊解も求まる. ax+by=cでcの値が大きい場合,\ ax+by=1の特殊解を求めてc倍する}とよいのであった. (1)の特殊解を15倍すると本問の特殊解が求められる. (1)を利用しない別解も示した. (1)と同様にユークリッドの互除法を逆に辿ることになるが,\ =1になるまで繰り返す必要はない. 15=5･3を考慮すると,\ =5になった時点から逆に辿れば十分である. 不定方程式$52x+19y=1$には自然数解($x,\ yともに自然数$)が存在しないことを示せ. \\ 　　これを満たす整数$k$は存在しない.} 　　よって,\ $52x+19y=1}$の自然数解は存在しない.} ax+by=cの応用問題では,\ 整数解を普通に求め,\ その後で追加条件を考慮する}とよいことが多い. x=-\,19k-4,\ y=52k+11より,\ 1つの整数kの値に対応して1つの(x,\ y)の値が定まる. つまり,\ 整数kの個数と整数解(x,\ y)の組数は一致する.} よって,\ 本問の場合,\ 条件を満たすkが0個であることを示せばよい. となる整数kは存在しない.