Processing math: 100%
横画面推奨!
モバイル機器の場合、数式が見切れる場合があります。

2023年11月11日

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*}\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)
となります。
3742が互いに素であることはすでにわかっているので、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になったときの割る数78449の最大公約数です。
さらに8449の最大公約数7と定数項21の最大公約数を求めます。
217の倍数なので、721の最大公約数は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*}
127が互いに素であることがわかります。
\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)
127は互いに素なので、この等式が成り立つ条件は任意の整数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の係数の3952の最大公約数は13であることがわかります。
今度は3952の最大公約数13と定数項12の最大公約数を求めますが、これは1です。すなわち1312は互いに素であることがわかります。
すると、問の1次不定方程式は以下のように変形できます。
13(3x+4y)=12
x,yは整数なので3x+4yも整数であり、左辺13(3x+4y)13の倍数です。
しかし、右辺1213の倍数ではありません。
したがって、問の1次不定方程式を成り立たせることができる整数x,yは存在しない、すなわち整数解は存在しません。

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

Share:
share
◎Amazonのアソシエイトとして、当サイト「数学について考えてみる」は適格販売により収入を得ています。
Powered by Blogger.

PR

blogmura_pvcount
ブログランキング・にほんブログ村へ