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

07/03/2021数学Ａ

今回も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*}

１組の整数解が見つかったら、すでに学習した解法を利用して１次不定方程式を解きます。基本的な解法は記事をご確認下さい。

整数の性質｜１次不定方程式について

参考書や問題集によっては、③式の方から辿っていく方法で解説してあるものもあります。

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

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

円と直線の位置関係