整数の性質｜互除法を利用して１次不定方程式を解こう
数学Ａ
今回も1次不定方程式を扱いますが、ユークリッドの互除法を利用して解く方法について学習しましょう。1次不定方程式を扱った問題は頻出ですが、解き方をいくつか知っておくと対応しやすいでしょう。
互除法を利用して１次不定方程式を解こう
ユークリッドの互除法は、２つの整数の最大公約数を求める方法です。互除法を利用するとき、割り算と最大公約数の間に成り立つ定理を利用します。
割り算と最大公約数
$2$ つの自然数 $a \ , \ b \ (a \gt b)$ について、$a$ を $b$ で割った商を $q$、余りを $r$ とすると
$a$ と $b$ の最大公約数は、$b$ と $r$ の最大公約数に等しい。
このような互除法の性質を利用して、１次不定方程式を解きます。
解くと言っても、異なるのは１組の整数解を見つけ方だけで、１組の整数解を見つけた後の手順は変わりません。１組の整数解の見つけ方は、自力ではなく互除法を利用します。
互除法を利用する解法を知っていれば、自力で見つけることができなくても諦めずに済みます。互除法を利用する方法では、少しコツが必要ですが、１度掴んでしまえば簡単です。
整数解が見つからないとき、互除法の他に、１次不定方程式の係数を小さくして解く方法がある。ここでは割愛する。
さっそく例題を使って手順を確認しましょう。
例題で学ぶ互除法を利用した方程式の解法
例題
\begin{align*}
&\text{次の方程式の整数解をすべて求めよ。} \\[ 5pt ]
&\quad 37x-90y=4
\end{align*}
係数になっている２数の最大公約数を求める
与式のように、係数が大きくなると１組の整数解を見つけにくくなります。
入試レベルでは係数が２桁の数になることが多いです。そんなときに互除法を利用すると、１組の整数解を見つけることができます。
まず、互除法を利用して、係数である３７と９０の最大公約数を求めます。計算過程を利用するので、筆算よりも式を書き並べていった方が良いでしょう。
係数３７，９０の最大公約数を求める
\begin{align*}
&\quad 37x – 90y = 4 \\[ 10pt ]
&\text{$37$ と $90$ の最大公約数を互除法で求める。} \\[ 5pt ]
&\quad 90 = 37 \cdot 2 + 16 \quad \cdots \text{①} \\[ 7pt ]
&\quad 37 = 16 \cdot 2 + 5 \quad \cdots \text{②} \\[ 7pt ]
&\quad 16 = 5 \cdot 3 + 1 \quad \cdots \text{③} \\[ 7pt ]
&\quad 5 = 1 \cdot 5 + 0
\end{align*}
３７と９０の最大公約数が１であることが分かりました。本来の目的は、最大公約数を求めることではなく、１組の整数解を見つけることなので、余りが１になった時点で終了しても構いません（③式）。
互除法の計算過程を逆に辿る
次は①～③式を使って、計算を逆に辿っていきます。すると、方程式に整数解を代入した後の式が得られます。ただし、計算を逆に辿るとき、混乱しやすいので、少し工夫します。
他の数と区別するために、係数を文字に置き換えます。また、①～③式から、「余り＝～」の形を導出します。
互除法の計算過程を逆に辿る
\begin{align*}
&\quad 90 = 37 \cdot 2 + 16 \quad \cdots \text{①} \\[ 7pt ]
&\quad 37 = 16 \cdot 2 + 5 \quad \cdots \text{②} \\[ 7pt ]
&\quad 16 = 5 \cdot 3 + 1 \quad \cdots \text{③} \\[ 7pt ]
&\text{ここで} \ m = 37 \ , \ n = 90 \ \text{とおく。} \\[ 5pt ]
&\text{①より} \\[ 5pt ]
&\quad 16 = 90 – 37 \cdot 2 \\[ 7pt ]
&\text{$m = 37 \ , \ n = 90$ より} \\[ 5pt ]
&\quad 16 = n – 2m \quad \cdots \text{①’} \\[ 7pt ]
&\text{②より} \\[ 5pt ]
&\quad 5 = 37 – 16 \cdot 2 \\[ 7pt ]
&\text{これと①’より} \\[ 5pt ]
&\quad 5 = m – (n – 2m) \cdot 2 \\[ 7pt ]
&\text{整理すると} \\[ 5pt ]
&\quad 5 = 5m – 2n \quad \cdots \text{②’} \\[ 7pt ]
&\text{③より} \\[ 5pt ]
&\quad 1 = 16 – 5 \cdot 3 \\[ 7pt ]
&\text{これと①’，②’より} \\[ 5pt ]
&\quad 1 = n – 2m – (5m – 2n) \cdot 3 \\[ 7pt ]
&\text{整理すると} \\[ 5pt ]
&\quad 1 = -17m + 7n \\[ 7pt ]
&\text{$m = 37 \ , \ n = 90$ より} \\[ 5pt ]
&\quad 37 \cdot (-17) -90 \cdot (-7) = 1 \\[ 7pt ]
&\text{この両辺に $4$ を掛けると} \\[ 5pt ]
&\quad 37 \cdot (-68) -90 \cdot (-28) = 4 \\[ 7pt ]
&\text{したがって、方程式の整数解の $1$ 組は} \\[ 5pt ]
&\quad x = -68 \ , \ y = -28
\end{align*}
１組の整数解が見つかったら、すでに学習した解法を利用して１次不定方程式を解きます。基本的な解法は記事をご確認下さい。
参考書や問題集によっては、③式の方から辿っていく方法で解説してあるものもあります。
どちらにしても、計算過程を逆に辿っていくことには変わりません。ただ、③式の方からだと、係数を文字に置き換えることができないので、①式からの方がやりやすいでしょう。
互除法を使って１組の整数解を見つける手順は以下のようになります。
円と直線の位置関係
- ２つの係数の最大公約数を互助法で求める。
- ２つの係数を文字で表す。
- 互除法で得られる式を「余り＝～」に変形する。
- 互除法で得られた式を上から順に文字式に置き換えていく。
- 最後の式の右辺が与式と同じかどうかを確認。違うなら、両辺を整数倍して揃える。
次は練習問題を解いてみましょう。
