不定方程式の応用問題

1次不定方程式は、日常的な場面を題材にした応用問題として出題されることが多いです。ここでは代表的なパターンを見ていきます。

両替問題

50円玉と80円玉を使って、ちょうど410円を支払う方法を考えます。50円玉を $x$ 枚、80円玉を $y$ 枚とすると

$50 x + 80 y = 410$

という不定方程式になります。

まず、両辺を 10 で割って簡単にします。

$5 x + 8 y = 41$

$g cd (5, 8) = 1$ で、 $41$ は $1$ の倍数なので整数解は存在します。

特殊解を見つけます。 $5 \times (- 3) + 8 \times 2 = 1$ なので、両辺を 41 倍して

$5 \times (- 123) + 8 \times 82 = 41$

一般解は $x = - 123 + 8 t$ 、 $y = 82 - 5 t$ です。

硬貨の枚数なので $x \geq 0$ 、 $y \geq 0$ の条件を課します。

x \geq 0

より

$- 123 + 8 t \geq 0$ なので $t \geq 15.375$ 、つまり $t \geq 16$

y \geq 0

より

$82 - 5 t \geq 0$ なので $t \leq 16.4$ 、つまり $t \leq 16$

$t = 16$ のみが条件を満たし、 $(x, y) = (5, 2)$ が唯一の解です。50円玉 5 枚と 80円玉 2 枚で 410 円になります。

ある整数を 5 で割ると 3 余り、7 で割ると 2 余ります。このような整数で最小の正の整数を求めます。

求める整数を $n$ とすると

$n = 5 a + 3 = 7 b + 2$

（ $a, b$ は 0 以上の整数）

これを整理すると

$5 a - 7 b = - 1$

$5 \times 3 - 7 \times 2 = 1$ なので、両辺を $- 1$ 倍して

$5 \times (- 3) - 7 \times (- 2) = - 1$

一般解は $a = - 3 + 7 t$ 、 $b = - 2 + 5 t$ です。

$a \geq 0$ より $t \geq 1$ 、 $b \geq 0$ より $t \geq 1$ なので、 $t = 1$ のとき最小となります。

$a = 4$ を代入して $n = 5 \times 4 + 3 = 23$ が答えです。

100 以下の正の整数で、 $3 x + 7 y = 100$ を満たす $(x, y)$ （ $x, y$ は正の整数）の組の個数を求めます。

$3 \times (- 2) + 7 \times 1 = 1$ より、両辺を 100 倍して特殊解 $(x_{0}, y_{0}) = (- 200, 100)$ を得ます。

一般解は $x = - 200 + 7 t$ 、 $y = 100 - 3 t$ です。

$x > 0$ より $t > 28.57...$ 、つまり $t \geq 29$

$y > 0$ より $t < 33.33...$ 、つまり $t \leq 33$

$t = 29, 30, 31, 32, 33$ の 5 通り

よって、正の整数解は 5 組存在します。

式を簡単にする

係数に公約数があれば、先に割って数を小さくします。計算ミスが減ります。

条件を不等式に変換

「正の整数」「0 以上」などの条件を $t$ の不等式に直し、 $t$ の範囲を求めます。

応用問題では、不定方程式を立てることと、追加条件から $t$ の範囲を絞ることの両方が重要です。