Bézoutの等式
概要
Bézoutの等式（Bézout's identity）とは、少なくとも一方が $0$ でない整数 $a,b$ の最大公約数 $d=\gcd(a,b)$ が、ある整数 $x,y$ により $d=ax+by$ と書けるという定理である。$ax+by$ の形の整数全体はちょうど $d$ の倍数全体であり、係数 $x,y$ は Euclid の互除法の各段を記録する拡張互除法で計算できる。合同式の逆元の存在、1 次不定方程式 $ax+by=c$ の可解条件 $d\mid c$、互いに素であることの判定はこの等式から従う。単項イデアル整域では $(a,b)=(d)$ として同じ主張が成り立つが、$\mathbb{Z}[x]$ の $2$ と $x$ のように、最大公約元 $1$ が線形結合で書けない環もある。
前提知識: 整数, 約数, 除法の原理, イデアル
Bézoutの等式は、2 つの整数の最大公約数が、その 2 数に整数を掛けて足したもの（整数係数の線形結合）として書けることを主張する。最大公約数は「共通の約数のうち最大のもの」として外側から定義されるが、この等式は同じ数を $ax+by$ という形で内側から作り出す。係数 $x,y$ は Euclidの互除法 の計算を記録するだけで具体的に求まり、合同式の逆元、1 次の不定方程式（一次不定方程式）、互いに素であることの判定、中国剰余定理など、初等整数論の多くの議論がこの等式から出発する。
動機
$12$ と $18$ の公約数は $\pm1,\pm2,\pm3,\pm6$ であり、最大のものは $6$ である。一方、$12x+18y$ の形の整数を並べると、$12\cdot(-1)+18\cdot1=6$、$12\cdot2+18\cdot(-1)=6$、$12\cdot3+18\cdot(-2)=0$、$12\cdot1+18\cdot1=30$ のように、現れるのはすべて $6$ の倍数であり、しかも $6$ 自身が現れる。$12x+18y$ が $6$ の倍数になることは、$6$ が $12$ と $18$ をともに割り切ることから明らかである。意外なのは逆向き、すなわち最大公約数そのものが線形結合として実際に現れることであり、これが Bézout の等式の内容である。
イデアルの言葉では、$12x+18y$ の全体は $12$ と $18$ が生成する $\mathbb{Z}$ のイデアル $(12,18)$ であり、等式は $(12,18)=(6)$ と言い換えられる。この読み替えにより、等式は整数だけでなく、すべてのイデアルが 1 つの元で生成される単項イデアル整域へと一般化される。逆に、等式が成り立たない環もある（ex-bezout-identity-z-x）。任意の 2 元について等式が成り立つ整域は Bezout 整域と呼ばれ、単項イデアル整域より広い（Bezout環）。
仮定と定理
整数 $a,b$ に対し、$a$ と $b$ をともに割り切る整数を $a,b$ の 公約数 という。
$a,b$ を整数とし、少なくとも一方は $0$ でないとする。$a,b$ の公約数のうち最大のものを $a,b$ の 最大公約数（greatest common divisor）といい、$\gcd(a,b)$ と書く。$a=b=0$ のときは $\gcd(0,0):=0$ と約束する。$\gcd(a,b)=1$ のとき、$a$ と $b$ は 互いに素 であるという。
$a\neq0$ なら $a$ の約数 $c$ は $|c|\leq|a|$ を満たすので、公約数は有限個であり、$1$ はつねに公約数である。よって最大公約数は存在し、$\gcd(a,b)\geq1$ である。定義から $\gcd(a,b)=\gcd(b,a)=\gcd(|a|,|b|)$、$\gcd(a,0)=|a|$ である。
$a,b$ を少なくとも一方は $0$ でない整数とし、$d=\gcd(a,b)$ とする。
- 整数 $x,y$ が存在して $ax+by=d$ となる。
- $a,b$ の整数係数の線形結合の全体は $d$ の倍数の全体に一致する。すなわち
$$ \{ax+by\mid x,y\in\mathbb{Z}\}=d\mathbb{Z} $$
である。特に $d$ は $ax+by$ の形の正の整数のうち最小のものである。 - $a,b$ の公約数は、ちょうど $d$ の約数である。
1 を満たす整数の組 $(x,y)$ を $a,b$ の Bézout係数 という。Bézout係数は一意でない（prop-bezout-identity-all-coefficients）。$a=b=0$ のときも $\gcd(0,0)=0=0\cdot x+0\cdot y$ なので 1、2 の集合の等式、3 は形式的に成り立つ（2 の最小性の主張は意味をもたない）が、係数に関する主張が退化するので定理からは除いた。3 は、最大公約数が「大きさについて最大」であるだけでなく「割り切る関係について最大」でもあることを述べている。一般の環ではこちらの性質を最大公約数の定義に採る（thm-bezout-identity-pid の前の段落）。
証明
最小の正の線形結合を使う証明
正の整数からなる集合
$$
S:=\{ax+by\mid x,y\in\mathbb{Z},\ ax+by>0\}
$$
を考える。$x=a$、$y=b$ とすると $a^2+b^2>0$ なので $S$ は空でない。正の整数からなる空でない集合は最小元をもつ（自然数の整列性。数学的帰納法と同値である）ので、$S$ の最小元 $e$ をとり、$e=ax_0+by_0$ と書く。
$e$ が $a$ を割り切ることを示す。除法の原理により $a=qe+r$、$0\leq r< e$ となる整数 $q,r$ がある。
$$
r=a-qe=a-q(ax_0+by_0)=a(1-qx_0)+b(-qy_0)
$$
も $a,b$ の線形結合であるから、$r>0$ なら $r\in S$ かつ $r< e$ となって $e$ の最小性に反する。よって $r=0$、すなわち $e\mid a$ である。同じ議論で $e\mid b$ である。したがって $e$ は $a,b$ の公約数である。
一方、$a,b$ の任意の公約数 $c$ は $ax_0+by_0=e$ を割り切る。$e>0$ なので $c\leq|c|\leq e$ である。よって $e$ は公約数のうち最大のもの、すなわち $e=d$ であり、1 が示された。同時に、任意の公約数 $c$ が $d=e$ を割り切ることも示された。
2 を示す。$d\mid a$、$d\mid b$ なので、任意の $x,y$ について $d\mid ax+by$ である。逆に $k\in\mathbb{Z}$ に対し $kd=a(kx_0)+b(ky_0)$ は線形結合である。よって 2 つの集合は一致する。$d\mathbb{Z}$ の正の元のうち最小のものは $d$ である。
3 を示す。公約数が $d$ を割り切ることは上で示した。逆に $d$ の約数は、$d\mid a$ と $d\mid b$ により $a$ と $b$ を割り切る。
この証明は $x_0,y_0$ の求め方を与えない。係数を具体的に計算するには、次の互除法を用いる。
互除法による構成
Euclidの互除法は、割り算を繰り返して最大公約数を求める手続きである。各段の余りを $a,b$ の線形結合として記録し続けると、最後に Bézout係数が得られる。この手続きを 拡張Euclid互除法（拡張Euclid互除法、extended Euclidean algorithm）という。
$a$ を整数、$b$ を正の整数とする。
$$
r_0:=a,\quad r_1:=b,\qquad (s_0,t_0):=(1,0),\quad (s_1,t_1):=(0,1)
$$
とおき、$r_i\neq0$ である限り、$r_{i-1}$ を $r_i$ で割った商 $q_i$ と余り $r_{i+1}$（$0\leq r_{i+1}< r_i$）をとって
$$
r_{i+1}=r_{i-1}-q_ir_i,\qquad s_{i+1}=s_{i-1}-q_is_i,\qquad t_{i+1}=t_{i-1}-q_it_i
$$
と定める。このとき次が成り立つ。
- ある $n\geq1$ で $r_{n+1}=0$ となり、手続きは止まる。
- 各 $i$ について $r_i=as_i+bt_i$ である。
- 最後の $0$ でない余り $r_n$ は $\gcd(a,b)$ に等しい。したがって $as_n+bt_n=\gcd(a,b)$ である。
- $r_1>r_2>r_3>\cdots\geq0$ は $0$ 以上の整数の真に減少する列なので、無限には続かない。よってある $n\geq1$ で $r_n\neq0$、$r_{n+1}=0$ となる。
- $i$ に関する帰納法で示す。$i=0,1$ では $r_0=a\cdot1+b\cdot0$、$r_1=a\cdot0+b\cdot1$ である。$r_{i-1}=as_{i-1}+bt_{i-1}$ と $r_i=as_i+bt_i$ が成り立つとすると、
$$ r_{i+1}=r_{i-1}-q_ir_i=a(s_{i-1}-q_is_i)+b(t_{i-1}-q_it_i)=as_{i+1}+bt_{i+1} $$
である。 - $1\leq i\leq n$ について、$r_{i-1},r_i$ の公約数全体と $r_i,r_{i+1}$ の公約数全体は一致する。実際、$c$ が $r_{i-1}$ と $r_i$ を割り切れば $r_{i+1}=r_{i-1}-q_ir_i$ も割り切り、$c$ が $r_i$ と $r_{i+1}$ を割り切れば $r_{i-1}=q_ir_i+r_{i+1}$ も割り切る。これを $i=1,\dots,n$ について繋げると、$a=r_0$ と $b=r_1$ の公約数全体は、$r_n$ と $r_{n+1}=0$ の公約数全体、すなわち $r_n$ の約数全体に一致する。$r_n>0$ なので、そのうち最大のものは $r_n$ である。よって $\gcd(a,b)=r_n$ であり、2 と合わせて $as_n+bt_n=\gcd(a,b)$ を得る。
prop-bezout-identity-extended-euclid は $b>0$ を仮定しているが、一般の場合はこれに帰着する。$b<0$ なら $\gcd(a,b)=\gcd(a,-b)$ なので、$a$ と $-b$ に適用して得た係数 $(s,t)$ から $(s,-t)$ をとればよい。$b=0$、$a\neq0$ なら $\gcd(a,0)=|a|$ であり、$a\cdot(\pm1)+0\cdot0=|a|$ である。こうして thm-bezout-identity の 1 は、整列性を直接使わずに、割り算の繰り返しが止まることから再び示された。
$a=1071$、$b=462$ に prop-bezout-identity-extended-euclid を適用する。
$$
1071=2\cdot462+147,\qquad 462=3\cdot147+21,\qquad 147=7\cdot21+0
$$
なので $q_1=2$、$q_2=3$、$q_3=7$ であり、係数は次のように更新される。
| $i$ | $r_i$ | $q_i$ | $s_i$ | $t_i$ |
|---|---|---|---|---|
| $0$ | $1071$ | $1$ | $0$ | |
| $1$ | $462$ | $2$ | $0$ | $1$ |
| $2$ | $147$ | $3$ | $1$ | $-2$ |
| $3$ | $21$ | $7$ | $-3$ | $7$ |
| $4$ | $0$ | $22$ | $-51$ |
したがって $\gcd(1071,462)=21$ であり、$1071\cdot(-3)+462\cdot7=-3213+3234=21$ である。最後の行 $1071\cdot22+462\cdot(-51)=23562-23562=0$ は、係数を $(22,-51)$ の整数倍だけずらしても等式が保たれることを示している。ここで $22=462/21$、$51=1071/21$ であり、これは prop-bezout-identity-all-coefficients の $(b/d,-a/d)$ にあたる。
同じ結果は、割り算の式を下から逆に代入しても得られる。
$$
21=462-3\cdot147=462-3(1071-2\cdot462)=7\cdot462-3\cdot1071.
$$
帰結・補足
Bézout係数の全体と 1 次不定方程式
$a,b$ を $0$ でない整数、$d=\gcd(a,b)$、$c$ を整数とする。
- 方程式 $ax+by=c$ が整数解 $(x,y)$ をもつことと、$d\mid c$ は同値である。
- $(x_0,y_0)$ を $ax+by=c$ の 1 つの整数解とすると、整数解の全体は
$$ x=x_0+\frac{b}{d}\,t,\qquad y=y_0-\frac{a}{d}\,t\qquad(t\in\mathbb{Z}) $$
である。特に $c=d$ とすると、Bézout係数は無限個あり、1 組から上の式ですべて得られる。
- 解があれば、$d\mid a$ と $d\mid b$ から $d\mid ax+by=c$ である。逆に $c=kd$ なら、thm-bezout-identity の係数 $au+bv=d$ に $k$ を掛けて $a(ku)+b(kv)=c$ を得る。
- $a':=a/d$、$b':=b/d$ とおく。$au+bv=d$ を $d$ で割ると $a'u+b'v=1$ なので、$a'$ と $b'$ の公約数は $1$ を割り切り、$\gcd(a',b')=1$ である。$(x,y)$ を解とすると、$ax_0+by_0=c$ との差をとって $d$ で割り
$$ a'(x-x_0)=-b'(y-y_0) $$
を得る。$a'$ は右辺を割り切り、$a'$ と $b'$ は互いに素なので、$a'\mid y-y_0$ である（互いに素 の記事の命題「互いに素な因子の消去」）。$y-y_0=-a't$ と書くと $a'(x-x_0)=b'a't$ であり、$a'\neq0$ なので $x-x_0=b't$ である。逆に、この形の $(x,y)$ については $a\cdot\frac{b}{d}t-b\cdot\frac{a}{d}t=0$ なので $ax+by=ax_0+by_0=c$ となる。
たとえば $12x+18y=6$ の整数解は $(x,y)=(-1+3t,\ 1-2t)$（$t\in\mathbb{Z}$）であり、$12x+18y=5$ は $6\nmid5$ なので整数解をもたない。prop-bezout-identity-all-coefficients の 2 より、$x$ を $|b/d|$ を法として動かせるので、$0\leq x<|b/d|$ を満たす Bézout係数がちょうど 1 組ある。
合同式の逆元
合同式 $ax\equiv1\pmod n$（$n\geq2$）が解をもつことは、$ax+ny=1$ となる整数 $x,y$ があること、すなわち thm-bezout-identity の 2 により $\gcd(a,n)=1$ であることと同値である。このとき $x$ の剰余類が $\mathbb{Z}/n\mathbb{Z}$ における $a$ の剰余類の逆元であり、単元である（環 の記事の例「整数の剰余環 $\mathbb{Z}/n\mathbb{Z}$」）。
$a=35$、$n=16$ に互除法を適用すると
$$
35=2\cdot16+3,\qquad 16=5\cdot3+1,\qquad 3=3\cdot1+0
$$
であり、$\gcd(35,16)=1$ である。逆に代入すると
$$
1=16-5\cdot3=16-5(35-2\cdot16)=11\cdot16-5\cdot35
$$
なので $35\cdot(-5)\equiv1\pmod{16}$ であり、$-5\equiv11\pmod{16}$ が $35$ の逆元である。実際 $35\cdot11=385=24\cdot16+1$ である。
3 個以上の整数
$a_1,\dots,a_n$（すべてが $0$ ではない）の公約数のうち最大のものを $\gcd(a_1,\dots,a_n)$ と書く。
$a_1,\dots,a_n$ をすべてが $0$ ではない整数とし、$d=\gcd(a_1,\dots,a_n)$ とする。このとき
$$
\{a_1x_1+\cdots+a_nx_n\mid x_1,\dots,x_n\in\mathbb{Z}\}=d\mathbb{Z}
$$
であり、特に $a_1x_1+\cdots+a_nx_n=d$ となる整数 $x_1,\dots,x_n$ が存在する。$a_1,\dots,a_n$ の公約数は、ちょうど $d$ の約数である。
左辺は $a_1,\dots,a_n$ が生成する $\mathbb{Z}$ のイデアル $(a_1,\dots,a_n)$ である（イデアル の記事の命題「生成されるイデアルの元」の 3）。$\mathbb{Z}$ のイデアルは $e\mathbb{Z}$（$e\geq0$）の形であり（イデアル の記事の例「整数環のイデアル」）、$a_i$ のどれかは $0$ でないので $e\geq1$ である。各 $a_i$ は $e\mathbb{Z}$ に属するので $e$ は公約数である。また $e\in(a_1,\dots,a_n)$ なので $e=\sum a_ix_i$ と書け、任意の公約数 $c$ は $e$ を割り切る。よって $c\leq|c|\leq e$ であり、$e$ は最大の公約数 $d$ に等しい。公約数がちょうど $d$ の約数であることも同時に示された。
たとえば $\gcd(6,10,15)=1$ であり、$6\cdot1+10\cdot1+15\cdot(-1)=1$ である。しかし $6,10,15$ のどの 2 つも互いに素でない（$\gcd(6,10)=2$、$\gcd(6,15)=3$、$\gcd(10,15)=5$）。全体の最大公約数が $1$ であることと、どの 2 つも互いに素であることの違いは 互いに素 の記事で扱う。
単項イデアル整域への一般化
整域 $A$ の元 $a,b$ に対し、$d\in A$ が $a,b$ の 最大公約元 であるとは、$d$ が $a$ と $b$ をともに割り切り、$a$ と $b$ をともに割り切る任意の元が $d$ を割り切ることをいう。一般の環には大小がないので、thm-bezout-identity の 3 の性質を定義に採る。最大公約元が存在すれば、単元倍の違いを除いて一意である。
$A$ を単項イデアル整域とし、$a,b\in A$ とする。$(a,b)=(d)$ を満たす $d\in A$ が存在し、この $d$ は $a,b$ の最大公約元である。さらに、$a,b$ の任意の最大公約元 $d'$ は、ある $x,y\in A$ により $d'=ax+by$ と書ける。
$A$ は単項イデアル整域なので、イデアル $(a,b)=\{ax+by\mid x,y\in A\}$ はある $d$ により $(d)$ と書ける。$a,b\in(d)$ なので $d$ は $a,b$ を割り切る。$d\in(a,b)$ なので $d=ax_0+by_0$ と書け、$a,b$ をともに割り切る元 $c$ は $ax_0+by_0=d$ を割り切る。よって $d$ は最大公約元である。
$d'$ を別の最大公約元とすると、$d\mid d'$ かつ $d'\mid d$ なので、$d'=de$、$d=d'f$ となる $e,f\in A$ がある。$d=0$ なら $d'=0=a\cdot0+b\cdot0$ である。$d\neq0$ なら $d=def$ であり、$A$ は整域なので $ef=1$ である。いずれの場合も $d'=de=a(x_0e)+b(y_0e)$ と書ける。
$\mathbb{Z}$ と体 $K$ 上の 1 変数多項式環 $K[x]$ は単項イデアル整域である（単項イデアル整域 の記事の例「整数環と体上の多項式環」）。$K[x]$ の場合、$f,g$（少なくとも一方は $0$ でない）の最大公約元のうちモニック（モニック多項式）なものが最大公約多項式 $\gcd(f,g)$ であり、$\gcd(f,g)=uf+vg$ となる多項式 $u,v$ があることは 多項式環 の記事の命題「最大公約多項式の特徴づけ」にある。たとえば有理数体 $\mathbb{Q}$ 上で $f=x^2-1$、$g=x^2-3x+2$ とすると、
$$
f=1\cdot g+(3x-3),\qquad g=\Bigl(\frac13x-\frac23\Bigr)(3x-3)
$$
なので $\gcd(f,g)=x-1$ であり、$x-1=\frac13f-\frac13g$ である。
Euclid整域では、整数の場合と同じく割り算の繰り返しで最大公約元と係数が計算できる（Euclid整域 の記事の命題「互除法による最大公約元の計算」）。すべての 2 元について Bézout の等式が成り立つ整域、すなわち有限生成イデアルがすべて単項である整域を Bezout整域といい（Bezout環）、単項イデアル整域はそのうち Noether環 であるものにちょうど一致する（Bezout環 の記事の系「PIDはネーター的なBezout整域とちょうど一致する」）。
反例：等式が成り立たない環
整数係数の多項式環 $\mathbb{Z}[x]$ で $a=2$、$b=x$ を考える。
$2$ と $x$ の公約元は $\pm1$ だけである。実際、$c\mid2$ なら次数を比べて $c$ は定数であり（$\mathbb{Z}$ は整域なので積の次数は次数の和になる。多項式環 の記事の命題「次数の公式と整域性」）、$c\in\{\pm1,\pm2\}$ である。$c=\pm2$ は $x$ を割り切らない（$x=\pm2h$ なら $x$ の係数 $1$ が偶数になる）。$\pm1$ はすべての元を割り切るので、$1$ は $2$ と $x$ の最大公約元である。
しかし $2u+xv=1$ となる $u,v\in\mathbb{Z}[x]$ は存在しない。左辺の定数項は $2u(0)$ で偶数だからである。この例で $\mathbb{Z}[x]$ は、最大公約元がつねに存在する環（一意分解整域。多項式環 の記事の定理「Gauss の定理（一意分解整域上の多項式環）」）であることを満たし、単項イデアル整域であることを満たさない。破れるのは「最大公約元が存在すれば、それは $a,b$ の線形結合で書ける」という含意である。イデアルの言葉では、$(2,x)$ が単項イデアルでないことにあたる（イデアル の記事の命題「整数係数多項式環の単項でないイデアル」）。
同様に、体 $k$ 上の 2 変数多項式環 $k[x,y]$ で $x$ と $y$ の最大公約元は $1$ であるが、$xu+yv$ の定数項はつねに $0$ なので $xu+yv=1$ とはならない。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
