ベズーの等式
問題
$ a, b, c \in \mathbb {Z} のとき$ ax + by = c の整数解$ (x, y) を求めよ
補題A
$ a, b が互いに素な整数ならば解が存在する。逆は必ずしも真ではない。 証明
$ ax + by = c より$ ax = c - by \equiv c (\bmod b)
$ a, b は互いに素だからこの式は$ x \equiv k (\bmod b) \Leftrightarrow x = bn + k (n \in \mathbb{Z}) の形の解を持つ(一次合同方程式が解を持つ条件)。 これを元の式に代入して$ by = c - a(bn+k) = -abn + (c-ak)
ここで、$ ak \equiv ax \equiv c (\bmod b) より、$ c-ak は$ b で割り切れる。そこで商を$ l とすると、$ y = -an + lを得る。
よって、$ x = bn + k, y = -an + l が解である。
NOTE
解を元の式に代入すると$ ak - bl = c であるから、$ ax + by は$ c の倍数全体を動く。
つまり、$ \{ ax + by | x, y \in \mathbb {Z} \} = \{ cn | n \in \mathbb{Z} \} である。
実際、任意の整数$ m \in \mathbb{Z} に対して、$ x = mk, y = -ml とすると、$ ax + by = m(ak-bl) = cm である。
補題B
下記は同値である。
$ ax + by = c の整数解$ (x, y) が存在する。
$ c が$ \gcd(a, b) の倍数である。
証明
$ d = \gcd(a, b) とする。
必要性
対偶を示す。
$ c が$ d の倍数でないとき、左辺は$ d の倍数だが右辺は$ d の倍数ではないためこの式を満たす$ x, y は存在しない。
十分性
$ a' = a/d, b' = b/d, c' = c/d とすると
$ d = \gcd(a, b) より$ a', b' は整数かつ互いに素な整数。 仮定より$ c' は整数。
よって補題Aより$ a'x+b'y=c' は解を持つ。
両辺を$ d 倍すると元の式に一致するので、この解はもとの式の解に一致する。