あなたは、教科書・参考書などで、次のような問題を見たことがありますか？
「\( 37x + 32y = 1 \)を満たす整数解を求めよ」
そして、解答を見ると、いきなりユークリッドの互除法が使われていたり。
- 「なんでユークリッドの互除法を使うんだ？」
- 「どういう発想で、その解法に至ったんだ？」
そう思ったことはありませんか？
ここでは、教科書や参考書とは違ったわかりやすい解答を説明いたします。
そこで、まずは、教科書・参考書ではどのような解答がされているかを見ていきます。
教科書・参考書の不定方程式の解答はわかりにくい
\( 37x + 32y = 1 \)のような方程式が１つ与えられても、未知数が\( x,y \)の２つあるので、普通は解くことはできません。
このような方程式を不定方程式といいます。
しかし、未知数\( x,y \)を整数に限定した場合、方程式の解をいくつか求めることができます。
そこで、次の問題を考えてみましょう。
（問題）
次の方程式の整数解をひとつ求めよ。
\[ 37x + 32y = 1 \]
まず、教科書や参考書に一般的に載っている解答を紹介します。
（よくある教科書・参考書の解答）
\( 37 \) と \( 32 \) に対して、ユークリッドの互除法を繰り返し用いると
\begin{align*}
& 37 = 32 + 5 \cdots (1) \\
& 32 = 5 \cdot 6 + 2 \cdots (2) \\
& \phantom{0}5 = 2 \cdot 2 + 1 \cdots (3)
\end{align*}
\( (1) \) ～ \( (3) \) の式は、それぞれ
\begin{align*}
& (1) \Leftrightarrow 5 = 37 – 32 \\
& (2) \Leftrightarrow 2 = 32 – 5 \cdot 6 \\
& (3) \Leftrightarrow 1 = 5 – \underline{2} \cdot 2
\end{align*}
のように式変形できる。
そして、\( (3) \) の式の下線を引いた\( 2 \)に、\( (2) \) の式を代入し、係数 \( 32 \) と \( 5 \) の項をそれぞれまとめる。
\begin{align*}
1 & = 5 – (32 – 5 \cdot 6) \cdot 2 \\
& = 5 – 32 \cdot 2 + 5 \cdot 12 \\
& = 32 \cdot (-2) + \underline{5} \cdot 13 \\
\end{align*}
そして、いま計算した式の下線を引いた\( 5 \)に、\( (1) \) の式を代入し、係数 \( 37 \) と \( 32 \) の項をそれぞれまとめる。
\begin{align*}
& 32 \cdot (-2) + \underline{5} \cdot 13 \\
= & \ 32 \cdot (-2) + (37 – 32) \cdot 13 \\
= & \ 37 \cdot 13 \ + 32 \cdot (-15) \\
\end{align*}
以上より
\[ 1 = 37 \cdot 13 \ + 32 \cdot (-15) \]
であるから、\( x = 13 \)、\( y = – 15 \) は \( 37x + 32y = 1 \)を満たす整数解のひとつである。
この解答を見た時
なんでいきなりユークリッドの互除法が出てきたんだ？
って思いませんでしたか？
参考書によっては、”ユークリッドの互除法を逆にたどって”などと書いているものもありますが、「正直、わかりにくいよな…」というのが本音です。
なので、ここからは教科書や参考書とは違った解き方で不定方程式の解を求めていきます。
そのためにも、まずは\( 37x + 32y = 1 \) を詳しく見ていくことから始めます。
教科書や参考書の解答は忘れて、初めて不定方程式の問題に出会ったつもりで一緒に考えていきましょう。
教科書や参考書とは違った解き方で、不定方程式の解を求める
具体的に値を入れて実験してみる
まず、いくつか値を代入して、実際に方程式を満たす整数の組がないか考えてみましょう。
たとえば、\( x = 1, y = -1 \)のときは
\[ 37 – 32 = 5 \]
より満たさない。
\( x = 4, y = -5 \)のときは
\begin{align*}
&37 \times 4 – 32 \times 5 \\
= & \ 148 – 160 \\
= & \ -12
\end{align*}
より満たさない。
\( x = -6, y = 7 \)のときは
\begin{align*}
&37 \times (-6) + 32 \times 7 \\
= & \ -222 + 224 \\
= & \ 2
\end{align*}
より満たさない。
いま、３つほど計算してみましたが、このまま当てずっぽうに値を代入していても、答えにはたどり着きそうにありませんね。
計算も大変ですし、何度も計算してたらしんどいですよね。
でも、なぜ計算が大変なんでしょうか？
なぜ\( 37x + 32y = 1 \)の計算は大変なのか？
たとえば、整数解を求めたい方程式が\( 37x + 32y = 1 \)ではなく、\( 5x + 2y = 1 \)であれば、どうでしょうか。
計算は楽にできますし、解も簡単に求められます。
実際、\( x = 1, y = -2 \)のとき
\begin{align*}
&5 \times 1 – 2 \times 2 \\
= & \ 5 – 4 \\
= & \ 1
\end{align*}
となり、方程式を満たす整数解が簡単に求められます。
では、なぜ\( 37x + 32y = 1 \)の計算は大変で、\( 5x + 2y = 1 \)の計算は楽に行えるのでしょうか。
それは、未知数\( x,y \)の係数の大小が大きく関わっています。
実際、\( x,y \)の係数は、\( 37x + 32y = 1 \)では\( 37 \)、\( 32 \)と２桁なのに対して、\( 5x + 2y = 1 \)では\( 5 \) と \( 2 \) で１桁です。
桁数が少ないほうが簡単に計算を行えますよね。
つまり、\( x,y \)の係数が小さいと計算が楽に行えるので、方程式を満たす整数解を求めるのも簡単になるということです。
\( 37x + 32y = 1 \)の係数を小さくすると、解が求められる
どうにかして、\( 37x + 32y = 1 \)の係数を小さくできないの？
そう考えたとき、参考になるのが、ユークリッドの互除法のところで見た
“都合のいい部分と、そうでない部分に分ける”
という考え方です。
具体的には、\( 56 \)を
\[ 56 = 36 + 20 \]
のように分けたところです。
この考え方に基づいて、係数を小さくしていくことを考えましょう。
まず、方程式\( 37x + 32y = 1 \)の大きい方の係数\( 37 \)を
\[ 37 = 32 + 5 \]
と、もう一方の係数の\( 32 \)が現れるような形に分けることで、
\begin{align*}
& 37x + 32y = 1 \\
\Leftrightarrow & \ (32 + 5)x + 32y = 1 \\
\Leftrightarrow & \ 32(x + y) + 5x = 1
\end{align*}
と式変形できます。
ここで、\( z = x + y \)と置くと
\[ 32z + 5x = 1 \]
となります。
つまり、係数が小さくなった方程式\( 32z + 5x = 1 \)が解ければ、元の方程式\( 37x + 32y = 1 \)も解けるということです。
そこで、同様の操作を繰り返し、解が簡単に求められるまで係数をどんどん小さくしていきましょう。
方程式\( 32z + 5x = 1 \)の大きい方の係数\( 32 \)は
\[ 32 = 5 \times 6 + 2 \]
と分けることができるので、
\begin{align*}
& 32z + 5x = 1 \\
\Leftrightarrow & \ (5 \times 6 + 2)z + 5x = 1 \\
\Leftrightarrow & \ 5(6z + x) + 2z = 1
\end{align*}
ここで、\( w = 6z + x \)と置くと
\[ 5w + 2z = 1 \]
となります。
よって、係数が小さくなった方程式\( 5w + 2z = 1 \)が解ければ、方程式\( 32z + 5x = 1 \)も解けます。
また、\( w,z \)の係数が十分小さくなったので、方程式\( 5w + 2z = 1 \)の整数解をいくつか求めることができます。
実際、\( w = 1, z = -2 \)は方程式\( 5w + 2z = 1 \)を満たします。
以上より、方程式\( 37x + 32y = 1 \)を満たす\( x ,y \)には
\begin{cases}
x + y = z \\
6z + x = w \\
w = 1 \\
z = -2
\end{cases}
を満たすものがあるということがわかります。
\( w = 1 \)、\( z = -2 \) をそれぞれの式に代入すると
\begin{cases}
x + y = -2 \\
6 \cdot (-2) + x = 1
\end{cases}
よって、元の不定方程式\( 37x + 32y = 1 \)の整数解のひとつとして
\begin{cases}
x = 13 \\
y = -15
\end{cases}
があります。