1次不定方程式の整数解を求める(2)

「次の1次不定方程式の整数解をすべて求めよ。

(1)$\large37x+42y=3$

(2)$\large84x-56y=21$

(3)$\large39x+52y=12$」

　$x,y$の係数が小さい場合は1つ目の整数解を簡単に見つけられますが、係数が大きくなると整数解を求めるのは難しくなります。

このような場合に1つ目の整数解を求めるにはユークリッドの互除法を利用します。

関連：ユークリッドの互除法　最大公約数を求める方法

(1)$37x+42y=3$

　1次不定方程式の$x,y$の係数は互いに素である場合とそうでない場合の2通りが存在します。
$(1)$の解き方は$x,y$の係数は互いに素である場合です。

ユークリッドの互除法をもちいて$x,y$の係数の最大公約数を求めます。

\begin{align*}\require{color}\textcolor{green}{42}\div\textcolor{blue}{37}&=1\ 余り\textcolor{red}{5}\tag{a}\\[1em]\textcolor{green}{37}\div\textcolor{blue}{5}&=7\ 余り\textcolor{red}{2}\tag{b}\\[0.5em]\textcolor{green}{5}\div\textcolor{blue}{2}&=2\ 余り\textcolor{red}{1}\tag{c}\end{align*}

互除法で余りが$1$になるのは2つの数が互いに素（最大公約数が$1$）である場合だけです。なので、余りに$1$が現れた時点で終わります。

関連：互いに素とは？

$\text{(a),(b),(c)}$を積と和の式に書き換え、右辺が余りだけになるように変形します。このとき、$×$は残しておきます。（$×1$の場合は消しても構いません。）

\begin{align*}\text{(a)}:&\\ &&\textcolor{green}{42}&=\textcolor{blue}{37}\times1+\textcolor{red}{5}\\[0.5em]&&\textcolor{green}{42}-\textcolor{blue}{37}&=\textcolor{red}{5}\tag*{(a)'}\\[1em]\text{(b)}:&\\ &&\textcolor{green}{37}&=\textcolor{blue}{5}\times7+\textcolor{red}{2}\\[0.5em]&&\textcolor{green}{37}-\textcolor{blue}{5}\times7&=\textcolor{red}{2}\tag*{(b)'}\\[1em]\text{(c)}:&\\ &&\textcolor{green}{5}&=\textcolor{blue}{2}\times2+\textcolor{red}{1}\\[0.5em]&&\textcolor{green}{5}-\textcolor{blue}{2}\times2&=\textcolor{red}{1}\tag*{(c)'}\end{align*}

$\text{(c)'}$に$\text{(a)',(b)'}$を代入し、左辺が$x,y$の係数それぞれの倍数の和または差、右辺が$1$の式をつくります。$(1)$の場合は1次不定方程式の左辺が$37$の倍数と$42$の倍数の和なので同様にします。ただし、代入をするのは商にあたる数以外の赤、青、緑に着色した数に対してのみです。

$\text{(c)'}$に$\text{(b)'}$を代入すると

\begin{align*}\textcolor{green}{5}-(\textcolor{green}{37}-\textcolor{blue}{5}\times7)\times2&=\textcolor{red}{1}\\[0.5em]\textcolor{green}{5}-\textcolor{green}{37}\times2+\textcolor{blue}{5}\times14&=\textcolor{red}{1}\\[0.5em](\textcolor{green}{5}+\textcolor{blue}{5}\times14)-\textcolor{green}{37}\times2&=\textcolor{red}{1}\\[0.5em]\textcolor{blue}{5}\times(1+14)-\textcolor{green}{37}\times2&=\textcolor{red}{1}\\[0.5em]\textcolor{blue}{5}\times15-\textcolor{green}{37}\times2&=\textcolor{red}{1}\end{align*}

さらに$\text{(a)'}$を代入すると

\begin{align*}(\textcolor{green}{42}-\textcolor{blue}{37})\times15-\textcolor{green}{37}\times2&=\textcolor{red}{1}\\[0.5em]\textcolor{green}{42}\times15-\textcolor{blue}{37}\times15-\textcolor{green}{37}\times2&=\textcolor{red}{1}\\[0.5em]\textcolor{green}{42}\times15+\textcolor{blue}{37}\times(-15-2)&=\textcolor{red}{1}\\[0.5em]\textcolor{green}{42}\times15+\textcolor{blue}{37}\times(-17)&=\textcolor{red}{1}\\[0.5em]\textcolor{blue}{37}\times(-17)+\textcolor{green}{42}\times15&=\textcolor{red}{1}\end{align*}

となり、問の1次不定方程式に近い形となります。

右辺は$3$なので、両辺に$3$を掛けますが、$x,y$それぞれの係数である$37,42$は変わらないようにします。

\begin{align*}\bigl\{\textcolor{blue}{37}\times(-17)+\textcolor{green}{42}\times15\bigr\}\times3&=\textcolor{red}{1}\times3\\[0.5em]\textcolor{blue}{37}\times(-17)\times3+\textcolor{green}{42}\times15\times3&=3\\[0.5em]\textcolor{blue}{37}\times(-51)+\textcolor{green}{42}\times45&=3\tag{d}\end{align*}

この式より整数解の1つは$x=-51,y=45$であることがわかります。

問の1次不定方程式と$\text{(d)}$の辺々を引くと

\begin{array}\ &37\quad x&+42\quad y&=3\\ -)&37\times(-51)&+42\times45&=3\\ \hline&37(x+51)&+42(y-45)&=0\end{array}

となり、さらに変形すると
\[37(x+51)=-42(y-45)\]
となります。
$37$と$42$が互いに素であることはすでにわかっているので、$37$と$-42$も互いに素であることがわかります。
このことから、この等式が成り立つ条件は両辺が因数に$37,-42$と任意の整数をもつことなので、任意の整数に$k$をもちいて

\begin{cases}x+51=-42k\\[0.5em]y-45=37k\end{cases}

となります。これらの式を整理すればすべての整数解は

\[x=-42k-51,y=37k+45\]

であることがわかります。

また、両辺の$k$以外の積が正となるように

\begin{cases}x+51=42k\\[0.5em]y-45=-37k\end{cases}

として、すべての整数解を

\[x=42k-51,y=-37k+45\]

とすることもできます。

(2)$84x-49y=21$

　$x,y$の係数が互いに素でない場合にはさらに2通りの場合があります。
$(2)$はそのうちの1つです。

ユークリッドの互除法をもちいて$x,y$の係数の最大公約数を求めます。$y$の係数は$-56$ですが、正負は無視して$56$として構いません。

\begin{align*}84\div49&=1\ 余り\textcolor{red}{35}\\[1em]49\div\textcolor{blue}{35}&=1\ 余り\textcolor{red}{14}\\[1em]35\div\textcolor{blue}{14}&=2\ 余り\textcolor{red}{7}\\[1em]14\div\textcolor{blue}{7}&=2\ 余り\textcolor{red}{0}\end{align*}

互除法で余りが$0$になったときの割る数$7$が$84$と$49$の最大公約数です。

さらに$84$と$49$の最大公約数$7$と定数項$21$の最大公約数を求めます。

$21$は$7$の倍数なので、$7$と$21$の最大公約数は$7$であることがわかります。

これはすなわち$84,49,21$の最大公約数が$7$であるということなので、両辺を$7$で割ります。

\[12x-7y=3\]

問の1次不定方程式の整数解はこれの整数解でもあるので、これを解きます。

$(1)$と同様に$x,y$の係数の最大公約数を求めます。

\begin{align*}\textcolor{green}{12}\div\textcolor{blue}{7}&=1\ 余り\textcolor{red}{5}\tag{e}\\[1em]\textcolor{green}{7}\div\textcolor{blue}{5}&=1\ 余り\textcolor{red}{2}\tag{f}\\[1em]\textcolor{green}{5}\div\textcolor{blue}{2}&=2\ 余り\textcolor{red}{1}\tag{g}\end{align*}

$12$と$7$が互いに素であることがわかります。

$\text{(e),(f),(g)}$を積と和の式に書き換え、右辺が余りだけになるように変形します。

\begin{align*}\text{(e)}:&\\ &&\textcolor{green}{12}&=\textcolor{blue}{7}\times1+\textcolor{red}{5}\\[0.5em]&&\textcolor{green}{12}-\textcolor{blue}{7}&=\textcolor{red}{5}\tag*{(e)'}\\[1em]\text{(f)}:&\\ &&\textcolor{green}{7}&=\textcolor{blue}{5}\times1+\textcolor{red}{2}\\[0.5em]&&\textcolor{green}{7}-\textcolor{blue}{5}&=\textcolor{red}{2}\tag*{(f)'}\\[1em]\text{(g)}:&\\ &&\textcolor{green}{5}&=\textcolor{blue}{2}\times2+\textcolor{red}{1}\\[0.5em]&&\textcolor{green}{5}-\textcolor{blue}{2}\times2&=\textcolor{red}{1}\tag*{(g)'}\end{align*}

$\text{(g)'}$に$\text{(e)',(f)'}$を代入すると

\begin{align*}\textcolor{green}{5}-(\textcolor{green}{7}-\textcolor{blue}{5})\times2&=\textcolor{red}{1}\\[0.5em]\textcolor{green}{5}+\textcolor{blue}{5}\times2-\textcolor{green}{7}\times2&=\textcolor{red}{1}\\[0.5em]\textcolor{blue}{5}\times3-\textcolor{green}{7}\times2&=\textcolor{red}{1}\\[0.5em](\textcolor{green}{12}-\textcolor{blue}{7})\times3-\textcolor{green}{7}\times2&=\textcolor{red}{1}\\[0.5em]\textcolor{green}{12}\times3-\textcolor{blue}{7}\times3-\textcolor{green}{7}\times2&=\textcolor{red}{1}\\[0.5em]\textcolor{green}{12}\times3-\textcolor{blue}{7}\times5&=\textcolor{red}{1}\end{align*}

両辺に$3$を掛けると

\begin{align*}(\textcolor{green}{12}\times3-\textcolor{blue}{7}\times5)\times3&=\textcolor{red}{1}\times3\\[0.5em]\textcolor{green}{12}\times3\times3-\textcolor{blue}{7}\times5\times3&=3\\[0.5em]\textcolor{green}{12}\times9-\textcolor{blue}{7}\times15&=3\tag{h}\end{align*}

この式より整数解の1つは$x=9,y=15$であることがわかります。

$12x-7y=3$と$\text{(h)}$の辺々を引くと

\begin{array}\ &12\quad x&-7\quad y&=3\\ -)&12\times9&-7\times15&=3\\ \hline&12(x-9)&-7(y-15)&=0\end{array}

となり、さらに変形すると

\[12(x-9)=7(y-15)\]

$12$と$7$は互いに素なので、この等式が成り立つ条件は任意の整数$k$をもちいて

\begin{cases}x-9=7k\\[0.5em]y-15=12k\end{cases}

となるので、これを整理してすべての整数解は

\[x=7k+9,y=12k+15\]

であることがわかります。

　このように$x,y$の係数が互いに素ではない場合、$x,y$の係数と定数項の最大公約数で方程式の両辺を割ることで、より簡単な形に直すことができるときがあります。

(3)$39x+52y=12$

　$(3)$も$x,y$の係数が互いに素でない場合ですが、$(2)$とは違う結果となります。

ユークリッドの互除法をもちいて$x,y$の係数の最大公約数を求めます。

\begin{align*}52\div\textcolor{blue}{39}&=1\ 余り\textcolor{red}{13}\\[1em]39\div\textcolor{blue}{13}&=3\ 余り\textcolor{red}{0}\end{align*}

$x,y$の係数の$39$と$52$の最大公約数は$13$であることがわかります。

今度は$39$と$52$の最大公約数$13$と定数項$12$の最大公約数を求めますが、これは$1$です。すなわち$13$と$12$は互いに素であることがわかります。

すると、問の1次不定方程式は以下のように変形できます。

\[13(3x+4y)=12\]

$x,y$は整数なので$3x+4y$も整数であり、左辺$13(3x+4y)$は$13$の倍数です。

しかし、右辺$12$は$13$の倍数ではありません。

したがって、問の1次不定方程式を成り立たせることができる整数$x,y$は存在しない、すなわち整数解は存在しません。

　このように$x,y$の係数の最大公約数が$1$でなく（互いに素でない）、かつその最大公約数と定数項が互いに素であるとき、整数解は存在しません。

関連：1次不定方程式の整数解を求める(1)