なかけんの数学ノート

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

【標準】不定一次方程式の整数解 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$ が答えとなります。

おわりに

ここでは、係数の大きい不定一次方程式の整数解を解く方法を見てきました。係数をお互いに割って、係数を小さくしていくテクニックを使えば、解くことができます。

割り算をした余りに着目していく、というのは最大公約数を求めるときに使ったユークリッドの互除法と共通する部分がありますね。実際、上で書いたような方法を「拡張ユークリッド互除法」と呼ぶことがあります。

[広告]
対象者: 数学A
分野: 整数の性質
トピック: 整数
レベル: 応用
キーワード: 不定方程式, ユークリッドの互除法
更新日:2016/11/17