ベズーの恒等式――整数と体上の多項式

目次

インタラクティブ

ベズーの係数は余りと一緒に運ばれる

拡張自動リセット

a = 30, b = 18 の拡張ユークリッド表

q	r	x	y	a·x + b·y

「拡張」を押して次の余りと係数を計算します。

a·x + b·y = gcd(a, b)

最大公約数は、2つの数を割り切るだけでなく、それらの整数係数の線形結合としても表せる。この性質は、たとえば剰余類の逆元を求める際に役立つ。$a=30,b=18$なら、ユークリッドの互除法で$30-18=12$、$18-12=6$、$12-2\cdot6=0$となるので、

$6=18-12=2\cdot18-30$

と書ける。ベズーの恒等式は、負の入力も含めて、このような係数が常に存在することを示す。

整数に対するベズーの恒等式

$a,b\in\mathbb Z$は同時に0ではないとし、$g=\gcd(|a|,|b|)>0$とする。このとき、ある整数$x,y$について

$ax+by=g$

が成り立つ。さらに、整数線形結合全体はちょうど$g$の倍数全体である。

$\{ax+by:x,y\in\mathbb Z\}=g\mathbb Z.$

最小の正の線形結合による証明

次の集合を考える。

$S=\{ax+by:x,y\in\mathbb Z,\ ax+by>0\}.$

$a,b$の少なくとも一方は0でないため、$S$は空ではない。0でない入力の絶対値は、その係数を必要に応じて$1$または$-1$とし、もう一方の係数を0にすれば正の結合として得られる。整列原理により、$S$には最小元$m=ax_0+by_0>0$がある。

$a$を$m$で割ると、$a=qm+r$、$0\le r<m$と書ける。$m=ax_0+by_0$だから、

$r=a-qm=a(1-qx_0)+b(-qy_0)$

であり、$r$も整数線形結合である。$r>0$なら$S$に属し、しかも$m$より小さいため、最小性に反する。よって$r=0$であり、$m\mid a$である。同じ議論を$b$に適用すると$m\mid b$も得られる。

$a,b$の任意の公約数は、すべての線形結合、特に$m$を割り切る。したがって$m$は正の公約数であり、すべての公約数の倍数でもあるので、最大公約数$g$に等しい。定義した表示から$ax_0+by_0=g$を得る。

$g$は$a,b$の両方を割るので、すべての$ax+by$を割る。一方、$ax_0+by_0=g$に任意の整数$n$を掛けると、$ng=a(nx_0)+b(ny_0)$となる。ゆえに線形結合全体はちょうど$g\mathbb Z$である。

多項式版――体上の場合

これは係数の範囲が異なる別の命題である。体$K$と、同時に0ではない$f,g\in K[x]$を考える。$d$を最高次係数が1の最大公約多項式、$I=(f,g)\subseteq K[x]$を$f,g$が生成するイデアルとすると、

$$\begin{aligned} uf+vg &= d\quad(u,v\in K[x]),\\ I=dK[x]. \end{aligned}$$

が成り立つ。

$I=\{uf+vg:u,v\in K[x]\}$の0でない元から次数が最小のものを選び、定数倍して最高次係数を1にし、これを$d$とする。体上の多項式除法で$f=qd+r$と書くと、$r=0$または$\deg r<\deg d$である。$d\in I$なので$r=f-qd\in I$でもあり、最小次数性から$r=0$となる。したがって$d\mid f$であり、同様に$d\mid g$である。$f,g$の任意の公約多項式は$I$のすべての元、特に$d$を割るので、$d$は最高次係数が1の最大公約多項式である。また$d\in I$だから$uf+vg=d$と表せる。すべての結合は$d$で割り切れ、上の表示に任意の多項式$h$を掛ければ$hd=(hu)f+(hv)g$となるため、$d$の倍数はすべて結合である。よって$I=dK[x]$である。この証明は体上の多項式除法を使っており、任意の係数環について主張するものではない。

出典とクレジット

多項式への拡張は、2022-04-03に0archlinux0 / MINJUN PARKが公開し、CC BY 4.0と表示したTistory ID 25をきっかけとしている。出典ページでは多項式版の命題が述べられているが、証明は掲載されていない。上では体上の証明を別途示した。