導入
この記事では、算術におけるベズー恒等式とベズーの定理について説明します。代数幾何学におけるベズーの定理については、ベズーの定理を参照してください。
数学では、バシェ・ベズーの定理またはベズーの恒等式は 初等算術の結果であり、線形ディオファントス方程式の解の存在を証明します。
未知数 x と y の相対整数、a、b は相対整数係数、PGCD(a,b) は a と b の最大公約数です。
ベズーの定理によれば、次の方程式は
この定理の現在知られている最初の実証は、Claude-Gaspard Bachet de Méziriac によるものです。この結果は、1624 年に出版された彼の著書『数字によって行われる問題』の第 2版に掲載されています。しかし、数学者のエティエンヌ・ベズーは、この結果を、特により困難な実証である多項式に一般化しました。数学史上非常に頻繁に起きたこのような事故の 1 つにより、ベズーという名前はバシェの結果に誤って帰属されることになりました。
相対整数の集合におけるベズー恒等式
バシェのメジリアックの定理
定理—すべてがゼロではない 2 つの相対整数aとbが与えられ、 d がaとbの GCD である場合、次のような 2 つの相対整数xとyが存在します。
特に、2 つの相対整数aとb は、次のような 2 つの相対整数xとyが存在する場合にのみ互いに素です。
拡張Euclidアルゴリズムは、方程式 ax + by = gcd(a,b) に対する一対の整数の解を提供することにより、方程式の解の存在をすでに証明しています。しかし、メインリングで使用されるものに近い、その後のデモンストレーションも興味深いものです。
たとえば、 a がゼロではないと仮定できます。
- もし$$ {A = \{xa+yb; (x;y) \in \Z^2\}} $$、 Aの厳密に正の最小の要素がaとbの最大公約数であることを示します。
- 確かに$$ {A \cap \N^*} $$は空ではない( aの絶対値を含む)ため、より小さい要素d 0 = x 0 a + y 0 bが含まれます。 a をd 0で除算すると、余りrが得られます。これは、次のように記述されるため、A の自然数要素になります。$$ {r = a-qd_0 = a-qx_0a-qy_0b = (1-qx_0) \cdot a + (-qy_0) \cdot b} $$。これはd 0より小さい整数であるため、次の値に属することはできません。$$ {A \cap \N^*} $$なので、r はゼロになります。これは、 d 0 がa を割ることを意味します。同様に、 d 0 はb を除算します。したがって、 d 0 はa と b に共通の約数です。
- 最後に、 aとbに共通する別の約数があるとします。 d がaとb を除算すると、 d はx 0 a + y 0 b を除算するため、 d はd 0 を除算します。実際、 d 0 はaとbの最大公約数であり、 p g c d ( a , b ) = a x 0 + b y 0となる 2 つの整数x 0とy 0が存在します。
注: a と b がゼロの場合、それらは任意の整数で割り切れるため、gcd は存在しません。
一般に、この定理には逆がありません。 d = a x + b yのような 2 つの整数が存在しても、 d がaとbの GCD であることは保証されません。これを確信するには、たとえば、2x + 3y = 5 となる 2 つの整数 x と y が存在する一方、5 は 2 と 3 の GCD ではないことに注目するだけで十分です。 d = a x + b yである場合、 d はGCD の倍数であるとしか言えません。実際、 aとb はそれらの GCD の倍数であり、 a x + b y はGCD の倍数であるため、 d = a x + b yの場合、 d はaとbの GCD の倍数になります。
ただし、方程式 ax+by = 1 の場合は逆になります。a x + b y = 1となる 2 つの整数xとyが存在すると、1 が a と b の GCD の倍数になることが保証されます。これは、 aとbの GCD が 1 の場合、つまりaとbが互いに素である場合にのみ実行できます。
バシェ-ベズーの定理は、ax + by = PGCD(a,b) のような整数のペアの存在を保証します。拡張 Euclid アルゴリズムは解のペアの 1 つを提供しますが、一般に、他にも無数の解のペアが存在します。
たとえば、12 と 42 の最大公約数は 6 で、次のように書くことができます。
- $$ {(-3) \cdot 12 + 1 \cdot 42 = 6} $$
だけでなく、
- $$ {4 \cdot 12 + (-1) \cdot 42 = 6} $$。
GCD dがゼロ以外の場合、解のペア( x 0 , y 0 )から、次の条件も満たしていることを証明するのは簡単です。
- $$ {a \cdot \left(x_0 – k \cdot {b \over d}\right) + b \cdot \left(y_0 + k \cdot {a \over d}\right) = d} $$
ここで、 k は次のように変化します
アプリケーション
バシェ・ベズーの定理は、数論の多くの領域に介入します。
- これにより、ガウスの定理を証明することができます。
- これは逆モジュロb の検索に関与するため、暗号化におけるメッセージの解読に役立ちます。
- これは、ディオファントス方程式 ax+by = c を解く際に関与します。
一般化
定理— a 1 , …, a nに対する相対的な整数がすべてゼロではない場合、 dがa 1 , …, a nの GCD である場合、 x 1 , …, x nに対する相対的な整数が存在します。として
特に、次のような相対整数x 1 , …, x n が存在する場合に限り、 a 1 , …, a n は(全体として) 互いに素です。
言い換えれば、 a i がすべてゼロではない場合、 a 1 、…、a n の GCD は、 a 1 、…、 a nの整数係数を伴う線形結合として記述できる最小の厳密に正の整数です。 .、 n 。