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

12/12/2018数学A合同式,整数の性質,不定方程式,整数解

実際に互除法を利用して1次不定方程式を解いてみよう

問(1)
次の方程式の整数解をすべて求めよ。
$\quad 71x + 32y = 3$

問(1)の解答・解説

方程式から合同式に置き換えます。

問(1)の解答例
\begin{align*}
&\quad 71x + 32y = 3 \quad \text{…①} \\[ 10pt ]
&\text{32を法とすると、①より、} \\[ 5pt ]
&\quad 71x + 32y \equiv 3 \pmod {32}
\end{align*}

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

問(1)の解答例つづき
\begin{align*}
&\quad \vdots \\[ 10pt ]
&\quad 71x + 32y \equiv 3 \pmod {32} \\[ 5pt ]
&\text{また、} \\[ 5pt ]
&\quad 32y \equiv 0 \pmod {32} \\[ 5pt ]
&\text{であるので、} \\[ 5pt ]
&\quad 71x \equiv 3 \pmod {32} \quad \text{…②}
\end{align*}

これで $x \ , \ y$ のうち $x$ だけを用いた合同式を導出することができました。この合同式から、左辺の係数が1になった合同式を導出します。

問(1)の解答例つづき
\begin{align*}
&\quad \vdots \\[ 10pt ]
&\quad 71x \equiv 3 \pmod {32} \quad \text{…②} \\[ 5pt ]
&\text{ここで、} \\[ 5pt ]
&\quad 71 \equiv 7 \pmod {32} \\[ 5pt ]
&\text{より、} \\[ 5pt ]
&\quad 71 \cdot x \equiv 7 \cdot x \pmod {32} \\[ 5pt ]
&\text{また、} \\[ 5pt ]
&\quad 3 \equiv 35 \pmod {32} \\[ 5pt ]
&\text{であるので、②は} \\[ 5pt ]
&\quad 7x \equiv 35 \pmod {32} \\[ 5pt ]
&\text{よって、} \\[ 5pt ]
&\quad x \equiv 5 \pmod {32}
\end{align*}

71と7が合同であるので、$71x$ と $7x$ が合同です。また、3は35と合同です。これらと②から、$7x$ は、3、すなわち35と合同であることが分かります。これをさらに変形すると、$x$ が5と合同であることが分かります。

ここでのポイントは、左辺の係数を小さくする(71から7へ)だけではなく、右辺を係数で割れる数(7の倍数)に置き換える(3から35へ)ことです。もちろん、32で割ったときの余りが3となる数です。

右辺の数を置き換える
\begin{align*}
35 &= 7 \cdot 5 \\[ 5pt ]
&= 32 \cdot 1 + 3
\end{align*}

係数を1まで小さくできれば問題ありません。しかし、問(1)では、$x$ の係数を7と小さくしても、1までは小さくできません。このようなときは、右辺の数を置き換えましょう。

係数を1まで小さくできないときは、右辺の数を調整しよう。

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

問(1)の解答例つづき
\begin{align*}
&\quad 71x + 32y = 3 \quad \text{…①} \\[ 10pt ]
&\quad \vdots \\[ 10pt ]
&\quad x \equiv 5 \pmod {32} \\[ 5pt ]
&\text{したがって、$k$ を整数とすると} \\[ 5pt ]
&\quad x = 32k + 5 \quad \text{…③} \\[ 5pt ]
&\text{① , ③より} \\[ 5pt ]
&\quad 32y = -71(32k + 5) + 3 = -71 \cdot 32k – 352 \\[ 5pt ]
&\text{よって、} \\[ 5pt ]
&\quad y = -71k – 11 \quad \text{…④} \\[ 5pt ]
&\text{③ , ④は①を満たすので、①の解である。} \\[ 5pt ]
&\quad \therefore \ x = 32k + 5 \ , \ y = -71k – 11 \quad \text{($k$ は整数)}
\end{align*}

この問題は、互除法を利用した解き方でも扱っていました。互除法を利用した解き方では、一般解は以下のように表されました。

互除法を利用したときの一般解
\begin{equation*}
\quad x = 32k-27 \ , \ y = -71k + 60 \quad \text{($k$ は整数)}
\end{equation*}

同じ不定方程式なのに、得られる一般解の式が異なります。しかし、得られる値は同じなので心配いりません。

互除法での解の場合、$k=1$ で $x=5 \ , \ y=-11$ ですが、合同式での解の場合、$k=0$ で $x=5 \ , \ y=-11$ です。代入する値は異なりますが、同じ解がきちんと得られます。ですから、どちらの一般解でも良いということです。

ちなみに、互除法で得られた解の $k$ を $k+1$ に置き換えると、合同式で得られた解になる。

もう一問解いてみましょう。

問(2)
次の方程式の整数解をすべて求めよ。
$\quad 37x – 90y = 4$

問(2)の解答・解説

過程は問(1)とほとんど変わりません。37を法とした合同式を利用します。ただし、係数が負の数になっているので、$y$ についての合同式を導出してから(②式以降)が要注意です。

解答例は以下のようになります。

問(2)の解答例
\begin{align*}
&\quad 37x – 90y = 4 \quad \text{…①} \\[ 10pt ]
&\text{37を法とすると、①より、} \\[ 5pt ]
&\quad 37x – 90y \equiv 4 \pmod {37} \\[ 5pt ]
&\text{また、} \\[ 5pt ]
&\quad 37y \equiv 0 \pmod {37} \\[ 5pt ]
&\text{であるので、} \\[ 5pt ]
&\quad -90y \equiv 4 \pmod {37} \quad \text{…②} \\[ 5pt ]
&\text{ここで、} \\[ 5pt ]
&\quad 90 \equiv 16 \pmod {37} \\[ 5pt ]
&\text{より、} \\[ 5pt ]
&\quad -90 \cdot y \equiv -16 \cdot y \pmod {37} \\[ 5pt ]
&\text{また、} \\[ 5pt ]
&\quad 4 \equiv -144 \pmod {37} \\[ 5pt ]
&\text{であるので、②は} \\[ 5pt ]
&\quad -16y \equiv -144 \pmod {37} \\[ 5pt ]
&\text{よって、} \\[ 5pt ]
&\quad y \equiv 9 \pmod {37} \\[ 5pt ]
&\text{したがって、$k$ を整数とすると} \\[ 5pt ]
&\quad y = 37k + 9 \quad \text{…③} \\[ 5pt ]
&\text{① , ③より} \\[ 5pt ]
&\quad 37x = 90(37k + 9) + 4 = 90 \cdot 37k + 814 \\[ 5pt ]
&\text{よって、} \\[ 5pt ]
&\quad x = 90k + 22 \quad \text{…④} \\[ 5pt ]
&\text{③ , ④は①を満たすので、①の解である。} \\[ 5pt ]
&\quad \therefore \ x = 90k + 22 \ , \ y = 37k + 9 \quad \text{($k$ は整数)}
\end{align*}

②式以降について、$y$ の係数を16と小さくしても、1までは小さくできません。問(1)と同じように、右辺の数を置き換えます。

右辺の数は、係数の16で割り切れる数(16の倍数)であり、なおかつ37で割ったときの余りが4となる数です。また、係数が負の数(-16)なので、右辺も負の数にします。

正の数だけとは限らない
\begin{align*}
-144 &= 16 \cdot (-9) \\[ 5pt ]
&= 37 \cdot (-4) + 4
\end{align*}

このような条件を満たす数に置き換えることによって、$y$ についての合同式を求めたとき、その右辺が正の数になります。問(1)よりも難易度が高いですが、慣れればすぐに見つけることができるようになります。

1次不定方程式を解くには、1組の整数解を見つける必要がありますが、どうしても見つからないとき、互除法を利用して見つけることができます。また、合同式を利用すれば、1組の整数解を見つけることなく、一般解を求めることができます。

Recommended books

整数の性質を扱った問題は、難関大なら必修でしたが、センター試験でも扱われるようになりました。

難しく感じる人もいるかもしれませんが、複雑な公式や図形を扱うことがないので、その気になれば得点源にできる単元です。単元別の問題集で集中的に取り組んでマスターしましょう。

これから紹介する教材で気になるものがあれば、ぜひ一読してみて下さい。気に入ったら最後まで徹底的にこなしましょう。

オススメその1

『[affi id=53]』は、教科書レベルから始めて大学入試の実戦レベルまで、最大効率で習得できる問題集です。新課程の整数問題に対応しています。問題数が47題なので、短期間でこなしたいなら候補に入れて良いでしょう。

【教科書編】
問題数16題。新課程版教科書「整数の性質」の項目に沿って配置。
教科書編項目:約数と倍数/約数の個数と総和/最大公約数と最小公倍数/剰余による分類/ユークリッドの互除法とディオファントス方程式/p進法/循環小数/合同式/部屋割り論法

【実戦問題のレベル別編】
初級編20題、中級編5題、上級編6題。
難関大学の整数問題に十分対処できるようにすることを目標として作成。
できる限り数学1・数学Aの範囲にとどめるように問題を選択。
ただし、二項定理・高次の多項式の因数分解・数列の問題あり。

数学1・Aの範囲内にとどめるように配慮されているおかげで、数学1・Aの学習直後から取り組めます。学習したてなら苦手意識がつく前なので、スムーズに取り組めるでしょう。

[affi id=54]

オススメその2

『[affi id=55]』は、頻出かつ重要な問題について、例題だけでなく、類題もあるので演習量をこなせる問題集です。解答例や解説は、高校までに学んだ知識だけで理解できるように配慮されているので、数学が苦手な人にも取り組みやすくなっています。

また、力試しの問題も収録されているので、最後の仕上げに取り組むと良いでしょう。定石を身に付けつつ、入試を想定した問題を解いてみたいのなら候補に入れて良いでしょう。

[affi id=56]

オススメその3

『[affi id=57]』は、教科書レベルから難関大学対策までに対応した参考書兼問題集です。基本事項では、具体例をあげながら解説されているので、イメージしやすいでしょう。文系で数学を必要とする人にも向いています。

また、大学入試レベルの問題では、実際に解くときの考察手順が詳細に記載されているので、自分のアプローチのやり方と比較することができます。整数についての知識が足りなくて、問題を解くには早いと考えているのなら候補に入れて良いでしょう。

[affi id=58]

オススメその4

『[affi id=59]』は、初歩・基本のレベルから発展的レベルまでを幅広く解説した参考書兼問題集です。4部構成ですが、大学受験対策としては、第3部を重点的に取り組むと良いでしょう。

第1部:中学上位生~高1・2年生が興味をもって無理なく取り組める系統別の問題演習。
第2部:整数、場合の数それぞれの重要手法のイメージ化に重点をおいて詳しく解説。
第3部:大学受験問題の系統だった解説。
第4部:興味深い問題・発展演習。

少し難易度の高い教材ですが、難関大を目指す理系志望者なら候補に入れて良いでしょう。

[affi id=60]

さいごにもう一度まとめ

  • 合同式を利用して、不定方程式の一般解を求めることができる。
  • 小さい方の係数を法とした合同式にする。
  • 合同式の性質を利用して、左辺の係数や右辺の数を小さくしよう。
  • 係数が1まで小さくできないときは、右辺の数を係数で割り切れる数に置き換えよう。