頑張れ!受験生! 数学の公式・定理集あります。物理のヒント集始めました。
スポンサーリンク

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

数学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$ を法として、
$\quad ax \pm by \equiv c \pmod b$
が成り立つ。(※逆は成り立たないので注意。)

不定方程式とは言え、両辺は等しいので、同じ数で割ったときの余りは等しくなります。ですから、合同式が成り立ちます。また、この合同式の左辺について、もう少し吟味していくと以下のことが成り立ちます。

\begin{align*}
&\quad by \equiv 0 \pmod b \\[ 5pt ]
&\text{であるので、} \\[ 5pt ]
&\quad ax \equiv c \pmod b \quad \text{…①} \\[ 5pt ]
&\text{ここで、$a$ を $b$ で割ったときの余りを $r$ とすると、} \\[ 5pt ]
&\quad a \equiv r \pmod b \\[ 5pt ]
&\text{より、} \\[ 5pt ]
&\quad ax \equiv rx \pmod b\quad \text{…②} \\[ 5pt ]
&\text{① , ②より、} \\[ 5pt ]
&\quad rx \equiv c \pmod b
\end{align*}

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

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

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

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

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

例題
次の方程式の整数解をすべて求めよ。
$\quad 7x + 6y = 40$

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

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

小さい方の係数を法に定める
\begin{align*}
&\quad 7x + 6y = 40 \quad \text{…①} \\[ 10pt ]
&\text{$6$ を法とすると、①より} \\[ 5pt ]
&\quad 7x + 6y \equiv 40 \pmod 6
\end{align*}

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

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

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

合同式の左辺の各項に注目する
\begin{align*}
&\quad \vdots \\[ 10pt ]
&\quad 7x + 6y \equiv 40 \pmod 6 \\[ 5pt ]
&\text{また、} \\[ 5pt ]
&\quad 6y \equiv 0 \pmod 6 \\[ 5pt ]
&\text{であるので、} \\[ 5pt ]
&\quad 7x \equiv 40 \pmod 6 \quad \text{…②}
\end{align*}

左辺は $7x$ と $6y$ の和からなる多項式です。$6y$ は、6の倍数であるので0と合同です。しかし、右辺の40は、6の倍数ではないので、$6y$ と合同ではありません。もとの合同式を考慮すると、$7x$ が $40$ と合同であることが分かります。以下の性質を利用しています。

合同式の性質②
$a \equiv b \pmod m \ , \ c \equiv d \pmod m$ のとき、
$\quad a+c \equiv b+d \pmod m$

これで $x \ , \ y$ のうち $x$ だけを用いた合同式を新たに導出することができました。

新しい合同式を調べる

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

新しい合同式を調べる
\begin{align*}
&\quad \vdots \\[ 10pt ]
&\quad 7x \equiv 40 \pmod 6 \quad \text{…②} \\[ 5pt ]
&\text{ここで、} \\[ 5pt ]
&\quad 7 \equiv 1 \pmod 6 \\[ 5pt ]
&\text{より、} \\[ 5pt ]
&\quad 7 \cdot x \equiv 1 \cdot x \pmod 6 \\[ 5pt ]
&\text{また、} \\[ 5pt ]
&\quad 40 \equiv 4 \pmod 6 \\[ 5pt ]
&\text{であるので、②は} \\[ 5pt ]
&\quad x \equiv 4 \pmod 6
\end{align*}

7と1が合同であるので、$7x$ と $x$ が合同です。また、40は4と合同です。これらと②から、$x$ は、40、すなわち4と合同であることが分かります。以下の性質を利用しています。

合同式の性質① 推移律
$a \equiv b \pmod m \ , \ b \equiv c \pmod m$ のとき、
$\quad a \equiv c \pmod m$ または $a\equiv b \equiv c \pmod m$
合同式の性質②
$a \equiv b \pmod m \ , \ c \equiv d \pmod m$ のとき、
$\quad ac \equiv bd \pmod m$

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

一般解を求める
\begin{align*}
&\quad 7x + 6y = 40 \quad \text{…①} \\[ 10pt ]
&\quad \vdots \\[ 10pt ]
&\quad x \equiv 4 \pmod 6 \\[ 5pt ]
&\text{したがって、$k$ を整数とすると} \\[ 5pt ]
&\quad x = 6k + 4 \quad \text{…③} \\[ 5pt ]
&\text{① , ③より} \\[ 5pt ]
&\quad 6y = -7(6k+4) + 40 = -42k+12 \\[ 5pt ]
&\text{よって、} \\[ 5pt ]
&\quad y = -7k+2 \quad \text{…④} \\[ 5pt ]
&\text{③ , ④は①を満たすので、①の解である。} \\[ 5pt ]
&\quad \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{△}$ を求める。

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

スポンサーリンク
Amazon ノート・メモ帳ランキング
楽天市場 学習参考書ランキング
スポンサーリンク
スポンサーリンク
気になる教材があればコチラで探せます。
数学A
この記事が気に入ったら
いいね!しよう
最新情報をお届けします。
フォローする
ちょっとど忘れしたときの公式・定理集

数学で覚えるべき公式や定理は、一覧で眺めてみるとそれほど多くはありません。大切なことは覚えることではなく、「公式や定理をどのように使うか」です。

公式・定理集で確認しつつ、演習で積極的に使っていきましょう。

日々是鍛錬 ひびこれたんれん
kiri

このサイトでは、できるだけ図や表を使い、丁寧な過程を記述することを心掛けながら解説しています。このサイトの記事が、苦手意識や壁を取り除くきっかけになれば幸いです。

中学生の先取り学習や高校生の受験対策、社会人の学び直しなどに役立てて下さいませ。

フォローする
タイトルとURLをコピーしました