1次不定方程式の整数解を求める(2) ~ 数学について考えてみる

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

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

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

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

x, y

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

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

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

　1次不定方程式の

x, y

$x,y$ の係数は互いに素である場合とそうでない場合の2通りが存在します。

(1)

$(1)$ の解き方は

x, y

$x,y$ の係数は互いに素である場合です。

ユークリッドの互除法をもちいて

x, y

$x,y$ の係数の最大公約数を求めます。

\begin{matrix} 42 \div 37 & = 1 余 り 5 37 \div 5 & = 7 余 り 2 5 \div 2 & = 2 余 り 1 \\ (a) (b) (c) \end{matrix}

$\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

$1$ になるのは2つの数が互いに素（最大公約数が

1

$1$ ）である場合だけです。なので、余りに

1

$1$ が現れた時点で終わります。

(a),(b),(c)

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

\times

$×$ は残しておきます。（

\times 1

$×1$ の場合は消しても構いません。）

\begin{matrix} (a) : 42 & = 37 \times 1 + 5 42 - 37 & = 5 (b) : 37 & = 5 \times 7 + 2 37 - 5 \times 7 & = 2 (c) : 5 & = 2 \times 2 + 1 5 - 2 \times 2 & = 1 \\ (a)' (b)' (c)' \end{matrix}

$\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*}$

(c)'

$\text{(c)'}$ に

(a)',(b)'

$\text{(a)',(b)'}$ を代入し、左辺が

x, y

$x,y$ の係数それぞれの倍数の和または差、右辺が

1

$1$ の式をつくります。

(1)

$(1)$ の場合は1次不定方程式の左辺が

37

$37$ の倍数と

42

$42$ の倍数の和なので同様にします。ただし、代入をするのは商にあたる数以外の赤、青、緑に着色した数に対してのみです。

(c)'

$\text{(c)'}$ に

(b)'

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

\begin{matrix} 5 - (37 - 5 \times 7) \times 2 & = 1 5 - 37 \times 2 + 5 \times 14 & = 1 (5 + 5 \times 14) - 37 \times 2 & = 1 5 \times (1 + 14) - 37 \times 2 & = 1 5 \times 15 - 37 \times 2 & = 1 \end{matrix}

$\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*}$

さらに

(a)'

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

\begin{matrix} (42 - 37) \times 15 - 37 \times 2 & = 1 42 \times 15 - 37 \times 15 - 37 \times 2 & = 1 42 \times 15 + 37 \times (- 15 - 2) & = 1 42 \times 15 + 37 \times (- 17) & = 1 37 \times (- 17) + 42 \times 15 & = 1 \end{matrix}

$\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$ なので、両辺に

3

$3$ を掛けますが、

x, y

$x,y$ それぞれの係数である

37, 42

$37,42$ は変わらないようにします。

\begin{matrix} {37 \times (- 17) + 42 \times 15} \times 3 & = 1 \times 3 37 \times (- 17) \times 3 + 42 \times 15 \times 3 & = 3 37 \times (- 51) + 42 \times 45 & = 3 \\ (d) \end{matrix}

$\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

$x=-51,y=45$ であることがわかります。

問の1次不定方程式と

(d)

$\text{(d)}$ の辺々を引くと

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

$\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(x+51)=-42(y-45)$
となります。

37

$37$ と

42

$42$ が互いに素であることはすでにわかっているので、

37

$37$ と

- 42

$-42$ も互いに素であることがわかります。
このことから、この等式が成り立つ条件は両辺が因数に

37, - 42

$37,-42$ と任意の整数をもつことなので、任意の整数に

k

$k$ をもちいて

{\begin{matrix} x + 51 = - 42 k y - 45 = 37 k \end{matrix}

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

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

x = - 42 k - 51, y = 37 k + 45

$x=-42k-51,y=37k+45$

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

また、両辺の

k

$k$ 以外の積が正となるように

{\begin{matrix} x + 51 = 42 k y - 45 = - 37 k \end{matrix}

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

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

x = 42 k - 51, y = - 37 k + 45

$x=42k-51,y=-37k+45$

とすることもできます。

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

x, y

$x,y$ の係数が互いに素でない場合にはさらに2通りの場合があります。

(2)

$(2)$ はそのうちの1つです。

ユークリッドの互除法をもちいて

x, y

$x,y$ の係数の最大公約数を求めます。

y

$y$ の係数は

- 56

$-56$ ですが、正負は無視して

56

$56$ として構いません。

\begin{matrix} 84 \div 49 & = 1 余 り 35 49 \div 35 & = 1 余 り 14 35 \div 14 & = 2 余 り 7 14 \div 7 & = 2 余 り 0 \end{matrix}

$\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

$0$ になったときの割る数

7

$7$ が

84

$84$ と

49

$49$ の最大公約数です。

さらに

84

$84$ と

49

$49$ の最大公約数

7

$7$ と定数項

21

$21$ の最大公約数を求めます。

21

$21$ は

7

$7$ の倍数なので、

7

$7$ と

21

$21$ の最大公約数は

7

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

これはすなわち

84, 49, 21

$84,49,21$ の最大公約数が

7

$7$ であるということなので、両辺を

7

$7$ で割ります。

12 x - 7 y = 3

$12x-7y=3$

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

(1)

$(1)$ と同様に

x, y

$x,y$ の係数の最大公約数を求めます。

\begin{matrix} 12 \div 7 & = 1 余 り 5 7 \div 5 & = 1 余 り 2 5 \div 2 & = 2 余 り 1 \\ (e) (f) (g) \end{matrix}

$\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

$12$ と

7

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

(e),(f),(g)

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

\begin{matrix} (e) : 12 & = 7 \times 1 + 5 12 - 7 & = 5 (f) : 7 & = 5 \times 1 + 2 7 - 5 & = 2 (g) : 5 & = 2 \times 2 + 1 5 - 2 \times 2 & = 1 \\ (e)' (f)' (g)' \end{matrix}

$\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*}$

(g)'

$\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$ でなく（互いに素でない）、かつその最大公約数と定数項が互いに素であるとき、整数解は存在しません。

数学について考えてみる

2023年11月11日