「次の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: