2元1次不定方程式（その2）

先ほど「2元1次不定方程式」の記事を上げたのですが、「東大塾長の理系ラボ」というサイトの「ユーグリッドの互除法」のページに丁寧な解説がありました。先に検索すればよかった…。まぁ、自分で考えるのも頭の体操です（笑）（無料見ることのできるサイトですが、有料の塾のコンテンツでリンクの是非がわからないので、あえてリンクを張っていません。）

さてと、当該ページには$ax + by = 1$の2元1次不定方程式をユーグリッドの互除法で解く方法が載っていました。そこで、これを$ax + by = c$に一般化する方法を考えてみました。「習えばいいじゃない」とお考えかもしれませんが、このような考察が頭を柔らかくするものと（個人的には）思っています。もちろん、基礎は教科書で学習するのですが。

では早速…。先ず

\begin{eqnarray*}
ax + by = c
\end{eqnarray*}

の$c$を$1$に置き換え、

\begin{eqnarray*}
ax + by = 1 \tag{1}
\end{eqnarray*}

とします。そのうえでユーグリッドの互除法を使って$(1)$の解の1組$(x, y) = (x^{\prime}_{0}, y^{\prime}_{0})$を求めます。こうすると、

\begin{eqnarray*}
ax^{\prime}_{0} + by^{\prime}_{0} = 1 \tag{2}
\end{eqnarray*}

となりますので、$(2)$の両辺に$c$を掛けると

\begin{eqnarray*}
cax^{\prime}_{0} + cby^{\prime}_{0} = c \tag{3}
\end{eqnarray*}

が成り立ちます。$(3)$を変形すると

\begin{eqnarray*}
a(cx^{\prime}_{0}) + b(cy^{\prime}_{0}) = c
\end{eqnarray*}

となり、$ax + by = c$の解の1組は$(x, y) = (x_{0}, y_{0}) = (cx^{\prime}_{0}, cy^{\prime}_{0})$となります。全ての整数解が必要であれば、2元1次不定方程式で導いた$k$を用いる式を使えばOKです。