不定方程式の整数解を見つける方法

前ページ \(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\)