1次不定方程式の整数解の求め方

今回は、1次不定方程式の整数解の求め方について解説していきます。

この「1次不定方程式の整数解の求め方」は、発想力が試されるというよりは、共通テストなど、計算メインで出題されることが多いものと思います。

ただ、解き方を知らないと、初見ではなかなか太刀打ちができないものでもあります。

ぜひ、今回の解説を通じて、1次不定方程式については完ペキにしていきましょう！

解説

\(a\) と \(b\) が互いに素な場合

それでは、例題を通して、解き方を確認していきましょう。

例題①　\(2x+7y=3\)

4STEPで解いていきます。

STEP 1 なんでもいいので、解を1つ見つける

まずは、STEP1として、1次不等式を満たす解を、何でもいいので、とにかく1つ見つけます。

そこで、例えば、\((x，\)\(y)=(\)\(-2，\)\(1)\) としてみると、

\[左辺=2\cdot(-2)+7\cdot 1=3=右辺\]

となり、\((x，\)\(y)=(\)\(-2，\)\(1)\) は、方程式の解の1つであることがわかりました。

※とにかく解を見つけろ、と言われてもどうしたらいいかわからない！という方は、機械的に見つける方法として、「ユークリッドの互除法」を利用することができます。こちらの方法は、次の例題で紹介します。

STEP 2 \(a(x-{x}_{0})+b(y-{y}_{0})=0\) の形を作る

先ほど得られた、\((x，\)\(y)=(\)\(-2，\)\(1)\) という解を、方程式に代入すると、

\[2\cdot(-2)+7\cdot 1=3\]

となります。これを、方程式 \(2x+7y=3\) から両辺引き算すると、

\[(2x+7y)-\{2\cdot(-2)+7\cdot 1\}=3-3\]

\[\therefore\ 2(x+2)+7(y-1)=0\]

となり、求める形が得られました。

STEP 3 互いに素であることを利用して、解を求める

次に、STEP2の結果より、

\[2(x+2)=-7(y-1)\]

となります。

今、両辺の係数 \(2\) と \(7\) は互いに素なので \(x+2\) は、必ず、\(7\) の倍数です。

したがって、整数 \(n\) を用いて、\(x+2=-7n\) とできます。

この部分が、この1次不等式の解法において最大のポイントです！

この点、若干理解が難しい部分かと思うので、簡単に整理してみます。

STEP 4 得られた解をキレイにして完了！

ここまでくれば、あと一息です！

STEP 3で得られた、\(x+2=-7n\) より、\(x=-7n-2\) となります。

また、\(x+2=-7n\) を \(2(x+2)=-7(y-1)\) に代入して、

\[\begin{alignat*}{3}
&{-7(y-1)}=2(x+2) \\
\Leftrightarrow\ &{-7(y-1)}=2\cdot(-7n) \\
\Leftrightarrow\ &y-1=2\cdot n
\end{alignat*}\]

\[\therefore\ y=2n+1\]

したがって、

\[(x，y)=(-7n-2，2n+1)\ (n\ は整数)\]

と、1次不定方程式を解くことができました！

例題②　\(2025x+1736y=1\)

続いて、いかにも難しそうな、こちらの1不定方程式を解いていきます。

こちらの方程式ですが、見た目は難しそうなものの、例題①で見たSTEP 1～4の通り解き進めてみれば、全く大したことはありません。

STEP 1～4の振り返りと思って、ぜひ、手を動かしてみましょう！

まずはSTEP 1で、1つでいいので、与えられた方程式を満たすような解を見つけます。

、、、が、あまりにも値が大きく、直感的に見つけるのは難しそうです。。。

そこで、ここでは、「ユークリッドの互除法による解の見つけ方」をご紹介します。
なお、ユークリッドの互除法については、こちらのページで解説していますので、まだ学習されていない方は、こちらを先にご覧ください。

係数の \(2025\) と \(1736\) に、ユークリッドの互除法を適用すると、以下のようになります。

\[\begin{alignat*}{3}
2025&=1736\times 1+289 \\
1736&=289\times 6+2 \\
289&=2\times 144+1
\end{alignat*}\]

各式を、「余り＝」の形にすると、

\[\begin{alignat*}{3}
\textcolor{#00B0F0}{289}&&\ \textcolor{#00B0F0}{=}&\ \textcolor{#00B0F0}{2025-1736\times 1}\quad&・・・① \\
\textcolor{#FF0000}{2}&&\ \textcolor{#FF0000}{=}&\ \textcolor{#FF0000}{1736-289\times 6}&・・・② \\
1&&\ =&\ 289-2\times 144&・・・③
\end{alignat*}\]

これを③→②→①と遡る形で変形していきます。

\[\begin{alignat*}{3}
&1=289-\textcolor{#FF0000}{2}\times 144・・・③ \\
\Leftrightarrow\ &{\small 1=289-(\textcolor{#FF0000}{1736-289\times 6})\times 144}\quad(\because\ ②) \\
\Leftrightarrow\ &1=289+864\times 289-144\times 1736 \\
\Leftrightarrow\ &1=865\times \textcolor{#00B0F0}{289}-144\times 1736 \\
\Leftrightarrow\ &{\small 1=865\times (\textcolor{#00B0F0}{2025-1736\times 1})-144\times 1736}\quad(\because\ ①) \\
\Leftrightarrow\ &{\small 1=865\times 2025-865\times 1736-144\times 1736} \\
\Leftrightarrow\ &1=865\times 2025-1009\times 1736 \\
\end{alignat*}\]

\[\therefore\ 2025\cdot 865+1736\cdot (-1009)=1\]

したがって、1次不定方程式 \(2025x+1736y=1\) の解の1つとして、\((x，\)\(y)=(\)\(865，\)\({-1009})\) を求めることができました。

※実際に計算してみると、以下のようになり、確かに成り立っていることがわかります。

\[\begin{alignat*}{3}
左辺&=2025\cdot 865+1736\cdot (-1009) \\
&=1751625-1751624 \\
&=1=右辺
\end{alignat*}\]

先ほど得られた、\((x，\)\(y)=(\)\(865，\)\(-1009)\) という解を、方程式に代入すると、

\[2025\cdot 865+1736\cdot (-1009)=1\]

となります。これを、方程式 \(2025x+1736y=1\) から両辺引き算すると、

\[{\small(2025x+1736y)-\{2025\cdot 865+1736\cdot (-1009)\}=1-1}\]

\[\therefore\ 2025(x-865)+1736(y+1009)=0\]

となり、求める形が得られました。

次に、STEP2の結果より、

\[2025(x-865)=-1736(y+1009)\]

となります。両辺の係数 \(2025\) と \(1736\) は、

• \(2025={3}^{4}\cdot{5}^{2}\)
• \(1736={2}^{3}\cdot 7\cdot 31\)

と素因数分解することができ、互いに素なので \(x-865\) は、必ず、\(1736\) の倍数です。

したがって、整数 \(n\) を用いて、\(x-865=-1736n\) とできます。

STEP 3で得られた、\(x-865=-1736n\) より、\(x=-1736n+865\) となります。

また、\(x-865=-1736n\) を \(2025(x-865)=-1736(y+1009)\) に代入して、

\[\begin{alignat*}{3}
&{-1736(y+1009)}=2025(x-865) \\
\Leftrightarrow\ &{-1736(y+1009)}=2025\cdot(-1736n) \\
\Leftrightarrow\ &y+1009=2025\cdot n
\end{alignat*}\]

\[\therefore\ y=2025n-1009\]

したがって、

\[{\small(x，y)=(-1736n+865，2025n-1009)\ (n\ は整数)}\]

と、1次不定方程式を解くことができました！

\(a\) と \(b\) が2以上の最大公約数 \(g\) を持つ場合

続いて、\(x，y\) の係数 \(a\) と \(b\) が、2以上の最大公約数 \(g\) を持つ場合を考えます。

とは言っても、ほとんど、前の章で見た、「\(a\) と \(b\) が互いに素な場合」と同じで、計算の前に、若干操作が増えるだけになりますので、ご安心ください！

例題③　\(4x+6y=12\)

両辺を \(4\) と \(6\) の最大公約数 \(2\) で割り算します。

すると、\(2x+3y=6\) となります。

あとは、\(a’\) と \(b’\) は互いに素であることに注意すると、前の章で見た、「\(a\) と \(b\) が互いに素な場合」と全く同じです。具体的には、

• STEP 1 なんでもいいので、解を1つ見つける
• STEP 2 \(a'(x-{x}_{0})+b'(y-{y}_{0})=0\) の形を作る
• STEP 3 互いに素であることを利用して、解を求める
• STEP 4 得られた解をキレイにして完了！

の4STEPを行うことで、1次不定方程式の整数解を得られます。（解答は割愛しますので、ぜひご自身の手で解いてみましょう！）

なお、今回は、右辺の \(c\) が、\(a\) と \(b\) の最大公約数 \(g\) を約数に持つことを前提に解説しました。

というのも、\(a\) と \(b\) の最大公約数 \(g\) を約数に持たない場合、方程式 \(ax+by=c\) は整数解を持ちません。
そのため、このような場合は出題されないと思われ、気にする必要ありません。

ちなみに、このような場合に整数解を持たないことについては、こちらのページで証明していますので、興味がある方はご覧ください。

おわりに

お疲れさまでした！今回は、1次不定方程式の整数解の求め方について解説しました。

慣れれば全然難しくないものの、初見だと少し考えてしまう、という、事前準備がものをいう分野になりますので、ぜひ、ご自身の手を動かして、解答の感覚をつかんでいただければうれしいです！

ちなみに、非常にどうでもいいことなのですが、、、

こちらの1次不定方程式の整数解を求める問題は、出題する側の先生からすると、採点にかなりの手間がかかってしまう、学校の先生泣かせの問題だったりします。

というのも、STEP 1で具体的な解を見つけましたが、最終的な不定方程式を満たすものであれば、何でもよく、パターンは（、理論上）、無限に存在します。

さらに、STEP 3において、今回の解説では、\(x-{x}_{0}=-bn\) と必ず表すようにしましたが、\(x-{x}_{0}=+bn\) と正負を反対にしても成り立ってしまいます。

、、、というわけで、正解のパターンが無数に存在してしまい、採点するのも一苦労、となってしまうわけです。

このような、出題者側の都合から、高校の定期テストなどでは、誘導により、答えの表し方限定されるような工夫がされることもあるようです。