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

07/03/2021数学Ａ

互除法を利用して１次不定方程式を解いてみよう

問

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

問の解答・解説

互除法を利用して、係数である７１と３２の最大公約数を求めます。

問の解答例 1⃣

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

最大公約数を求めることが目的ではないですが、①～④式を利用するので計算ミスには気を付けましょう。

①～④式を使って、計算を逆に辿っていきます。混乱を避けるために、係数を文字に置き換えておきます。また、①～④式から「余り＝～」の形を導出します。

問の解答例 2⃣

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

丁寧に記述すると、過程が長くなりますが、複雑な計算をしているわけではありません。

１組の整数解を見つけたら、与式と⑤式を加減算して一般解を求めます。

問の解答例 3⃣

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

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

Recommended books

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

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

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

オススメその１

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

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

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

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

created by Rinker

オススメその２

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

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

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