1次不定方程式の整数解の存在条件

1次不定方程式 $a x + b y = c$ が整数解を持つかどうかは、 $a, b, c$ の関係で決まります。闘雲に解こうとする前に、まず解が存在するかを確認することが大切です。

存在条件

$a x + b y = c$ が整数解を持つための必要十分条件は次のとおりです。

整数解が存在する条件

$g cd (a, b)$ が $c$ を割り切る

言い換えると

$c$ が $g cd (a, b)$ の倍数である

この条件を満たさないとき、どんなに頑張っても整数解は見つかりません。

$d = g cd (a, b)$ とします。 $a = d a^{'}$ 、 $b = d b^{'}$ と書けるので

$a x + b y = d (a^{'} x + b^{'} y)$

となります。左辺は必ず $d$ の倍数です。したがって、 $c$ が $d$ の倍数でなければ、等式は成り立ちません。

逆に、 $c$ が $d$ の倍数であれば、ベズーの等式により解が存在することが保証されます。

ベズーの等式とは、任意の整数 $a, b$ に対して $a x + b y = g cd (a, b)$ を満たす整数 $x, y$ が存在するという定理です。これはユークリッドの互除法を逆にたどることで構成的に証明できます。

2つの整数の最大公約数を求めるアルゴリズム。

6 x + 9 y = 12

$g cd (6, 9) = 3$ で、 $12$ は $3$ の倍数なので、整数解が存在します。実際、 $(x, y) = (2, 0)$ や $(x, y) = (- 1, 2)$ などが解です。

6 x + 9 y = 7

$g cd (6, 9) = 3$ で、 $7$ は $3$ の倍数でないので、整数解は存在しません。 $6 x + 9 y$ は常に $3$ の倍数になるため、 $7$ にはなり得ません。

1次不定方程式の整数解の有無を判定する手順は次のとおりです。

$g cd (a, b)$ を求める

$c$ が $g cd (a, b)$ で割り切れるか確認

割り切れれば解あり、割り切れなければ解なし

整数解が存在する場合、解は無数に存在します。1つの特殊解 $(x_{0}, y_{0})$ が見つかれば、一般解は

$x = x_{0} + \frac{b}{d} t, y = y_{0} - \frac{a}{d} t$

（ $d = g cd (a, b)$ 、 $t$ は任意の整数）

の形で表され、 $t$ に任意の整数を代入することで無限に解が得られます。

問題によっては「正の整数解」「自然数解」など、追加の条件がつくことがあります。その場合は一般解を求めてから、条件を満たす $t$ の範囲を絞り込む必要があります。

存在条件の確認は、不定方程式を解く際の最初のステップとして習慣づけておくとよいでしょう。