本記事は数学の徹底解説シリーズに含まれます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
目次
一次不定方程式の解の存在（ベズーの等式）
整数$a,b,c$に対して，一次不定方程式
\begin{align}
ax + by &= c\label{主題}
\end{align}
ax + by &= c\label{主題}
\end{align}
が整数解をもつための必要十分条件は，$c$が$\gcd(a,b)$の倍数となることである。
証明
「式($\ref{主題}$)が整数解をもつ」⇒「$c$が$\gcd(a,b)$の倍数となる」
整数解を$x_{0},y_{0}$とおくと
\begin{align}
ax_{0} + by_{0} &= c
\end{align}
ax_{0} + by_{0} &= c
\end{align}
が成り立ちますが，左辺は$d=\gcd(a,b)$の倍数となるため，右辺も$d$の倍数となります。
「$c$が$\gcd(a,b)$の倍数となる」⇒「式($\ref{主題}$)が整数解をもつ」
まずは$a>0,b>0$を考えます。ユークリッドの互助法より，
\begin{align}
r_{n-2} - q_{n}r_{n-1} &= \gcd(a,b) = d
\end{align}
r_{n-2} - q_{n}r_{n-1} &= \gcd(a,b) = d
\end{align}
を満たすような$n$が存在します。このステップの$r_{n-1}$に$1$つ前のステップで得られた$r_{n-1}$を代入すると
\begin{align}
r_{n-2} - q_{n}(r_{n-3}-q_{n-1}r_{n-2}) &= d
\end{align}
r_{n-2} - q_{n}(r_{n-3}-q_{n-1}r_{n-2}) &= d
\end{align}
が得られます。同様に，$r_{n-2}$に$1$つ前のステップで得られた$r_{n-2}$を代入すると
\begin{align}
-q_{n}r_{n-3}+(1+q_{n}q_{n-1})r_{n-2} &= d
\end{align}
-q_{n}r_{n-3}+(1+q_{n}q_{n-1})r_{n-2} &= d
\end{align}
が得られます。これを続けていくと最終的に，ある整数$x_{0},y_{0}$を用いて
\begin{align}
x_{0}a+ y_{0}b &= d\label{代入前}
\end{align}
x_{0}a+ y_{0}b &= d\label{代入前}
\end{align}
が得られます。$a,b$の符号が異なる場合も，例えば$a{<}0$の場合は${-}a{=}a$と置き直すことで同様の議論が可能であるため，整数$a,b$に対して一次不定方程式
\begin{align}
ax + by &= d
\end{align}
ax + by &= d
\end{align}
は整数解$x_{0},y_{0}$をもちます。ゆえに，$c^{\prime}{=c/d}$として式($\ref{代入前}$)の両辺に$c^{\prime}$をかけると，
\begin{align}
a(c^{\prime}x_{0}) + b(c^{\prime}y_{0}) &= c^{\prime}d = c
\end{align}
a(c^{\prime}x_{0}) + b(c^{\prime}y_{0}) &= c^{\prime}d = c
\end{align}
となるため，式($\ref{主題}$)は整数解$c^{\prime}x_{0},c^{\prime}y_{0}$をもつことが示されました。
コメント