ベズーの等式のソースを表示

'''ベズーの等式'''（ベズーのとうしき、{{Lang-en-short|Bézout's identity}}）は初等[[整数論]]における定理である。'''ベズーの補題'''（ベズーのほだい、{{Lang-en-short|Bézout's lemma}}）とも呼ばれる。{{math theorem|ベズーの等式|{{Mvar|a}} と {{Mvar|b}} を {{Math|0}} でない[[整数]]とし、{{Mvar|d}} をそれらの[[最大公約数]]とする。このとき整数 {{Mvar|x}} と {{Mvar|y}} が存在して
: {{math|''ax'' + ''by'' {{=}} ''d''}}
となる。さらに、
# {{Mvar|d}} は {{nowrap|{{Mvar|ax}} + {{Mvar|by}}}} と書ける最小の正の整数であり、
# {{nowrap|{{Mvar|ax}} + {{Mvar|by}} }}の形のすべての整数は {{Mvar|d}} の倍数である。}}
{{Mvar|x}} と {{Mvar|y}} は ({{Mvar|a}}, {{Mvar|b}}) の'''ベズー係数''' (Bézout coefficients) と呼ばれる。それらは一意的ではない。ベズー係数の組は[[ユークリッドの互除法#拡張された互除法|拡張ユークリッドの互除法]]によって計算できる。{{Mvar|a}} と {{Mvar|b}} がどちらも {{Math|0}} でなければ、拡張ユークリッドの互除法から <math>|x|\le\left |\tfrac{b}{d}\right |</math> かつ <math>|y|\le\left |\tfrac{a}{d}\right |</math> であるような 2 つの組の一方が出る。

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

== 解の構造 ==

（例えば[[ユークリッドの互除法#拡張された互除法|拡張されたユークリッドの互除法]]を使って）ベズー係数の一組 ({{Mvar|x}}, {{Mvar|y}}) が計算されたとき、すべての組は
:<math>\left(x+k\frac{b}{\gcd(a,b)},\ y-k\frac{a}{\gcd(a,b)}\right)</math>
の形で表せる、ただし {{math|{{Mvar|k}}}} は任意の整数であり分数は整数になる。

ベズー係数のこれらの組の中で、ちょうど2つが
:<math> |x| \leqq \left |\frac{b}{\gcd(a,b)}\right |\quad \text{and}\quad |y| \leqq \left |\frac{a}{\gcd(a,b)}\right |.</math>

を満たす。また、{{Mvar|a}} と {{Mvar|b}} の一方が他方の約数であるときのみ等号が成立しうる。

これは[[除法の原理]]による。すなわち、2つの整数 {{Mvar|c}} と {{Mvar|d}} が与えられると、{{Mvar|d}} が {{Mvar|c}} を割らなければ、ちょうど1つの組 {{math|({{Mvar|q}},{{Mvar|r}}&thinsp;)}} が存在して、{{math|1={{Mvar|c}} = {{Mvar|dq}} + {{Mvar|r}}}} かつ {{math|1=0 < {{Mvar|r}} < {{!}}{{Mvar|d}}&thinsp;{{!}}}} となり、別の1つの組が存在して、{{math|1={{Mvar|c}} = {{Mvar|dq}} + {{Mvar|r}}}} かつ {{math|1=0 < &minus;{{Mvar|r}} < {{!}}{{Mvar|d}}&thinsp;{{!}}}} となる。

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

=== 例 ===

{{Mvar|a}} = 12、{{Mvar|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}} でない整数 {{Mvar|b}} による割り算は {{math|{{!}}''b''{{!}}}} よりも真に小さい[[余り]]をもつことの結果である。以下の証明は任意の[[ユークリッド整域]]に対して適用することができる。

与えられた {{Math|0}} でない整数 {{Mvar|a}} と {{Mvar|b}} に対して、{{Mvar|x}} と {{Mvar|y}} を整数として {{math|{{Mvar|ax}} + {{Mvar|by}}}} がとりうる整数の集合 {{Mvar|S}} について、{{Mvar|S}} の任意の要素 {{math|{{Mvar|u}}, {{Mvar|v}}}} および整数 {{Mvar|k}} に対して {{math|''u'' + ''v'', ''ku''}} は {{Mvar|S}} に含まれる。実際、{{math|{{Mvar|u}}, {{Mvar|v}}}} が {{math|''u'' {{=}} ''ax''{{sub|1}} + ''by''{{sub|1}}, ''v'' {{=}} ''ax''{{sub|2}} + ''by''{{sub|2}}}} と書ければ、{{math|''u'' + ''v'' {{=}} ''a''(''x''{{sub|1}} + ''x''{{sub|2}}) + ''b''(''y''{{sub|1}} + ''y''{{sub|2}}) ∈ ''S'',&nbsp;&nbsp;  ''ku'' {{=}} ''a''(''kx''{{sub|1}}) + ''b''(''ky''{{sub|1}}) ∈ ''S''}} である。符号をかえれば {{math|''u'' - ''v'' ∈ ''S''}} も同様にいえることがわかる。

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

というのは、もし {{Mvar|h}} の倍数で表せない数 {{Mvar|m}} が存在すると仮定すると {{Mvar|m}} を {{Mvar|h}} で割った商を {{Mvar|q}}、{{Math|0}} でない余りを {{Mvar|r}} と置いて {{math|''m'' {{=}} ''qh'' + ''r''}} すなわち {{math|''r'' {{=}} ''m'' - ''qh''}} と書ける。
仮定より {{math|''m'' ∈ ''S''}} および {{math|''h'' ∈ ''S'',&nbsp;&nbsp;''qh'' ∈ ''S''}} から {{math|''r'' ∈ ''S''}}。{{Mvar|r}} は割り算の余りなので割る数 {{Mvar|h}} より小さく、これは {{Mvar|h}} が {{Mvar|S}} に含まれる最小の正整数であるという仮定に反する。すなわち {{Mvar|S}} の要素はすべて {{Mvar|h}} の倍数になっている。

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

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

①②より {{math|{{Mvar|h}} {{=}} {{Mvar|g}}}}、すなわち、{{math|{{Mvar|ax}} + {{Mvar|by}} {{=}} {{Mvar|g}}}}（{{Mvar|g}} は {{math|{{Mvar|a}}, {{Mvar|b}}}} の最大公約数）を満たす {{math|{{Mvar|x}}, {{Mvar|y}}}} が存在する。<ref>以上の証明は{{Harvtxt|石井|2013|pp=26-32}}によった。</ref>

== 一般化 ==
=== 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>

が成り立つ。また右辺の形の数式は以下の性質をもつ：
# {{Mvar|d}} はこの形の最小の正の整数である
# この形の数はすべて {{Mvar|d}} の倍数である
<!--# {{Mvar|d}} は {{Mvar|a}}<sub>1</sub>, ..., {{Mvar|a}}<sub>{{Mvar|n}}</sub> の[[最大公約数]]である、つまり {{Mvar|a}}<sub>1</sub>, ..., {{Mvar|a}}<sub>{{Mvar|n}}</sub> のすべての共通因子は {{Mvar|d}} を割り切る-->

=== 多項式に対して ===
{{main|{{仮リンク|多項式の最大公約数|en|Polynomial greatest common divisor#Bézout's identity and extended GCD algorithm}}}}
ベズーの等式は[[可換体|体]]上の一変数[[多項式]]に対して整数に対してとちょうど全く同じようにうまくいく。とくにベズー係数と最大公約数は[[ユークリッドの互除法#拡張された互除法|拡張されたユークリッドの互除法]]によって計算できる。

2つの多項式の共通[[関数の零点|根]]はそれらの最大公約数<!--最大公約因子あるいは最大公約多項式とでも言うべきか？-->の根であるから、ベズーの等式と[[代数学の基本定理]]は次の結果を意味する：
:体係数の一変数多項式 {{Mvar|f}} と {{Mvar|g}} に対して、多項式 {{Mvar|a}} と {{Mvar|b}} が存在して {{Mvar|af}} + {{Mvar|bg}} = 1 であることと、{{Mvar|f}} と {{Mvar|g}} が任意の[[代数的閉体]]（通例は[[複素数]]体）において共通根をもたないことが同値である。

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

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

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

== 歴史 ==

[[フランス人]][[数学者]] [[エティエンヌ・ベズー]]（Étienne Bézout 1730年–1783年）がこの等式を多項式に対して証明した<ref>{{Harvnb|Bézout|1779}}</ref>。しかしながら、整数に対するこのステートメントは別のフランス人数学者{{仮リンク|クロード・バシェ|en|Claude Gaspard Bachet de Méziriac}}（Claude Gaspard Bachet de Méziriac 1581年–1638年）の仕事において既に見つかったものである<ref>{{Harvnb|Tignol| 2001}}</ref><ref>{{Harvnb|Tignol|2005}}</ref>。これらのページにおいて[[:d:Q371882|バシェ]] は（方程式なしに）次を証明する<ref>{{Harvnb|Bachet|1624|pp=18–33}}</ref>。<blockquote>“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.”{{fr icon}}（互いに素な2つの数が与えられたとき、一方の倍数が他方の倍数より 1 大きいような最小の倍数を見つけよ。）</blockquote>この問題（すなわち {{math|''ax'' - ''by'' {{=}} 1}}）はベズーの方程式の特別なケースであり、バシェはそれを用いてページ199ffに現れる問題を解いた。次も参照<ref>{{Harvnb|Bullynck|2009|pp=48–72}}</ref>。

== 関連項目 ==
{{Div col}}
*{{仮リンク|AF+BG定理|en|AF+BG theorem}}{{efn|3元不定斉次多項式に対するベズーの等式の類似。}}
*[[算術の基本定理]]
*[[ディオファントス方程式]]
*[[ユークリッドの互除法]]
*[[ユークリッドの補題]]
{{Div col end}}

== 脚注 ==
=== 注釈 ===
{{Notelist}}
=== 出典 ===
{{Reflist|2}}

== 参考文献 ==
*{{Cite book|和書
|author=石井俊全
|date=2013-08-25
|title=ガロア理論の頂を踏む
|series=BERET SCIENCE
|publisher=ベレ出版
|isbn=978-4-86064-363-8
|ref={{Harvid|石井|2013}}
}}
*{{citation|author=Claude Gaspard Bachet (sieur de Méziriac)|title=Problèmes plaisants & délectables qui se font par les nombres|edition=2nd|location=[[リヨン|Lyons, France]]|publisher=Pierre Rigaud & Associates|year=1624|url=http://www.bsb-muenchen-digital.de/~web/web1008/bsb10081407/images/index.html?digID=bsb10081407&pimage=38&v=100&nav=0&l=de|language=fr|ref={{Harvid|Bachet|1624}}}}
*{{citation |last=Bézout|first=E.|url=https://books.google.fr/books?id=FoxbAAAAQAAJ&hl=en&pg=PP5 |title=Théorie générale des équations algébriques |place=Paris, France |publisher=Ph.-D. Pierres |year=1779|language=fr}}
*{{citation|date=February 2009|first=Maarten |last=Bullynck|title=Modular arithmetic before C.F. Gauss: Systematizations and discussions on remainder problems in 18th-century Germany|doi=10.1016/j.hm.2008.08.009|journal=Historia Mathematica|volume=36|issue=1|pages=48–72|url=http://hal.inria.fr/docs/00/66/32/92/PDF/Gauss_Modular_Oct2008.pdf|format=pdf|language=en}}
*{{citation | last=Tignol | first=Jean-Pierre | title=Galois' Theory of Algebraic Equations | publisher=World Scientific| location=Singapore | year=2001 | isbn=981-02-4541-6|language=en}}
**{{Cite book|和書
|first=Jean‐Pierre
|last=Tignol
|others=新妻弘 訳
|date=2005-03
|title=代数方程式のガロアの理論
|publisher=共立出版
|isbn=978-4-320-01770-2
|ref={{Harvid|Tignol|2005}}
}}

== 外部リンク ==
*{{高校数学の美しい物語|title=一次不定方程式ax+by=cの整数解|urlname=axbyc}}
*{{高校数学の美しい物語|title=ユークリッドの互除法の証明と不定方程式|urlname=euclid}}
*[http://wims.unice.fr/wims/wims.cgi?module=tool/arithmetic/bezout.en Online calculator]
*{{mathworld|urlname=BezoutsIdentity|title=Bézout's Identity}}

{{Normdaten}}
{{DEFAULTSORT:へすうのとうしき}}
[[Category:人名を冠した数式]]
[[Category:証明を含む記事]]
[[Category:ディオファントス方程式]]
[[Category:補題]]
[[Category:数学に関する記事]]