ベズーの等式

提供: miniwiki
2018/8/19/ (日) 16:57時点におけるAdmin (トーク | 投稿記録)による版 (1版 をインポートしました)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先:案内、検索

ベズーの等式 (Bézout's identity) （ベズーの補題 (Bézout's lemma) とも呼ばれる）は初等整数論における定理である。a と b を 0 でない整数とし、d をそれらの最大公約数とする。このとき整数 x と y が存在して

[math] ax+by=d [/math]

となる。さらに、i) d は ax + by と書ける最小の正の整数であり、ii) ax + by の形のすべての整数は d の倍数である。x と y は (a, b) のベズー係数 (Bézout coefficients) と呼ばれる。それらは一意的ではない。ベズー係数の組は拡張ユークリッドの互除法によって計算できる。a と b がどちらも 0 でなければ、拡張ユークリッドの互除法から [math]|x|\lt \left |\tfrac{b}{d}\right |[/math] かつ [math]|y|\lt \left |\tfrac{a}{d}\right |[/math] であるような 2 つの組の一方が出る。

ベズーの補題は任意の主イデアル整域において正しいが、正しくないような整域が存在する。

解の構造

（例えば拡張ユークリッドアルゴリズム（English版）を使って）ベズー係数の一組 (x, y) が計算されたとき、すべての組は

[math]\left(x+k\frac{b}{\gcd(a,b)},\ y-k\frac{a}{\gcd(a,b)}\right)[/math]

の形で表せる、ただし k は任意の整数であり分数は整数になる。

ベズー係数のこれらの組の中で、ちょうど2つが

[math] |x| \lt \left |\frac{b}{\gcd(a,b)}\right |\quad \text{and}\quad |y| \lt \left |\frac{a}{\gcd(a,b)}\right |.[/math]

を満たす。これは除法の原理による。すなわち、2つの整数 c と d が与えられると、d が c を割らなければ、ちょうど1つの組 (q,r ) が存在して、c = dq + r かつ 0 < r < |d | となり、別の1つの組が存在して、c = dq + r かつ 0 < −r < |d | となる。

拡張ユークリッドアルゴリズムはつねにこれらの2つの最小の組の1つをもたらす。

例

a = 12、b = 42 とすると、gcd (12, 42) = 6 である。このとき次のベズーの等式が成り立つ。赤で書かれたベズー係数は最小の組であり青は他のものである。

[math] \begin{align} \vdots \\ 12 &\times (\color{blue}{-10}) & + \;\; 42 &\times \color{blue}{3} &= 6 \\ 12 &\times (\color{red}{-3}) & + \;\;42 &\times \color{red}{1} &= 6 \\ 12 &\times \color{red}{4} & + \;\;42 &\times(\color{red}{-1}) &= 6 \\ 12 &\times \color{blue}{11} & + \;\;42 &\times (\color{blue}{-3}) &= 6 \\ 12 &\times \color{blue}{18} & + \;\;42 &\times (\color{blue}{-5}) &= 6 \\ \vdots \end{align} [/math]

証明

ベズーの補題は性質を定義する除法の原理、すなわち [math]0[/math] でない整数 [math]b[/math] による割り算は [math]\left | b \right |[/math] よりも真に小さい余りをもつことの結果である。以下の証明は任意のユークリッド整域に対して適用することができる。

与えられた [math]0[/math] でない整数 [math]a[/math] と [math]b[/math] に対して、[math]x[/math] と [math]y[/math] を整数として [math]ax + by[/math] のとりうる整数の集合 [math]\mathit{S}[/math] について、[math]\mathit{S}[/math] の任意の要素 [math]u, v[/math] および整数 [math]k[/math] に対して [math]u + v, ku[/math] は [math]\mathit{S}[/math] に含まれる。実際、[math]u, v[/math] が [math]u = ax_1 + by_1, v = ax_2 + by_2[/math] と書ければ、[math]u + v = a(x_1 + x_2) + b(x_2 + y_2) \in \mathit{S}, ku = a(kx_1) + b(ky_1) \in \mathit{S} [/math] である。符号をかえれば [math]u - v \in \mathit{S}[/math] も同様にいえることがわかる。

今 [math]\mathit{S}[/math] に含まれる正の整数のうち最小の数を [math]h[/math] とする。すると、[math]\mathit{S}[/math] の要素はすべて [math]h[/math] の倍数になっている。

というのは、もし [math]h[/math] の倍数で表せない数 [math]m[/math] が存在すると仮定すると [math]m[/math] を [math]h[/math] で割った商を [math]q[/math]、[math]0[/math] でない余りを [math]r[/math] と置いて [math]m = qh + r[/math] すなわち [math]r = m - qh[/math] と書ける。 仮定より [math]m \in \mathit{S}[/math] および [math]h \in \mathit{S}, qh \in \mathit{S}[/math] から [math]r \in \mathit{S}[/math]。[math]r[/math] は割り算の余りなので割る数 [math]h[/math] より小さく、 これは [math]h[/math] が [math]\mathit{S}[/math] の最小の数であるという仮定に反する。すなわち [math]\mathit{S}[/math] の要素はすべて [math]h[/math] の倍数になっている。

[math]ax + by[/math] の式で [math]x = 1, y = 0[/math] を代入すれば [math]a[/math] となるから、[math]a \in \mathit{S}[/math]、同様に [math]b \in \mathit{S}[/math]。 ということは、[math]a, b[/math] は [math]h[/math] の倍数であり、[math]h[/math] は [math]a, b[/math] の公約数である。したがって [math]a, b[/math] の最大公約数 [math]g[/math] 以下であるから [math]h \leqq g[/math]。……①

また [math]a, b[/math] は [math]g[/math] の倍数だから、[math]a = a'g, b = b'g[/math] と置いて、[math] ax + by = (a'x + b'y)g[/math] となり、[math]\mathit{S}[/math] の要素は [math]g[/math] の倍数である。 特に [math]h \in \mathit{S}[/math] も [math]g[/math] の倍数だから、[math]h \geqq g[/math]。……②

①②より [math]h = g[/math]、すなわち、[math]ax + by = g[/math]（[math]g[/math] は [math]a, b[/math] の最大公約数）を満たす [math]x, y[/math] が存在する。

一般化

3つ以上の整数に対して

ベズーの等式は2つよりも多い整数に対して拡張することができる：

[math]\gcd(a_1, a_2, \ldots, a_n) = d[/math]

とおくと、整数 [math]x_1, x_2, \ldots, x_n[/math] が存在して、

[math]d = a_1 x_1 + a_2 x_2 + \cdots + a_n x_n[/math]

が成り立つ。また右辺の形の数式は以下の性質をもつ：

  1. d はこの形の最小の正の整数である
  2. この形の数はすべて d の倍数である

多項式に対して

"「多項式の最大公約数（English版）」"

ベズーの等式は体上の一変数多項式に対して整数に対してとちょうど全く同じようにうまくいく。とくにベズー係数と最大公約数は拡張ユークリッド互除法（English版） によって計算できる。

2つの多項式の共通根はそれらの最大公約数の根であるから、ベズーの等式と代数学の基本定理は次の結果を意味する：

体係数の一変数多項式 f と g に対して、多項式 a と b が存在して af + bg = 1 であることと、f と g が任意の代数的閉体（通例は複素数体）において共通根をもたないことが同値である。

この結果の任意個の多項式と不定元に対する一般化はヒルベルトの零点定理である。

主イデアル整域に対して

導入部で言及したように、ベズーの等式は整数環においてだけでなく任意の他の単項イデアル整域 (PID) においてもうまくいく。つまり、R が PID で a と b が R の元で d が a と b の最大公約元であれば、R の元 x と y が存在して、ax + by = d である。理由：イデアル Ra+Rb が単項であり確かに Rd に等しい。

ベズーの等式が成り立つような整域はベズー整域と呼ばれる。

歴史

フランス人数学者 Étienne Bézout (1730–1783) がこの等式を多項式に対して証明した[1]。しかしながら、整数に対するこのステートメントは別のフランス人数学者 Claude Gaspard Bachet de Méziriac (1581–1638) の仕事において既に見つかる[2][3][4]。

関連項目

脚注

  1. ↑ Bézout E. (1779). Théorie générale des équations algébriques. Ph.-D. Pierres. 
  2. ↑ Tignol, Jean-Pierre (2001). Galois' Theory of Algebraic Equations. Singapore: World Scientific. ISBN 981-02-4541-6. 
  3. ↑ Claude Gaspard Bachet (sieur de Méziriac) (1624). Problèmes plaisants & délectables qui se font par les nombres, 2nd, Lyons, France: Pierre Rigaud & Associates, 18–33.  これらのページにおいて Bachet は（方程式なしに）次を証明する。 “Proposition XVIII. Deux nombres premiers entre eux estant donnez, treuver le moindre multiple de chascun d’iceux, surpassant de l’unité un multiple de l’autre.” （互いに素な2つの数が与えられたとき、一方の倍数が他方の倍数より 1 大きいような最小の倍数を見つけよ。）この問題（すなわち ax - by = 1）はベズーの方程式の特別なケースでありページ 199ff. に現れる問題を解くために Bachet によって使われた。
  4. ↑ 次も参照： Maarten Bullynck (February 2009). “Modular arithmetic before C.F. Gauss: Systematizations and discussions on remainder problems in 18th-century Germany”. Historia Mathematica 36 (1): 48–72. doi:10.1016/j.hm.2008.08.009. http://hal.inria.fr/docs/00/66/32/92/PDF/Gauss_Modular_Oct2008.pdf. 

外部リンク



「http:///http:///mymemo.xyz/mymemo.xyz/wiki/index.php?title=ベズーの等式&oldid=106283」から取得