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

数学A

数学A 整数の性質

今回も1次不定方程式を扱いますが、合同式を利用して解く方法について学習しましょう。ユークリッドの互除法を利用した解き方まででも十分ですが、合同式は意外と便利なので知っておくと検算にも使えます。

合同式を利用して1次不定方程式を解こう

合同式は、以下のような基本性質をもつものでした。2つの数を同じ数で割った余りに注目しています。合同式の基本事項は3つあります。

合同式の基本事項

  1. 合同式
    $a-b$ が $m$ の倍数であるとき、$a \ , \ b$ は $m$ を法として合同であるといい、$a \equiv b \pmod m$ と式で表す。このような式を合同式という。
  2. 合同式の性質①
    1. 反射律 $a \equiv a \pmod m$
    2. 対称律 $a \equiv b \pmod m$ のとき、$b \equiv a \pmod m$
    3. 推移律 $a \equiv b \pmod m \ , \ b \equiv c \pmod m$ のとき、
      $a \equiv c \pmod m$ または $a\equiv b \equiv c \pmod m$
  3. 合同式の性質② $a \equiv b \pmod m \ , \ c \equiv d \pmod m$ のとき、次のことが成り立つ。
    1. $a+c \equiv b+d \pmod m$
    2. $a-c \equiv b-d \pmod m$
    3. $ac \equiv bd \pmod m$
    4. 自然数(0以上の整数も可) $n$ に対し $a^n \equiv b^n \pmod m$

詳細は参考記事をご覧下さい。

合同式を利用した1次不定方程式について以下のようなことが成り立ちます。

合同式と1次不定方程式

$a \ , \ b$ は互いに素である自然数であるとし、$a \gt b$ とするとき、不定方程式 $ax \pm by = c$ に対し、$b$ を法として

\begin{align*} \quad ax \pm by \equiv c \pmod b \end{align*}

が成り立つ。(※逆は成り立たないので注意)

不定方程式とは言え、両辺は等しいので、同じ数で割ったときの余りは等しくなります。ですから、合同式が成り立ちます。

また、この合同式の左辺について、もう少し吟味していくと以下のことが成り立ちます。

合同式と1次不定方程式(左辺)

\begin{align*} &\quad by \equiv 0 \pmod b \\[ 7pt ] &\text{であるので} \\[ 5pt ] &\quad ax \equiv c \pmod b \quad \cdots \text{①} \end{align*}

ここで、$a$ を $b$ で割ったときの余りを $r$ とすると

\begin{align*} &\quad a \equiv r \pmod b \\[ 7pt ] &\text{より} \\[ 5pt ] &\quad ax \equiv rx \pmod b\quad \cdots \text{②} \\[ 7pt ] &\text{①,②より} \\[ 5pt ] &\quad rx \equiv c \pmod b \end{align*}

このことから分かるのは、xの係数を小さくしていけば必ず解けるということです。ユークリッドの互除法も同じような考え方なので、共通点と言えるでしょう。

最初に挙げた定理では、a>bであることが条件でしたが、もしa<bであれば、aを法として考えれば同じようにしてこの定理を利用することができます。

2つの係数のうち、小さい方の数を法として合同式を利用しよう。

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

例題で学ぶ合同式を利用した解き方

例題

\begin{align*} &\text{次の方程式の整数解をすべて求めよ。} \\[ 5pt ] &\quad 7x + 6y = 40 \end{align*}

小さい方の係数を法に定める

与式を見ると、係数は7と6です。小さい方は6なので、6を法とします。法が定まったら、合同式を立式します。

例題の解答例 1⃣

\begin{align*} &\quad 7x + 6y = 40 \quad \cdots \text{①} \\[ 7pt ] &\text{$6$ を法とすると、①より} \\[ 5pt ] &\quad 7x + 6y \equiv 40 \pmod 6 \end{align*}

①式から左辺と右辺は等しいので、法に定めた数で割ったときの余りは等しくなります。ですから、両辺は6を法として合同です。

合同式の左辺の各項に注目する

合同式ができたので、次は左辺の各項に注目します。

例題の解答例 2⃣

\begin{align*} &\quad \vdots \\[ 7pt ] &\quad 7x + 6y \equiv 40 \pmod 6 \\[ 7pt ] &\text{また} \\[ 5pt ] &\quad 6y \equiv 0 \pmod 6 \\[ 7pt ] &\text{であるので} \\[ 5pt ] &\quad 7x \equiv 40 \pmod 6 \quad \cdots \text{②} \end{align*}

左辺は7xと6yの和からなる多項式です。6yは6の倍数であるので0と合同です。

しかし、右辺の40は6の倍数ではないので、6yと合同ではありません。もとの合同式を考慮すると、7xが40と合同であることが分かります。これは合同式の性質②に関連します。

合同式の性質②

\begin{align*} &a \equiv b \pmod m \ , \ c \equiv d \pmod m \ \text{のとき} \\[ 5pt ] &\quad a+c \equiv b+d \pmod m \end{align*}

このようにして、x,yのうちxだけを用いた合同式(②式)を新たに導出することができました。

新しい合同式を調べる

新しい合同式(②式)を詳しく調べていきます。

例題の解答例 3⃣

\begin{align*} &\quad \vdots \\[ 7pt ] &\quad 7x \equiv 40 \pmod 6 \quad \cdots \text{②} \\[ 7pt ] &\text{ここで} \\[ 5pt ] &\quad 7 \equiv 1 \pmod 6 \\[ 7pt ] &\text{より} \\[ 5pt ] &\quad 7 \cdot x \equiv 1 \cdot x \pmod 6 \\[ 7pt ] &\quad \therefore \ 7x \equiv x \pmod 6 \\[ 7pt ] &\text{また} \\[ 5pt ] &\quad 40 \equiv 4 \pmod 6 \\[ 7pt ] &\text{であるので、②は} \\[ 5pt ] &\quad x \equiv 4 \pmod 6 \end{align*}

7と1が6を法として合同であるので、7xとxが6を法として合同です。また、40は4と6を法として合同です。

これらと②から、xは40、すなわち4と6を法として合同であることが分かります。これは合同式の性質①,②に関連します。

合同式の性質① 推移律

\begin{align*} &a \equiv b \pmod m \ , \ b \equiv c \pmod m \ \text{のとき} \\[ 5pt ] &\quad a \equiv c \pmod m \\[ 7pt ] &\text{または} \\[ 5pt ] &\quad a\equiv b \equiv c \pmod m \end{align*}

合同式の性質②

\begin{align*} &a \equiv b \pmod m \ , \ c \equiv d \pmod m \ \text{のとき} \\[ 5pt ] &\quad a+c \equiv b+d \pmod m \end{align*}

xは、6を法としたとき4と合同になることが分かりました。ですから、xは6で割ったときの余りが4になる数となります。方程式の一般解を求めます。

例題の解答例 4⃣

\begin{align*} &\quad 7x + 6y = 40 \quad \cdots \text{①} \\[ 7pt ] &\quad \vdots \\[ 7pt ] &\quad x \equiv 4 \pmod 6 \\[ 7pt ] &\text{したがって、$k$ を整数とすると} \\[ 5pt ] &\quad x = 6k + 4 \quad \cdots \text{③} \\[ 7pt ] &\text{①,③より} \\[ 5pt ] &\quad 6y = -7(6k+4) + 40 = -42k+12 \\[ 7pt ] &\text{よって} \\[ 5pt ] &\quad y = -7k+2 \quad \cdots \text{④} \\[ 7pt ] &\text{③,④は①を満たすので、①の解である。} \\[ 5pt ] &\therefore \ x = 6k + 4 \ , \ y = -7k+2 \quad \text{($k$ は整数)} \end{align*}

合同式を利用した解き方では、法に定めた数で割ったときの余りに注目して解いていきます。上手に利用できれば、式変形や面倒な計算がないので、とても有効な解き方です。

合同法を利用して不定方程式の一般解を求める手順は以下のようになります。

合同法を利用して不定方程式の一般解を求める手順

  1. 方程式 $ax \pm by = c \ (a \gt b)$ から合同式 $ax \pm by \equiv c \pmod b$ へ置き換える。ただし、小さい方の係数を法とする。
  2. 合同式の左辺 $ax \pm by$ から、一方の文字だけを用いた合同式 $ax \equiv c \pmod b$ を新たに導く。
  3. 合同式 $ax \equiv c \pmod b$ から、係数が1になった合同式 $x \equiv \text{□} \pmod b$ を導く。
  4. 合同式 $x \equiv \text{□} \pmod b$ から、解 $x = bk + \text{□}$ を求める。
  5. 4で求めた解と与式から、残りの解 $y = \mp ak + \text{△}$ を求める。

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