問題
次の問に答えよ。
(1) 2元1次不定方程式 $ 31x+19y=1 $ の整数解をすべて求めよ。 (2) $19$ で割り切れ、$31$ で割ると $1$ 余る最小の自然数を求めよ。
(3) $19$ で割ると $10$ 余り、$31$ で割ると$20$ 余る最小の自然数を求めよ。
(1) 2元1次不定方程式 $ 31x+19y=1 $ の整数解をすべて求めよ。 (2) $19$ で割り切れ、$31$ で割ると $1$ 余る最小の自然数を求めよ。
(3) $19$ で割ると $10$ 余り、$31$ で割ると$20$ 余る最小の自然数を求めよ。
（１）解答・解説
方針
\[
31x+19y=1 \hspace{5mm} \cdots \mbox{①} \]
の係数の小さいほうの19を法とする合同式を考えます。合同式を考えるときは、法の数で割ったときの割り切れずに残る数字を考えることになります。
\[ 31=19 \times 1 +12 \]
なので、
\[ 31 \equiv 12 \pmod{19} \]
と書けて、$19y$は割り切れるので、元の式は
\[ 12x \equiv 1 \pmod{19} \hspace{5mm} \cdots \mbox{②} \]
となります。慣れないうちは意味を考えてみてください。上の式の意味は
\[ 12x \mbox{は} 19 \mbox{で割ると} 1 \mbox{あまる} \]
ということです。あとは、左辺の係数が1になるように計算するのですが、このブログでは左辺の$x$の係数を12からさらに19だけずれた-7にすることによってもう一本
\[ -7x \equiv 1 \pmod{19} \hspace{5mm} \cdots \mbox{③} \]
という合同式を立てて、これらを加減法により連立して計算しています。他の問題でも練習してみたいという方は【ユークリッドの互除法は無理という人へ】不定方程式は合同式を試してみて というブログ記事もご覧ください。
ただし、① → ② や③ は言えますが、② → ① はもちろん言えません。①以外に②や③が成立するのは
\[ 31x+19y=20 \ \mbox{や} \ 31x+19y=-18 \]
など無限にあります。(①に戻らない人などいないとは思いますが)気になる人は、必要条件であることをハッキリと明示してください。
（１）解答
\[
31x+19y=1 \hspace{5mm} \cdots \mbox{①}
\]
19を法とする合同式を考えると①を満たす整数 $x,\, y$ が存在するためには
\begin{cases}
12x \equiv 1 \pmod{19} \hspace{5mm} \cdots \mbox{②}\\
-7x \equiv 1 \pmod{19} \hspace{5mm} \cdots \mbox{③}
\end{cases}
でなければならないが、②×3+③×5を作ると
\begin{eqnarray}
(36-35)x &\equiv& 3\cdot1 + 5\cdot1 \pmod{19} \\
x &\equiv& 8 \pmod{19}
\end{eqnarray}
となるので、
\[
x = 8 + 19t \quad (t\mbox{は整数})
\]
と表せる。これを①に代入すると
\begin{eqnarray}
31(8+19t) + 19y &=& 1 \\
19y &=& -247 + 31 \times 19t \\
y &=& -13 – 31t
\end{eqnarray}
したがって、求める整数解は
\[
(x,y) = (8+19t,\,-13-31t) \quad (tは\mbox{整数}) \hspace{5mm} \mbox{(答)}
\]
（２）解答・解説
問題文から式を作っていると（１）の結果を利用できるのではと気づくのではないでしょうか？
もちろん（１）の誘導がない場合もあります。
（２）解答
19 で割り切れ、31 で割ると 1 余る自然数を$N$とすると
\begin{cases}
N = 19n \hspace{5mm} (n\mbox{は自然数})\\
N = 31m+1 \hspace{5mm} (m\mbox{は負でない整数})
\end{cases}
と表せるので
\[ 19n=31m+1\]
すなわち
\[
-31m+19n=1
\]
ここで、$m=-x, n=y$ とおくと、(1)の結果より
\[
(m,n) = (-8-19t,\,-13-31t) \quad (tは\mbox{負の整数})
\]
これより、$t=-1$ すなわち $(m,n)=(11,18)$ のとき、$N$は最小値
\[ 19 \cdot 18 = 342 \hspace{5mm} \mbox{(答)}
\]
をとる。
（３）解答・解説
（２）と同じように式を立ててみます。
19で割ると10余り，31で割ると20余る自然数を$M$とすると
\begin{cases}
M = 19p+10 \hspace{5mm} (p\mbox{は負でない整数})\\
M = 31q+20 \hspace{5mm} (q\mbox{は負でない整数})
\end{cases}
と表せるので
\[
19p+10=31q+20
\]
すなわち
\[
-31q+19p=10 \hspace{5mm} \cdots \mbox{④}
\]
となるが、④を満たす整数 $p,\, q$ が存在するためには
\begin{cases}
-12q \equiv 10 \pmod{19} \hspace{5mm} \cdots \mbox{⑤} \\
7q \equiv 10 \pmod{19} \hspace{5mm} \cdots \mbox{⑥}
\end{cases}
でなければならない。ここで⑤×3+⑥×5を作ると
\begin{eqnarray}
-q &\equiv& 80 \equiv 4 \pmod{19} \\
q &\equiv& -4 \pmod{19}
\end{eqnarray}
となるので、
\[
q = -4 + 19u \quad (u\mbox{は自然数})
\]
と表せる。これを④に代入すると
\begin{eqnarray}
-31(-4 + 19u)+19p &=& 10 \\
19p &=& 114 + 31 \times 19u \\
p &=& 6 + 31u
\end{eqnarray}
以上より
\[
(p,q) = (6 + 31u,\,-4 + 19u) \quad (uは\mbox{自然数})
\]
よって、$u=1$ すなわち $(p,q)=(37,15)$のとき、自然数$M$は最小値
\[ 31 \times 15 +20 = 485 \hspace{5mm} \mbox{(答)}
\]
をとる。
コメント