ベズーの等式とその証明

ベズーの等式とは
ベズーの等式の例
ベズーの等式の特別な場合
ベズーの等式の証明
ベズーの等式の拡張

ベズーの等式とは

初等整数論でよく知られている定理として, ベズーの等式というものがあります。
ベズーの等式は, 整数$a, b, c$に対して1次不定方程式$ax+by=c$が整数解をもつかどうかを調べられる強力な定理です。

※ベズーの等式は, 等式ではなく定理です。名前からすると等式を指しているように聞こえますが, そうではなくて以下の定理のことをいいます。

ベズーの等式

$a,b$を$0$でない整数とし, $d$を$a$と$b$の最大公約数とする。

このとき, $ax+by=d$をみたす整数$x, y$が存在する。

ベズーの等式の例

以下, 整数$a, b$の最大公約数を$\gcd(a, b)$と書くことにします。

例

$\gcd(9, 6)=3$なので, 方程式$9x+6y=3$は整数解をもつ。
実際, $x=-1, y=2$は解になっている。

例

$\gcd(5, 10)=5$なので, 方程式$5x+10y=5$は解をもつ。
実際, $x=3, y=-1$は解になっている。

ここでは実際に整数解を見つけていますが, ベズーの等式を用いれば, 実際に解を見つけなくてもこれらの1次不定方程式が整数解をもつことがすぐにわかりますね。

ベズーの等式の特別な場合

上のベズーの等式において$d=1$として, 以下の定理を得ます。

ベズーの等式の特別な場合

$a$と$b$が互いに素であるとき, すなわち$\gcd(a, b)=1$であるとき, $ax+by=1$を満たす整数$x, y$が存在する。

例

$\gcd(13, 19)=1$であるので, $13x+19y=1$をみたす整数$x, y$が存在する。

ベズーの等式の証明

ベズーの等式を証明していきましょう。割り算の余りを用いて考えることがポイントになります。
以下, 整数の集合を$\mathbb{Z}$とします。

ベズーの等式の証明

$$A=\{ax+by \mid x, y \in \mathbb{Z}, ax+by > 0\}$$
とする（つまり, $A$は整数$x,y$を用いて$ax+by$と表せる正の整数全体の集合）。

$A$に属する整数のうち最小のものを$m$とする。$m$は$A$の要素であるので, $aX+bY=m$となる整数$X, Y$が存在する。

$a$を$m$で割った商を$q$, 余りを$r \ (0 \leqq r < m)$とおく。すると$a=mq+r$より$r=a-mq$であるので
$$r=a-mq=a-(aX+bY)q=a(1-qX)+b(-qY)$$
となる。

$1-qX$, $-qY$はともに整数なので, もし$r>0$であれば$r$も$A$の要素となる。しかし$r<m$なので, $r$は$A$の最小値より小さいことになり矛盾。よって$r=0$である。

$a=mq+r$より$a=mq$なので, $m$は$a$の約数である。同様に, $m$は$b$の約数である。

これより$m$は$a$と$b$の公約数であるので, $m \leqq d$となる。

一方, $a$と$b$はともに$d$の倍数なので, $m=aX+bY$は$d$の倍数で正のもの, すなわち$d, 2d, 3d, \ldots$のいずれかである。

よって$m=d$である。

したがって$aX+bY=d$であり, 1次不定方程式$ax+by=d$は整数解をもつことがわかった。

ベズーの等式の拡張

上で見たベズーの等式は, 1次不定方程式$ax+by=d$が解をもつということを示す定理でした。
実は, より一般に次のことが成り立ちます。

この定理を用いると, 1次不定方程式がいつ整数解をもつかだけでなく, 逆にどんなときに整数解をもたないかまでわかります。

これはベズーの等式の拡張になっています。

ベズーの等式の拡張

$a, b$を$0$でない整数とし, $c$を整数とする。$d=\gcd(a, b)$とする。

このとき, 1次不定方程式$ax+by=c$が整数解をもつための必要十分条件は, $c$が$d$の倍数であることである。

この定理は, 1次不定方程式$ax+by=c$が整数解をもつための必要十分条件を与えています。
つまり, $a, b, c$の関係を調べるだけで, 整数解をもつかどうかをYES/NOで答えられるということです。

証明

$c$が$d$の倍数であるとする。
仮定より, $c=c’d$となる整数$c’$が存在する。

ベズーの等式から, $aX+bY=d$となる整数$X, Y$が存在する。

両辺に$c’$をかけると, $a(c’X)+b(c’Y)=c’d$, すなわち$a(c’X)+b(c’Y)=c$となる。

$X’=c’X, Y’=c’Y$とおくと, $X’, Y’$は整数で, $aX’+bY’=c$をみたす。

したがって方程式$ax+by=c$は整数解をもつ。

逆に, 方程式$ax+by=c$が整数解をもつとする。

$a, b$はともに$d$の倍数なので, $a=a’d, b=b’d$となる整数$a’, b’$が存在する。

仮定より$aX+bY=c$となる整数$X, Y$が存在し, $c=a’dX+b’dY=(a’X+b’Y)d$で$a’X+b’Y$は整数なので, $c$は$d$の倍数である。

例

$\gcd(4, 6)=2$で, $8$は$2$の倍数なので, 方程式$4x+6y=8$は整数解をもつ。
実際, $x=2, y=0$は解になっている。

例

$gcd(12, 18)=6$で, $42$は$6$の倍数なので, 方程式$12x+18y=42$は整数解をもつ。
実際, $x=2, y=1$は解になっている。

逆に, 与えられた方程式が整数解をもたない場合もあります。

例

$\gcd(6, 8)=2$であるが, $5$は$2$の倍数でないので, 方程式$6x+8y=5$は整数解をもたない。