本記事では，数学検定1級で頻出の2元1次不定方程式の解法についてまとめていきます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
目次
2元1次不定方程式の解法
$a$と$b$が互いに素な整数であるとき，
\begin{align}
ax + by &= c
\end{align}
ax + by &= c
\end{align}
の解はユークリッドの互助法を用いて求めることができる。具体的には，$a$と$b$が互いに素であることからユークリッドの互助法は最終的に「余りが$1$」となるため，ユークリッドの互助法の手続きを逆に辿ることにより，
\begin{align}
ax + by &= 1
\end{align}
ax + by &= 1
\end{align}
が得られる。両辺を$c$倍して$a$と$b$が互いに素であることを利用すれば解が得られる。
具体例
\begin{align}
83x + 29y &= 4
\end{align}
83x + 29y &= 4
\end{align}
解答
$83$と$29$は互いに素であるから，ユークリッドの互助法を適用すると，
\begin{align}
83 &= 29\times 2 + 25\\[0.7em]
29 &= 25\times 1 + 4\\[0.7em]
25 &= 4\times 6 + 1
\end{align}
83 &= 29\times 2 + 25\\[0.7em]
29 &= 25\times 1 + 4\\[0.7em]
25 &= 4\times 6 + 1
\end{align}
これらの等式を利用すると，
\begin{align}
25 - 4\times 6 &= 1\\[0.7em]
25 - (29-25\times 1 )\times 6 &= 1\\[0.7em]
25\times 7 - 29\times 6 &= 1\\[0.7em]
(83-29\times 2)\times 7 - 29\times 6 &= 1\\[0.7em]
83\times 7-29\times 20 &= 1\\[0.7em]
83\times 7+29\times (-20) &= 1
\end{align}
25 - 4\times 6 &= 1\\[0.7em]
25 - (29-25\times 1 )\times 6 &= 1\\[0.7em]
25\times 7 - 29\times 6 &= 1\\[0.7em]
(83-29\times 2)\times 7 - 29\times 6 &= 1\\[0.7em]
83\times 7-29\times 20 &= 1\\[0.7em]
83\times 7+29\times (-20) &= 1
\end{align}
が得られます。両辺を$4$倍すると，
\begin{align}
83\times 28+29\times (-80) &= 4
\end{align}
83\times 28+29\times (-80) &= 4
\end{align}
となるため，与えられた式との差を取ることにより，
\begin{align}
83(x-28) &= -29(y+80)
\end{align}
83(x-28) &= -29(y+80)
\end{align}
が得られます。$83$と$29$は互いに素であるから，$k$を整数として
\begin{cases}
x-28 = -29k\\[0.7em]
y + 80 = 83k
\end{cases}
となります。これを変形することにより，
\begin{cases}
x = -29k + 28\\[0.7em]
y = 83k - 80
\end{cases}
が得られます。
コメント