「次の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$の係数は互いに素である場合です。
$(1)$の解き方は$x,y$の係数は互いに素である場合です。
ユークリッドの互除法をもちいて$x,y$の係数の最大公約数を求めます。
\begin{align*}\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)}$の辺々を引くと
\[37(x+51)=-42(y-45)\]
となります。
$37$と$42$が互いに素であることはすでにわかっているので、$37$と$-42$も互いに素であることがわかります。
このことから、この等式が成り立つ条件は両辺が因数に$37,-42$と任意の整数をもつことなので、任意の整数に$k$をもちいて
\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つです。
$(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$でなく（互いに素でない）、かつその最大公約数と定数項が互いに素であるとき、整数解は存在しません。
Share:
