整数の性質|互除法を利用して1次不定方程式を解こう

12/11/2018数学A整数の性質,ユークリッドの互除法,不定方程式

今回も1次不定方程式を扱いますが、ユークリッドの互除法を利用して解く方法について学習しましょう。1次不定方程式を扱った問題は頻出ですが、解き方をいくつか知っておくと対応しやすいでしょう。

互除法を利用して1次不定方程式を解こう

ユークリッドの互除法は、2つの整数の最大公約数を求める方法でした。互除法を利用するとき、割り算と最大公約数の間に成り立つ定理を利用していました。

割り算と最大公約数
2つの自然数 $a \ , \ b \ (a \gt b)$ について、$a$ を $b$ で割った商を $q$、余りを $r$ とすると、
$a$ と $b$ の最大公約数は、$b$ と $r$ の最大公約数に等しい。

このような互除法を利用して、1次不定方程式を解きます。解くと言っても、1組の整数解を自分で見つけるのではなく、互除法を利用して見つけるところだけが異なります。1組の整数解を見つけた後の手順は変わりません。

ただ、自力で1組の整数解を見つけられないとき、諦めずに済むので覚えておきたいところです。互除法を利用して整数解を見つける方法では、少しコツが必要ですが、1度掴んでしまえば簡単です。

整数解が見つからないとき、互除法の他に、1次不定方程式の係数を小さくして解く方法がある。ここでは割愛する。

さっそく例題を使って手順を確認しましょう。

例題で学ぶ互除法を利用した解き方

例題
次の方程式の整数解をすべて求めよ。
$\quad 37x-90y=4$

係数の最大公約数を求める

与式のように、係数が大きくなると1組の整数解を見つけにくくなります。入試レベルでは係数が2桁の数になることが多いです。そんなときに、互除法を利用すると、1組の整数解を見つけることができます。

まず、互除法を利用して、係数の37と90の最大公約数を求めます。計算過程を利用するので、筆算よりも式を書き並べていった方が良いでしょう。

係数37 , 90の最大公約数を求める
\begin{align*}
&\quad 37x – 90y = 4 \\[ 10pt ]
&\text{$37$ と $90$ の最大公約数を互除法で求める。} \\[ 5pt ]
&\quad 90 = 37 \cdot 2 + 16 \quad \text{…①} \\[ 5pt ]
&\quad 37 = 16 \cdot 2 + 5 \quad \text{…②} \\[ 5pt ]
&\quad 16 = 5 \cdot 3 + 1 \quad \text{…③} \\[ 5pt ]
&\quad 5 = 1 \cdot 5 + 0
\end{align*}

37と90の最大公約数は1であることが分かりましたが、目的は最大公約数ではないので、余りが1になったら終了しても構いません(③式)。

互除法の計算過程を逆に辿る

次は①~③式を使って、計算を逆に辿っていきます。すると、方程式に整数解を代入した後の式が得られます。ただし、計算を逆に辿るとき、混乱しやすいので、少し工夫します。

他の数と区別するために、係数を文字で表します。また、①~③式において、「余り=~」の形に変形します。

互除法の計算過程を逆に辿る
\begin{align*}
&\quad 90 = 37 \cdot 2 + 16 \quad \text{…①} \\[ 5pt ]
&\quad 37 = 16 \cdot 2 + 5 \quad \text{…②} \\[ 5pt ]
&\quad 16 = 5 \cdot 3 + 1 \quad \text{…③} \\[ 10pt ]
&\quad m = 37 \ , \ n = 90 \ \text{とおく。} \\[ 5pt ]
&\text{①より、} \\[ 5pt ]
&\quad 16 = 90 – 37 \cdot 2 \\[ 5pt ]
&\text{$m = 37 \ , \ n = 90$ より、} \\[ 5pt ]
&\quad 16 = n – 2m \quad \text{…①’} \\[ 5pt ]
&\text{②より、} \\[ 5pt ]
&\quad 5 = 37 – 16 \cdot 2 \\[ 5pt ]
&\text{これと①’より} \\[ 5pt ]
&\quad 5 = m – (n – 2m) \cdot 2 \\[ 5pt ]
&\text{整理すると、} \\[ 5pt ]
&\quad 5 = 5m – 2n \quad \text{…②’} \\[ 5pt ]
&\text{③より、} \\[ 5pt ]
&\quad 1 = 16 – 5 \cdot 3 \\[ 5pt ]
&\text{これと①’ , ②’より} \\[ 5pt ]
&\quad 1 = n – 2m – (5m – 2n) \cdot 3 \\[ 5pt ]
&\text{整理すると、} \\[ 5pt ]
&\quad 1 = -17m + 7n \\[ 5pt ]
&\text{$m = 37 \ , \ n = 90$ より、} \\[ 5pt ]
&\quad 37 \cdot (-17) -90 \cdot (-7) = 1 \\[ 5pt ]
&\text{この両辺に $4$ を掛けると、} \\[ 5pt ]
&\quad 37 \cdot (-68) -90 \cdot (-28) = 4 \\[ 5pt ]
&\text{したがって、方程式の整数解の1組は} \\[ 5pt ]
&\quad x = -68 \ , \ y = -28
\end{align*}

1組の整数解が見つかったら、あとは基本的な解き方と同じ手順で解きます。解き方は参考記事をご確認下さい。

参考書や問題集によっては、③式の方から辿っていく方法で解説してあるものもあります。どちらにしても、計算過程を逆に辿っていくことには変わりません。ただ、③式の方からだと、係数を文字に置き換えることができないので、①式からの方がやりやすいでしょう。

互除法を使って1組の整数解を見つける手順は以下のようになります。

  1. 2つの係数の最大公約数を互助法で求める。
  2. 2つの係数を文字で表す。
  3. 互除法で得られる式を「余り=~」に変形する。
  4. 互除法で得られた式を上から順に文字式に置き換えていく。
  5. 最後の式の右辺が与式と同じかどうかを確認。違うなら、両辺を整数倍して揃える。

次は練習問題を解いてみましょう。