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

12/11/2018数学A整数の性質,ユークリッドの互除法,不定方程式

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


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

問の解答・解説

まず、互除法を利用して、係数の71と32の最大公約数を求めます。

問の解答例
\begin{align*}
&\quad 71x + 32y = 3 \\[ 10pt ]
&\text{$71$ と $32$ の最大公約数を互除法で求める。} \\[ 5pt ]
&\quad 71 = 32 \cdot 2 + 7 \quad \text{…①} \\[ 5pt ]
&\quad 32 = 7 \cdot 4 + 4 \quad \text{…②} \\[ 5pt ]
&\quad 7 = 4 \cdot 1 + 3 \quad \text{…③} \\[ 5pt ]
&\quad 4 = 3 \cdot 1 + 1 \quad \text{…④}
\end{align*}

次は①~④式を使って、計算を逆に辿っていきます。混乱を避けるために、係数を文字で表します。また、①~④式において、「余り=~」の形に変形します。

問の解答例つづき
\begin{align*}
&\quad 71 = 32 \cdot 2 + 7 \quad \text{…①} \\[ 5pt ]
&\quad 32 = 7 \cdot 4 + 4 \quad \text{…②} \\[ 5pt ]
&\quad 7 = 4 \cdot 1 + 3 \quad \text{…③} \\[ 5pt ]
&\quad 4 = 3 \cdot 1 + 1 \quad \text{…④} \\[ 10pt ]
&\quad m = 71 \ , \ n = 32 \ \text{とおく。} \\[ 5pt ]
&\text{①より、} \\[ 5pt ]
&\quad 7 = 71 – 32 \cdot 2 \\[ 5pt ]
&\text{$m = 71 \ , \ n = 32$ より、} \\[ 5pt ]
&\quad 7 = m – 2n \quad \text{…①’} \\[ 5pt ]
&\text{②より、} \\[ 5pt ]
&\quad 4 = 32 – 7 \cdot 4 \\[ 5pt ]
&\text{これと①’より} \\[ 5pt ]
&\quad 4 = n – (m – 2n) \cdot 4 \\[ 5pt ]
&\text{整理すると、} \\[ 5pt ]
&\quad 4 = -4m + 9n \quad \text{…②’} \\[ 5pt ]
&\text{③より、} \\[ 5pt ]
&\quad 3 = 7 – 4 \cdot 1 \\[ 5pt ]
&\text{これと①’ , ②’より} \\[ 5pt ]
&\quad 3 = m – 2n – (-4m + 9n) \cdot 1 \\[ 5pt ]
&\text{整理すると、} \\[ 5pt ]
&\quad 3 = 5m – 11n \quad \text{…③’} \\[ 5pt ]
&\text{④より、} \\[ 5pt ]
&\quad 1 = 4 – 3 \cdot 1 \\[ 5pt ]
&\text{これと②’ , ③’より} \\[ 5pt ]
&\quad 1 = -4m + 9n – (5m – 11n) \cdot 1 \\[ 5pt ]
&\text{整理すると、} \\[ 5pt ]
&\quad 1 = -9m + 20n \\[ 5pt ]
&\text{$m = 71 \ , \ n = 32$ より、} \\[ 5pt ]
&\quad 71 \cdot (-9) + 32 \cdot 20 = 1 \\[ 5pt ]
&\text{この両辺に $3$ を掛けると、} \\[ 5pt ]
&\quad 71 \cdot (-27) + 32 \cdot 60 = 3 \quad \text{…⑤} \\[ 5pt ]
&\text{したがって、方程式の整数解の1組は} \\[ 5pt ]
&\quad x = -27 \ , \ y = 60
\end{align*}

これで1組の整数解が見つかったので、与式と⑤式を加減算して一般解を求めます。

問の解答例つづき
\begin{align*}
&\quad 71x + 32y = 3 \\[ 5pt ]
&\quad 71 \cdot (-27) + 32 \cdot 60 = 3 \quad \text{…⑤} \\[ 10pt ]
&\text{与式と⑤を減算すると、} \\[ 5pt ]
&\quad 71 (x+27) + 32 (y-60) = 0 \\[ 5pt ]
&\text{よって、} \\[ 5pt ]
&\quad 71 (x+27) = -32 (y-60) \quad \text{…⑥} \\[ 5pt ]
&\text{$71$ と $32$ は互いに素であるので、$k$ を整数とすると、} \\[ 5pt ]
&\quad x+27 = 32k \quad \text{…⑦} \\[ 5pt ]
&\text{⑥ , ⑦より} \\[ 5pt ]
&\quad y-60 = -71k \quad \text{…⑧} \\[ 5pt ]
&\text{⑦ , ⑧を整理すると、一般解は} \\[ 5pt ]
&\quad x = 32k-27 \ , \ y = -71k + 60 \quad \text{($k$ は整数)}
\end{align*}

自力で整数解を見つけることができればそれに越したことはないですが、問題によってはなかなか見つからないときもあります。そういうときはユークリッドの互除法を利用してみましょう。

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組の整数解を見つけることができる。
  • 互除法での計算過程を逆に辿っていこう。
  • 混乱を避けるため、係数を文字に置き換えておこう。
  • 順序よく、文字式に置き換えていくと、1組の整数解が分かる式が得られる。