2元1次不定方程式②

問題

次の方程式の整数解をすべて求めよ。

解説

1次不定方程式の問題を解説します。

1次不定方程式はまず1組の解を見つければいいんでしたよね。でもこの方程式の解は全然見つからない$\cdots$

そういうときは「ユークリッドの互除法」を使うんだ。

ユークリッドの互除法ってなんですか？

ユークリッドの互除法はある2つの自然数の最大公約数を求める方法だよ。

ユークリッドの互除法って最大公約数を求めるのに使うんですよね。それでなぜ$1$組の解が分かるんですか？

順を追って簡単に説明していくね。まず、$1$次不定方程式$ax+by=c$は$2$パターン存在するんだ。

1. 無数の解を持つ不定方程式 (例: $79x+35y=1$)
2. 解を持たない方程式 (例: $6x+3y=1$)

（ここでいう解とは、整数解のこと）

そもそもこの問題では「整数解を求めよ」と出題されているからパターン①であることは決まっているんだけれど、このとき不定方程式$ax+by=c$の$a$と$b$は互いに素になっているよね。

互いに素ということは最大公約数は1ですよね？

そこがポイントで、最大公約数が$1$ということはユークリッドの互除法を使うと最終的に$A=Br+q$の$q$の値が1になるんだ。そうすると、$1=A-Br$として$Br$の値を戻していくような作業をすることにより確実に(機械的に)方程式の$1$組の解を求めることができるんだ。

つまり最大公約数を求めるためにユークリッドの互除法を使うのではなくて最大公約数が1であるという式をユークリッドの互除法により作ってそこから逆に解を特定するような感じですか？

その通り！

それでは、実際にユークリッドの互除法を用いて${\large79x+35y=1}の解の{1}組を$求めていきましょう。

$79$と$35$に対しユークリッドの互除法を用いると、

次に$(3)$の式の$9=8\cdot 1 + \underline{1}$の右辺の$1$に注目して、${ 1=9-8\cdot 1\cdots}{(4)}$と変形します。

$(2)$の$35=9\cdot 3 +8$の右辺の$8$に注目すると、$8=35-9\cdot 3$とできるのでこの式を$(4)$の$8$に代入すると$1=9-(35-9\cdot 3)$となります。

ここでマイナスをカッコにかけると$1=9-35+9\cdot 3$とでき右辺の$9$をくくると${1=-35+9\cdot (1+3)}\cdots (5)$

$(5)$に$(1)$を変形した$9=79-35\cdot 2$を代入すると$1=-35+(79-35\cdot 2)\cdot 4$

よって$1=-35+4\cdot 79 -8\cdot 35$

整理すると$1=79\cdot 4 -35\cdot 9$とできます。

よって、${79x+35y=1}の1組の解は$ ${x=4, y=-9}と$見つけることができました。

この変形は最初は難しいと思うから、何度も練習してスラスラと変形できるようになろう。

次のように色をつけてみるとわかりやすいよ。

方程式の$1$組の解を見つけることができたので、あとは「$1$次不定方程式①」と同様に以下の手順で解いていきます。

1. $a(x-x_0)+b(y-y_0)=0$と変形する
2. $x=bk,\; y=ak$ ($k$は整数)で表す

解答例は次のようになります。

ここでは1次不定方程式の問題について解説しました。

1次不定方程式の問題でユークリッドの互除法を使う方法を理解できましたか？

この解法の式変形は慣れていないとスムーズにできないので、色々な問題を解いて慣れていってくださいね！