本記事は数学の徹底解説シリーズに含まれます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
目次
一次不定方程式の解全体
一次不定方程式
\begin{align}
ax + by &= c\label{一次不定式}
\end{align}
ax + by &= c\label{一次不定式}
\end{align}
において，$c$が$d=\gcd(a,b)$の倍数のとき，解の一つを
\begin{align}
x = x_{1},\quad y = y_{1}
\end{align}
x = x_{1},\quad y = y_{1}
\end{align}
とすると，自然数$k$および$a^{\prime}{=}a/d,b^{\prime}{=}b/d$を用いて解の全体は
\begin{align}
x = x_{1}+b^{\prime}k,\quad y = y_{1}-a^{\prime}k
\end{align}
x = x_{1}+b^{\prime}k,\quad y = y_{1}-a^{\prime}k
\end{align}
と表される。
証明
$x_{1},y_{1}$は式($\ref{一次不定式}$)の解であることから，
\begin{align}
ax_{1} + by_{1} &= c
\end{align}
ax_{1} + by_{1} &= c
\end{align}
が成り立ちます。式($\ref{一次不定式}$)からこれを辺々引くと，
\begin{align}
a(x-x_{1}) + b(y-y_{1}) &= 0
\end{align}
a(x-x_{1}) + b(y-y_{1}) &= 0
\end{align}
が得られます。$d$で辺々割って整理すると，
\begin{align}
a^{\prime}(x-x_{1}) &= -b^{\prime}(y-y_{1})\label{互いに素の適用先}
\end{align}
a^{\prime}(x-x_{1}) &= -b^{\prime}(y-y_{1})\label{互いに素の適用先}
\end{align}
が得られます。$a^{\prime}$と$b^{\prime}$は互いに素となることから，$x{-}x_{1}$は$b^{\prime}$の倍数となります。したがって，自然数$k$を用いて
\begin{align}
x &= x_{1} + b^{\prime}k
\end{align}
x &= x_{1} + b^{\prime}k
\end{align}
が得られます。これを式($\ref{互いに素の適用先}$)に代入すると，
\begin{align}
y &= y_{1} - a^{\prime}k
\end{align}
y &= y_{1} - a^{\prime}k
\end{align}
が得られます。
参考文献
本稿の執筆にあたり参考にした文献は，以下でリストアップしております。
コメント