ユークリッドの互除法と1次不定方程式

1次不定方程式の特殊解が見つかりにくい場合は、ユークリッドの互除法を利用することで見つけることができます。

(例題)
方程式 \(73x-26y=3\) の整数解を求めよ。

(解答①)ユークリッドの互除法の利用

係数 \(73\)と\(26\) について互除法を利用します。
\(73\)と\(26\) は互いに素なので、余りが\(1\)になるときがあり、そこが終着点です。互除法を利用する際、\(73=m\), \(26=n\) と文字でおくと、わかりやすいです。

\(73=m\), \(26=n\) とする。

\(73=26×2+21\) より
\(m-2n=21\)

\(26=21×1+5\)より
\(26-21=5\) だから
\(n-(m-2n)=-m+3n=5\)

\(21=5×4+1\)より (←余りが\(1\)になった)
\(21-5×4=(m-2n)-(-m+3n)×4\)\(=5m-14n\) だから
\(5m-14n=1\)

\(73=m\), \(26=n\) を代入すると
\(73×5-26×14=1\)・・・①

①は、\(73x-26y=1\) の特殊解が、\(x=5,y=14\) であることを表しています。もとの方程式は右辺が\(3\)なので①を\(3\)倍します。するともとの方程式の特殊解が\(x=15,y=42\)であることが分かります。あとは普通に解くだけです。

①の両辺を\(3\)倍して
\(73×15-26×42=3\)・・・②
方程式 \(73x-26y=3\)・・・③ で
③－②より
\(73(x-15)-26(y-42)=0\)

\(73(x-15)=26(y-42)\)・・・④ より
\(73\)と\(26\) は互いに素なので
\(x-15=26k\)・・・⑤ (\(k\)は整数)とおける。

⑤を④に代入して
\(y-42=73×26k÷26=73k\) ・・・⑥

⑤⑥より
\(x=26k+15\),　\(y=73k+42\) (\(k\)は整数)

(解答②)係数の大きさを小さくする方法

大きい方の係数\(73\)を\(26\)で割った式で表して、方程式の係数を下げる方法を繰り返しても解くことができます。係数が\(1\)になるところが終着点です。

\(73=26×2+21\) より
\((26×2+21)x-26y=3\)
\(21x-26(-2x+y)=3\)
\(-2x+y=a\)・・・(1) とおくと
\(21x-26a=3\)

\(21x-(21+5)a=3\) より
\(21(x-a)-5a=3\)
\(x-a=b\)・・・(2) とおくと
\(21b-5a=3\)・・・(A)

\((5×4+1)b-5a=3\) より
\(b-5(a-4b)=3\)
\(a-4b=k\)・・・(3)とおくと
\(b-5k=3\)・・・(4) (←\(b\)の係数が\(1\)になった)

(4)より \(b=5k+3\)
(3)より \(a=k+4b=k+4(5k+3)=21k+12\)
(2)より \(x=a+b=26k+15\)
(1)より \(y=a+2x=21k+12+2(26k+15)=73k+42\)

よって
\(x=26k+15\),　\(y=73k+42\) (\(k\)は整数)

解答②も繰り返し互除法を用いていることになります。(73を26で割ったあまりが21→26を21で割った余りが5→21を5で割った余りが1)

なお、どちらも最後までやる必要がない場合もあります。
例えば解答②だと、(A)の特殊解は\(b=3,a=12\) とわかるので、(1)(2)より、\(x,y\)の特殊解が分かります。
解答①の方法については、余りがもとの方程式の右辺の数字そのものになるときや、右辺の約数になる場合はそこで終わらすこともできます。

以上になります。お疲れさまでした。
ここまで見ていただきありがとうございました。

→高校数学TOP　next→ax+by=1 の整数解の存在条件　 back→1次不定方程式