不定方程式の整数解を見つける方法
前ページ \(2\) つで不定方程式の整数解の求め方について、ほぼすべてを説明しました。
さらに詳しく学習して、周辺を固めておきましょう。
互除法を使わないで、サクッと整数解が見つかるケースもありうる、そんな話です。
実際に、センター試験においても出題されています。
例題１
不定方程式 \(19x-13y=1\) の整数解を求めなさい。
解説
もちろん互除法による解法を使えば解決します。
このページでは、互除法を使わないで整数解を見つける方法についてをテーマとしています。
書き出しで探す
まずは不定方程式の整数解の性質についての復習です。
例えば、\((x,y)=(a,b)\) という整数解が見つかったとします。
このとき、一般解は、
\(x=13t+a\)
\(y=19t+b\)
となります。
この式の意味するところですが、
\(x\) は \(13\) で割ったときの余りが \(a\) になる数
だということです。
これは、
\(x\) は \(0,1,2,\cdots\) とあてはめで調べていったときに、\(12\) まで調べれば
確実に答えが見つかる！
ということです。
よって最大 \(13\) 回調べれば解決するのです。
さらにテクニックを授けます。
\(x\) に \(0,1,2,\cdots,12\) とあてはめて調べるのではなく、
\(x\) に \(-6,-5,-4,-3,-2,-1\)\(,0,1,2,3,4,5,6\) とあてはめて調べます。
積は数が小さい方が計算が圧倒的に楽ですからね。
互除法とどっちがはやいでしょうか？
どっちもどっちというところでしょうか。
実際に書き出しで調べると
\(19x=13y+1\) なので、
\(19\) の倍数で、\(13\) の倍数 \(+1\) になっているものを探します。
\(19,38,57,76,95,114,\cdots\) と \(19\) の倍数は続きます。
\(13,26,39,\cdots\) と \(13\) の倍数は続きます。
差が \(1\) になっているものが見つかりましたね。
\(38\) と \(39\) です。
\(19\) の倍数で、\(13\) の倍数 \(+1\) を満たす数が欲しいのに、
\(19\) の倍数で、\(13\) の倍数 \(-1\) を満たす数が見つかった。
このようなときは、符号をマイナスにすれば解決します。
\(19×(-2)=-38\)
\(13×(-3)=-39\)
よって、 \(19×(-2)-13×(-3)=1\) という解が見つかりました。
もちろん、
\(-2+13=11\)
\(-3+19=16\)
より、\(19×11-13×16=1\) も成り立ちます。
※\(19×11=209\)、\(13×16=208\)
よって、\(t\) を整数として
\(x=13t+11\)
\(y=19t+16\)
と整数解が求まります。
もちろん、\(t\) を整数として
\(x=13t-2\)
\(y=19t-3\)
でも可です。
倍数とあまりに着目
倍数と余りの性質を使う方法もあります。
\(x,y\) の係数で、絶対値が小さい方に直目します。
\(19x-13y=1\)
この式ですが、 \(13\) の倍数を基準として式をかき直します。
\(19x=13x+6x\) なので、\(19x-13y=1\) は、
\(13x+6x-13y=1\)
つまり、
\(13(x-y)+6x=1\)
右辺の \(1\) ですが、\(13×0+1\) のことなので、
\(13\) の倍数 \(+1\) です。
つまり、左辺も \(13\) の倍数 \(+1\) のとき式が成立するので、
\(6x\) が \(13\) の倍数 \(+1\) になるときです。
あとは、\(6\) の倍数の中から、該当するものを探します。
\(6,12,18,24\cdots\)
と探していき、
\(6x=66=13×5+1\)
があっさりと見つかります。
より、\(x=11\) のときに成立します。
この方法は数値が小さいものを調べればいいので、かなりおススメです。
\(x=11\) のとの \(y\) は、
\(19×11-13y=1\)
から計算して求めても良いのですが、
\(13(x-y)+6x=1\)
を使うとより計算が楽です。
\(x=11\) のとき、
\(13(11-y)+\)\(66\)\(=1\)
\(13(11-y)+\)\(13×5+1\)\(=1\)
より、\(11-y=-5\)
\(y=16\)
と求まります。
例題２
不定方程式 \(139x+11y=1\) の整数解を求めなさい。
解説
\(x\) は \(0\) から \(10\) まで調べれば必ず見つかりますが・・・
値が大きいので計算が面倒ですね。
※もちろん、\(-4\) ～\(5\) で探す方が楽です。
こんなときは、「互除法」でも良いのですが、先ほどの「倍数とあまり」による探索
もおススメです。
\(11\) を基準にかき直すと
\(132x+7x+11y=1\)
\(11(12x+y)+7x=1\)
つまり、\(7x\) が \(11\) の倍数 \(+1\) になればよい。
\(7x=56=11×5+1\)
がすぐに見つかりますね。
よって、\(x=8\)
これを、\(11(12x+y)+7x=1\) に代入すると、
\(11(12\cdot8 +y)+7\cdot8=1\)
\(11(96+y)+\)\(56\)\(=1\)
\(11(96+y)+\)\(11\cdot 5+1\)\(=1\)
よって、\(96+y=-5\)
\(y=-101\)
よって、\(t\) を整数として
\(x=11t+8\)
\(y=-139t-101\)
と整数解が求まります。
例題３
不定方程式 \(179x+37y=1\)の整数解を求めなさい。
解説
\(x\) は \(0\) から \(36\) まで、
\(y\) は \(0\) から \(178\) まで調べれば必ず見つかりますが・・・
値が大きいので計算が面倒ですね。
かなり運が良くないと、計算地獄になりそうです。
こんなときは、間違いなく「互除法」です。
迷いなく互除法を選択しましょう。
互除法による解法
\(179÷37=4\cdots31\)
\(37÷31=1\cdots6\)
\(31÷6=5\cdots1\)
上から式をかき直すと
\(31=179-37×4\)
\(6=37-31\)
\(1=31-6×5\)
\(1=31-6×5\) の \(6\) に、 \(6=37-31\) を代入して、
\(1=31-(37-31)×5\)
\(1=31×6-37×5\)
\(1=31×6-37×5\) の \(31\) に、\(31=179-37×4\) を代入して、
\(1=(179-37×4)×6-37×5\)
\(1=179×6-37×29\)
よって、整数解が \(1\) つ見つかりました。
\((x,y)=(6,-29)\) です。
よって、\(t\) を整数として
\(x=37t+6\)
\(y=-179t-29\)
と整数解が求まります。
参考・倍数とあまりに着目
倍数とあまりに着目して解くとどうなるか。
参考にどうぞ。
\(x,y\) の係数で、絶対値が小さい方に直目します。
\(179x+37y=1\)
この式ですが、 \(37\) の倍数を基準として式をかき直します。
\(179x=37\cdot4 x+31x\) なので、\(179x+37y=1\)は、
\(37\cdot4 x+31x+37y=1\)
\(37(4x+y)+31x=1\)
このまま解き進めるならば、
\(31x\) が \(37\) の倍数 \(+1\) になるときを探します。
\(2\) 桁になるとちょっと面倒です。
そこで。
はじめにもどります。
\(179x+37y=1\)
を、
\((185x-6x)+37y=1\)
とします。
\(185=37×5\) です。
\((37×5x-6x)+37y=1\)
\(37(5x+y)-6x=1\)
\(37(5x+y)=6x+1\)・・・①
よって、
\(37\) の倍数の中から、\(6\) の倍数 \(+1\) となっているものを探します。
本問は数値設定のおかげですが、あっさり見つかりますね。
\(37=6×6+1\) です。
つまり、\(x=6\)
①式に、\(x=6\) を入れて \(y\) を求めましょう。
\(37(5x+y)=6x+1\)・・・①
\(37(5\cdot6+y)=36+1\)
より、\(30+y=1\)
\(y=-29\)