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

07/07/2021数学Ａ

１次不定方程式を扱った問題を合同式で解いてみよう

問１

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

「整数解をすべて求めよ」とあるので、一般解を求めなければなりません。

問１の解答・解説

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

問１の解答例 1⃣

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

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

問１の解答例 2⃣

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

これでｘ，ｙのうちｘだけを用いた合同式を導出できました。この合同式から、左辺の係数が１になった合同式を導出します。

問１の解答例 3⃣

\begin{align*} &\quad \vdots \\[ 7pt ] &\quad 71x \equiv 3 \pmod {32} \quad \cdots \text{②} \\[ 7pt ] &\text{ここで} \\[ 5pt ] &\quad 71 \equiv 7 \pmod {32} \\[ 7pt ] &\text{より} \\[ 5pt ] &\quad 71 \cdot x \equiv 7 \cdot x \pmod {32} \\[ 7pt ] &\therefore \ 71x \equiv 7x \pmod {32} \\[ 7pt ] &\text{また} \\[ 5pt ] &\quad 3 \equiv 35 \pmod {32} \\[ 7pt ] &\text{であるので、②は} \\[ 5pt ] &\quad 7x \equiv 35 \pmod {32} \\[ 7pt ] &\text{よって} \\[ 5pt ] &\quad x \equiv 5 \pmod {32} \end{align*}

７１と７が３２を法として合同であるので、７１ｘと７ｘが合同です。また、３は３５と３２を法として合同です。

これらと②から、７ｘは３、すなわち３５と３２を法として合同となります。これをさらに変形すると、ｘが５と３２を法として合同であることが分かります。

ここでのポイントは２つあります。１つ目は、左辺の係数を小さくする（７１から７へ）ことです。

２つ目は、合同式の右辺を係数で割れる数（７の倍数）に置き換える（３から３５へ）ことです。このとき、係数で割り切れるだけでなく余りにも気を付けます。

ここでは、３２で割ったときの余りが３となる数に置き換えました。

合同式の右辺を置き換える

\begin{align*} 35 &= 7 \cdot 5 \\[ 7pt ] &= 32 \cdot 1 + 3 \end{align*}

$35$ は $7$ の倍数であり、かつ $32$ で割ると余りが $3$ になる数

ｘの係数を１まで小さくできれば良いのですが、問１のようにすんなりいかないときもあります。

問１では、ｘの係数を７と小さくしても、１までは小さくできません。このようなときは、右辺の数を置き換えましょう。

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

ｘは３２を法として５と合同になることが分かりました。ですから、ｘは３２で割ったときの余りが５になる数となります。

方程式の一般解を求めます。

問１の解答例 4⃣

\begin{align*} &\quad 71x + 32y = 3 \quad \cdots \text{①} \\[ 7pt ] &\quad \vdots \\[ 7pt ] &\quad x \equiv 5 \pmod {32} \\[ 7pt ] &\text{したがって、$k$ を整数とすると} \\[ 5pt ] &\quad x = 32k + 5 \quad \cdots \text{③} \\[ 7pt ] &\text{①，③より} \\[ 5pt ] &\quad 32y = -71(32k + 5) + 3 = -71 \cdot 32k – 352 \\[ 7pt ] &\text{よって} \\[ 5pt ] &\quad y = -71k – 11 \quad \cdots \text{④} \\[ 7pt ] &\text{③，④は①を満たすので、①の解である。} \\[ 5pt ] &\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*}

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

互除法での一般解では、ｋ＝１のときｘ＝５，ｙ＝－１１です。それに対して、合同式での一般解では、ｋ＝０のときｘ＝５，ｙ＝－１１です。

ｋの値は異なりますが、同じ解がきちんと得られます。ですから、どちらの一般解でも問題ありません。

もう少し丁寧に言えば、互除法での一般解のｋをｋ＋１に置き換えると、合同式での一般解が得られます。つまり、解がずれて出てくるだけです。

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

問２

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

問２の解答・解説

過程は問１とほとんど変わりません。３７を法とした合同式を利用します。

ただし、係数が負の数になっているので、ｙについての合同式を導出してから（②式以降）が要注意です。

与えられた方程式から３７を法とする合同式を立式します。そして、文字ｘ，ｙのうちｙだけを用いた合同式を導出します。

問２の解答例 1⃣

\begin{align*} &\quad 37x – 90y = 4 \quad \cdots \text{①} \\[ 7pt ] &\text{$37$ を法とすると、①より} \\[ 5pt ] &\quad 37x – 90y \equiv 4 \pmod {37} \\[ 7pt ] &\text{また} \\[ 5pt ] &\quad 37y \equiv 0 \pmod {37} \\[ 7pt ] &\text{であるので} \\[ 5pt ] &\quad -90y \equiv 4 \pmod {37} \quad \cdots \text{②} \end{align*}

②式を導出するのは難しくありません。問題はここからです。

問２の解答例 2⃣

\begin{align*} &\quad \vdots \\[ 7pt ] &\quad -90y \equiv 4 \pmod {37} \quad \cdots \text{②} \\[ 7pt ] &\text{ここで} \\[ 5pt ] &\quad 90 \equiv 16 \pmod {37} \\[ 7pt ] &\text{より} \\[ 5pt ] &\quad -90 \cdot y \equiv -16 \cdot y \pmod {37} \\[ 7pt ] &\therefore \ -90y \equiv -16y \pmod {37} \\[ 7pt ] &\text{また} \\[ 5pt ] &\quad 4 \equiv -144 \pmod {37} \\[ 7pt ] &\text{であるので、②は} \\[ 5pt ] &\quad -16y \equiv -144 \pmod {37} \\[ 7pt ] &\text{よって} \\[ 5pt ] &\quad y \equiv 9 \pmod {37} \end{align*}

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

右辺の数は、係数の１６で割り切れる数（１６の倍数）であり、なおかつ３７で割ったときの余りが４となる数です。

また、係数が負の数（－１６）なので、右辺も負の数にします。

正の数とは限らない

\begin{align*} -144 &= 16 \cdot (-9) \\[ 7pt ] &= 37 \cdot (-4) + 4 \end{align*}

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

ｙは３７を法として９と合同になることが分かりました。ですから、ｙは３７で割ったときの余りが９になる数となります。

方程式の一般解を求めます。

問２の解答例 3⃣

\begin{align*} &\quad 37x – 90y = 4 \quad \cdots \text{①} \\[ 7pt ] &\quad \vdots \\[ 7pt ] &\quad y \equiv 9 \pmod {37} \\[ 7pt ] &\text{したがって、$k$ を整数とすると} \\[ 5pt ] &\quad y = 37k + 9 \quad \cdots \text{③} \\[ 7pt ] &\text{①，③より} \\[ 5pt ] &\quad 37x = 90(37k + 9) + 4 = 90 \cdot 37k + 814 \\[ 7pt ] &\text{よって} \\[ 5pt ] &\quad x = 90k + 22 \quad \cdots \text{④} \\[ 7pt ] &\text{③，④は①を満たすので、①の解である。} \\[ 5pt ] &\therefore \ x = 90k + 22 \ , \ y = 37k + 9 \quad \text{（$k$ は整数）} \end{align*}

１次不定方程式を解くには、１組の整数解を見つける必要があります。しかし、どうしても見つからなければ、互除法を利用すれば上手くいきます。

また、合同式を利用すれば、１組の整数解を見つけることなく、一般解を求めることができます。

１次不定方程式の解くために知っておきたい事柄

一般的な解法：１組の整数解を見つけて、それをもとに一般解を求める
１組の整数解がどうしても見つからない ⇒ 互除法を利用する
１組の整数解を見つけずに一般解を求めたい ⇒ 合同式を利用する

Recommended books

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

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

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

オススメその１

『２週間で完成！整数問題入試対策編』は、教科書レベルから始めて大学入試の実戦レベルまで、最大効率で習得できる問題集です。新課程の整数問題に対応しています。問題数が４７題なので、短期間でこなしたいなら候補に入れて良いでしょう。

【教科書編】
問題数１６題。新課程版教科書「整数の性質」の項目に沿って配置。
教科書編項目:約数と倍数/約数の個数と総和/最大公約数と最小公倍数/剰余による分類/ユークリッドの互除法とディオファントス方程式/ｐ進法/循環小数/合同式/部屋割り論法
【実戦問題のレベル別編】
初級編２０題、中級編５題、上級編６題。
難関大学の整数問題に十分対処できるようにすることを目標として作成。
できる限り数学１・数学Ａの範囲にとどめるように問題を選択。
ただし、二項定理・高次の多項式の因数分解・数列の問題あり。

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

２週間で完成！整数問題入試対策編

created by Rinker

オススメその２

『教科書だけでは足りない大学入試攻略整数』では、入試の整数問題１０００題から選ばれた問題が収録されています。例題、類題、力試し問題と３ステップで進めていけるので、自分の学力に合わせて周回できます。解答例や解説は、高校までに学んだ知識だけで理解できるように配慮されているので、数学が苦手な人にも取り組みやすくなっています。

整数問題は、難関大入試では頻出で、しかも教科書の問題と入試とではそのレベルの差が激しい分野のひとつです。また、経験値がものをいう問題が多いことも確かです。そこで、ここ数十年の大学入試の整数問題約１０００題の中からぜひやっておきたい問題を例題、類題、力だめし問題として計８１題セレクトしました。
高校までに学んだ知識だけで理解できる解説、解答例を作成しています。

定石を身に付けつつ、入試を想定した問題を解いてみたいのなら候補に入れて良いでしょう。