1次不定方程式 ax + by = c の解き方

1次不定方程式とは、 $a x + b y = c$ （ $a, b, c$ は整数の定数）の形をした方程式で、整数解 $(x, y)$ を求める問題です。解が存在する場合、無数に存在するのが特徴です。

解法の基本方針

1次不定方程式を解く手順は次のとおりです。

特殊解を1つ見つける

一般解の公式に当てはめる

条件があれば絞り込む

特殊解の見つけ方

特殊解を見つける方法はいくつかありますが、ユークリッドの互除法を逆にたどる方法が確実です。

$7 x + 5 y = 1$ の特殊解を求めてみましょう。

まず、ユークリッドの互除法で $g cd (7, 5)$ を求めます。

$7 = 5 \times 1 + 2$

$5 = 2 \times 2 + 1$

$2 = 1 \times 2 + 0$

次に、逆向きにたどって 1 を $7$ と $5$ の式で表します。

$1 = 5 - 2 \times 2$

$2 = 7 - 5 \times 1$

を代入すると

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

よって $7 \times (- 2) + 5 \times 3 = 1$ となり、特殊解 $(x, y) = (- 2, 3)$ が得られます。

一般解の公式

$a x + b y = c$ の特殊解を $(x_{0}, y_{0})$ とすると、一般解は次の式で表されます。

$x = x_{0} + \frac{b}{d} t, y = y_{0} - \frac{a}{d} t (t は任意の整数)$

ここで $d = g cd (a, b)$ です。

なぜこの公式が成り立つのか

$(x_{0}, y_{0})$ が解なら $a x_{0} + b y_{0} = c$ です。一般解を $(x_{0} + s, y_{0} + t)$ とすると、 $a (x_{0} + s) + b (y_{0} + t) = c$ より $a s + b t = 0$ が必要です。これを満たす整数 $s, t$ が公式の形になります。

d = 1

の場合

$a$ と $b$ が互いに素なら、一般解は $x = x_{0} + b t$ 、 $y = y_{0} - a t$ と簡単になります。

具体例

$7 x + 5 y = 1$ の一般解を求めます。

特殊解 $(x_{0}, y_{0}) = (- 2, 3)$ を先ほど求めました。 $g cd (7, 5) = 1$ なので、一般解は

$x = - 2 + 5 t, y = 3 - 7 t (t は任意の整数)$

$t = 0$ のとき $(x, y) = (- 2, 3)$ 、 $t = 1$ のとき $(x, y) = (3, - 4)$ などが解です。

右辺が 1 でない場合

$7 x + 5 y = 3$ のように右辺が 1 でない場合は、まず $7 x + 5 y = 1$ の解を求め、両辺を 3 倍します。

$7 \times (- 2) + 5 \times 3 = 1$ の両辺を 3 倍すると

$7 \times (- 6) + 5 \times 9 = 3$

よって特殊解は $(x_{0}, y_{0}) = (- 6, 9)$ で、一般解は

$x = - 6 + 5 t, y = 9 - 7 t$

となります。