不定方程式とその考え方（その２）

 

---

 

 

解を簡単に求められない場合の不定方程式の解き方

その１では「一つでも解が求められれば不定方程式は解ける」と学びました。今回はその一つがなかなか見つけられないときにどうするかを説明しましょう。

端的に言うとその解を「機械的に」見つける方法があります。それは

ユークリッドの互除法を用いたやり方

です。ユークリッドの互除法を使えばなぜ解が見つけられるのかは別記事で解説しますが、今回はそのやり方を伝授いたしましょう。

ユークリッドの互除法がわからない人は別の記事で解説しているのでそちらを見てくださいね。簡単に言うと”ある２つの数字の公約数を簡単に求められる方法”です。

では早速やってみます。まずは次の問題を考えます。

$$23x+5y=1$$

これの解を見つけるのはなかなか大変な気がします。あまりたくさん計算したくはないですよね。なので機械的な方法を試すことにします。

まず、左辺の２３と５に注目し、ユークリッドの互除法を行います。どんどん割ります。割る数とあまりに注目するのでしたね。

 

 

余りが１になったところで止めます。さて、次はどうするかというと、これを逆にたどっていきます。

どういう意味かというと、上に書いた式を利用して、

$$23\times(\ \ \ )+5\times(\ \ \ )=1$$

という元の式と同じ形を目指していくのです。このかっこに入る数字を見つけることができれば、それすなわち今求めたい解の一つであります。

ではどうやって戻るのかというと、一番下の式からスタートして、どんどん余りの部分をなくしていくのです。

最初の式

$$3=2\times 1+1$$

から、まず\(=1\)が作れそうなので移項して

$$3-2\times 1=1$$

とします。次にその上の式から、\(2=\)の形を作れば

$$2=5-3\times 1$$

が得られます。これを先ほどの式の２の部分に代入するのです。

$$3-(5-3\times 1)\times 1+1=1$$

掛け算を残しているのは訳アリです。なぜなら最終的に形が数字×数字になってほしいからです。

まとめます。まとめるときは５と３でそれぞれと数字の積の形で計算をします。

$$3-5\times 1+3\times 1=1$$

$$5\times(-1)+3\times 2=1$$

\(3+3\times 1\)は３が２個になるので\(3\times 2\)としました。５のほうは-５ではなく５が出てほしかったのでマイナスを掛け算のほうに押し付けました。

あとはさらに上の式で

$$23=5\times 4+3$$

から

$$3=23-5\times 4$$

なので同じように３に代入して整理します。

$$5\times(-1)+(23-5\times 4)\times 2=1$$

２３と５に出てきてほしいのでそれを念頭に入れて計算します。２項目は分配法則でばらばらにします。

$$5\times(-1)+23\times 2-5\times 8=1$$

\(-5\times 4\times 2=-5\times 8\)に気を付けてください。

まとめると

$$23\times 2+5\times (-1)+5\times(-8)=1$$

で\(5\times (-1)+5\times(-8)\)は５が-１個と５が-８個なのでトータルで５が-９個になりますので

$$23\times 2+5\times (-9)=1$$

となります。これは私たちの目指していた形ですね。

よって不定方程式の１つの解は

$$x=2\ ,\ y=-9$$

と分かったわけです。この後はその１でやったように答えを求めるだけです。ユークリッドの互除法を用いて機械的に解を一つ求めることができました。

いったん広告の時間です。

\(=1\)じゃなくてもユークリッドの互除法は使える

さて、今の話はあくまでも

$$23x+5y=1$$

のように\(=1\)の形でしか使えないような気がします。ユークリッドの互除法で出てくるのは最終的にあまり１ですからね。

ですが\(=1\)の解がわかればこのパターンの不定方程式は全て解けます。例えば

$$23x+5y=8$$

なんていう不定方程式が出てきても解の一つはもうすぐにわかります。なぜなら私たちは\(=1\)の形での解の一つを知っていて

$$23\times 2+5\times (-9)=1$$

ですね。今欲しいのは\(=8\)の時の解の一つですが、じゃあ両辺に８をかけましょう。

すると

$$23\times 2\times 8+5\times (-9)\times 8=8$$

となるわけですが、左辺はそれぞれ掛け算なので

$$23\times 16+5\times (-72)=8$$

としたって何の問題もありません。これはまさに今欲しかった解の一つでありそれは

$$x=16\ ,\ y=-72$$

となるわけです。このパターンのどんな不定方程式でも、\(=1\)の解さえ見つければ大丈夫であることがわかったと思います。

なので不定方程式を解く際は\(=1\)の形でなくても

ことが大切になります。いろんな問題がこれで解けそうですね。

終わりに

不定方程式とユークリッドの互除法のつながりがわかったでしょうか。このタイプの問題はかなり出やすいのでまずはやり方を覚えて、自分の手でできるまで取り組んでください。

ではまた。