【標準】不定一次方程式の整数解 ax+by=cの場合
【基本】不定一次方程式の整数解 ax+by=0の場合では、不定一次方程式「$ax+by=0$」の整数解を考えました。ここでは、これより少し難しい「$ax+by=c$」の場合、つまり、右辺が0でないケースを考えてみましょう。
なお、このページでは、 a, b, c はすべて0でない整数とします。
例題
次の例題を考えます。
【導入】不定一次方程式の整数解で見た通り、文字が2つで式が1つなので、答えは一つには決まりません。例えば、 $(x,y)=(-1,1)$ という解もあるし、 $(x,y)=(-333,250)$ という解もあります。解は無限にあります。
右辺が0の場合、つまり、【基本】不定一次方程式の整数解 ax+by=0の場合では、簡単に解けます。 $ax=-by$ と変形すれば、 x が b の倍数であることが分かります（係数が互いに素の場合）。しかし、今回は c が邪魔なので、このような解き方はできません。
そこで、次のようなテクニックを使って、 c を消してみます。まずは、この式を満たす解を1つ見つけます。このような、不定方程式を満たす1組の解のことを、特殊解 (particular solution)と呼びます。上で書いた通り、 $(x,y)=(-1,1)$ が解の1つなので、これを使いましょう。
これを式で書けば、次のようになります。\[ 3\cdot (-1) +4\cdot 1=1 \]ここで、元の式と並べて、辺々引いてみると、右辺同士が消えるんですよね。
\begin{array}{llllll}
& 3x & + & 4y & = & 1 \\
-) & 3\cdot(-1) & + & 4\cdot 1 & = & 1 \\
\hline
& 3(x+1) & + & 4(y-1) & = & 0 \\
\end{array}この変形ができれば、すでに見たことのある式です。 $X=x+1$, $Y=y-1$ とすれば、 $3X+4Y=0$ ですからね。
ここから先は、右辺が0のときと同様にすれば解けます。\[ 3(x+1)=-4(y-1) \]が成り立つので、左辺は4の倍数。よって、整数 k を用いて、 $x+1=4k$ と書けるので、$x=4k-1$ となります。これを上の式に代入すると $-(y-1)=3k$ なので、 $y=-3k+1$ となります。以上から、解は次のようになります。
$(x,y) = (4k-1,-3k+1)$ (k は整数)
例えば、序盤で書いた $(x,y)=(-1,1)$ という解は、$k=0$に対応します。また、 $(x,y)=(-333,250)$ は $k=-83$ に対応しています。
解き方のまとめ
$ax+by=c$ の整数解を求める方法をまとめておきましょう。
まずは、$ax+by=c$ を満たす整数解の1つ（特殊解）を見つけます。小さい数字からいくつか代入していけば見つかります。その解を $(x,y)=(p,q)$ としましょう。このとき、\[ ap+bq=c \]が成り立ちます。そして、元の式とこの式を並べて、辺々を引きます。
\begin{array}{llllll}
& ax & + & by & = & c \\
-) & ap & + & bq & = & c \\
\hline
& a(x-p) & + & b(y-q) & = & 0 \\
\end{array}
あとは、【基本】不定一次方程式の整数解 ax+by=0の場合を参考にすれば、答えまでたどり着けるでしょう。
この解法で一番重要なポイントは、これです。
いくつかの疑問
さて、「不定一次方程式： $ax+by=c$ 」の解き方を紹介しましたが、いくつか疑問がわいてくるかもしれません。
例えば、解法の序盤で「$ax+by=c$ を満たす整数解の1つ（特殊解）を見つける」と書きましたが、いつも見つかるのでしょうか。実は、 $a,b$ の最大公約数が c を割り切ることができるなら、いつでも見つかります。特に、最大公約数が1の場合は、c はどんな整数であっても見つかります。
「整数解が１つは見つかるのはわかった。でも、解が $(x,y)=(10000,30000)$ みたいな大きな数だったら、見つかる気がしないぞ！」と思う人もいるかもしれません。しかし、実は、 $x=1$ から $x=|b|$ までを考えるだけでOKです。解がある場合は、この範囲で必ず見つかります。
「整数解を探す範囲が限定されるのはわかった。でも、結局、 $a,b$ が大きかったら解を見つけるのが大変なのでは？」という疑問もあるでしょう。このケースは、「【応用】不定一次方程式 係数が大きい場合」で説明します。係数が大きい場合は、もう少し下準備が必要になります。
おわりに
ここでは、係数が小さい場合の不定一次方程式の解き方を見ました。答えを出すまでのステップが多いですが、流れを理解すればできないことはないでしょう。よく練習して、身につけておきましょう。
また、入試では係数が大きい場合もよく出題されるので、【応用】不定一次方程式 係数が大きい場合も合わせて見ておきましょう。
