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

07/07/2021数学Ａ

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

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

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

合同式の基本事項

合同式
$a-b$ が $m$ の倍数であるとき、$a \ , \ b$ は $m$ を法として合同であるといい、$a \equiv b \pmod m$ と式で表す。このような式を合同式という。
合同式の性質①
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$
合同式の性質②　$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. 自然数(０以上の整数も可) $n$ に対し　$a^n \equiv b^n \pmod m$

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

数学Ａ｜整数の問題で合同式を使ってみよう

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

合同式と１次不定方程式

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

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

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

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

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

合同式と１次不定方程式（左辺）

\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*}

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

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

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

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

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

例題

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

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

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

例題の解答例 1⃣

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

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

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

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

例題の解答例 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*}

左辺は７ｘと６ｙの和からなる多項式です。６ｙは６の倍数であるので０と合同です。

しかし、右辺の４０は６の倍数ではないので、６ｙと合同ではありません。もとの合同式を考慮すると、７ｘが４０と合同であることが分かります。これは合同式の性質②に関連します。

合同式の性質②

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

このようにして、ｘ，ｙのうちｘだけを用いた合同式（②式）を新たに導出することができました。

新しい合同式を調べる

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

例題の解答例 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*}

７と１が６を法として合同であるので、７ｘとｘが６を法として合同です。また、４０は４と６を法として合同です。

これらと②から、ｘは４０、すなわち４と６を法として合同であることが分かります。これは合同式の性質①，②に関連します。

合同式の性質① 推移律

\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*}

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

例題の解答例 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*}

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

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

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

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

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