【応用】不定一次方程式係数が大きい場合

🕒 2016/05/07 🔄 2023/05/01

【標準】不定一次方程式の整数解 ax+by=cの場合では、不定一次方程式「$ax+by=c$」の整数解を考えました。その解法では、まず「式を満たす解を1つ見つける」（つまり、「特殊解」を見つける）のですが、係数が大きい場合には解を見つけることが大変です。ここでは、そうした場合に、どうやって解いていけばいいかを解説していきます。

📘 目次

例題

次のような、係数が大きい場合の不定一次方程式を考えてみます。

例題

次の方程式の整数解を求めなさい。\[ 47x+531y=1 \]

係数が大きすぎて、これを満たす解を1つ見つけるのが大変です。いきなりつまずいてしまいます。なので、係数が大きい場合には、「係数を小さくする」ためのテクニックを使います。

531を47で割ると、次の式が成り立つことが分かります。\[ 531=47\times 11+14 \]これをもとの式に代入すると、次のようになります。
\begin{eqnarray} 47x+531y &=& 1 \\ 47x+(47\cdot 11+14)y &=& 1 \\ 47x+47\cdot 11y+14y &=& 1 \\ 47(x+11y)+14y &=& 1 \\ \end{eqnarray}ここで、$p=x+11y$ (pは整数)とおくと、\[47p+14y=1\]となりますね。係数が小さくなって、考えやすくなりました。係数の割り算により、係数を小さくすることができるんですね。

これをもう一度繰り返せば、係数をもっと小さくできます。同じようにして47を14で割ると、次が分かります。\[ 47 = 14\times 3+5 \]これを上の式に入れれば、
\begin{eqnarray} 47p+14y &=& 1 \\ (14\times 3+5)p+14y &=& 1 \\ 14\times 3p +5p+14y &=& 1 \\ 5p+14(3p+y) &=& 1 \\ \end{eqnarray}ここで、$q=3p+y$ (qは整数)とおけば、\[ 5p+14q=1 \]となります。かなり考えやすくなりました。

ここまで来れば、これを満たす整数解も見つけやすいですね。 $(p,q)=(3,-1)$ が解の1つであることがわかります。このときの $x,y$ を求めるために、今度はこれを逆にたどっていきます。

$q=3p+y$ だったので、
\begin{eqnarray} y &=& q-3p \\ &=& -1-3\cdot 3 \\ &=& -10 \end{eqnarray}とわかります。また、 $p=x+11y$ だったので、 \begin{eqnarray} x &=& p-11y \\ &=& 3-11\cdot(-10) \\ &=& 113 \\ \end{eqnarray}と求められます。実際、元の式 $47x+531y=1$ の左辺にこれらを代入してみると \begin{eqnarray} & & 47\cdot 113 +531\cdot(-10) \\ &=& 5311 -5310 \\ &=& 1 \end{eqnarray}となるので、成り立つことが分かりますね。これをもとの式のまま、数字を1から代入していって見つけるのは至難の業です。

解の1つ、つまり、特殊解が見つかれば、後は同じ流れです。
\begin{array}{llllll} & 47x & + & 531y & = & 1 \\ -) & 47\cdot 113 & + & 531 \cdot (-10) & = & 1 \\ \hline & 47(x-113) & + & 531 (y+10) & = & 0 \\ \end{array}なので、 $47(x-113)=-531(y+10)$ となります。よって、整数 k を用いて、 $x=531k+113$, $y=-47k-10$ が答えとなります。