§A4.3一次不定方程式 ax + by = c

1 解を持つ条件——ベズーの等式

まず、そもそも整数解が存在するかどうかを判定できます。

$ax + by = c$が整数解を持つための必要十分条件は、$\gcd(a, b)$が$c$を割り切ることです。 特に$\gcd(a, b) = 1$なら、$c$がどんな整数でも解が存在します。必要なことはすぐに分かります——解$(x, y)$が1つでもあれば、左辺$ax + by$は$a$と$b$の公約数$\gcd(a, b)$で必ず割り切れるので、それに等しい右辺$c$も割り切れていなければなりません。本題は十分性、つまり「割り切れさえすれば本当に解が作れる」ほうです。

これは互除法を「逆向きにたどる」ことで具体的に確かめられます。互除法の各ステップを逆にたどっていくと、$\gcd(a, b)$そのものを$a$と$b$の整数係数の和として書く式（ベズーの等式$ax + by = \gcd(a, b)$）が作れるのです。実際に$1071x + 1029y = 21$の特殊解を作ってみます。互除法の計算は前回の記事の通りです。

1. $1071 = 1 \times 1029 + 42$
2. $1029 = 24 \times 42 + 21$
3. $42 = 2 \times 21 + 0$

これを下から一つずつ、余りについて逆に解いていきます。

$21 = 1029 - 24 \times 42$

次に$42 = 1071 - 1029$を代入します。

$21 = 1029 - 24 \times (1071 - 1029) = 25 \times 1029 - 24 \times 1071$

つまり$1071 \times (-24) + 1029 \times 25 = 21$です。$c = 21$はちょうど$\gcd(1071, 1029)$そのものなので、これがそのまま特殊解$(x_0, y_0) = (-24, 25)$になります。$c$が$\gcd$の倍数（たとえば$c = 63 = 3 \times 21$）であれば、この特殊解を$3$倍すればよいだけです。

2 一般解——特殊解に「ずれ」を足す

特殊解が1つ見つかれば、あとは全部の解を機械的に書き下せます。$d = \gcd(a, b)$、$(x_0, y_0)$を特殊解とすると、一般解は

$x = x_0 + \frac{b}{d}t, \qquad y = y_0 - \frac{a}{d}t \qquad (t \text{ は任意の整数})$

と表せます。$t$を$1$ずらすごとに$x$が$b/d$だけ増え、$y$が$a/d$だけ減ることで、$ax + by$の値がちょうど打ち消し合って変わらないという仕組みです。符号の付け方（$+bt/-at$か$-bt/+at$か）はどちらでも構わず、流儀の違いに過ぎません。