Bézouts Identität - Bézout's identity

In der elementaren Zahlentheorie ist Bézouts Identität (auch Bézouts Lemma genannt ), benannt nach Étienne Bézout , der folgende Satz :

Bézout Identität - Sei a und b sein ganzer Zahlen mit größter gemeinsamer Teiler d . Dann gibt es ganze Zahlen x und y , so daß ax + durch = d . Ganz allgemein sind die ganzen Zahlen der Form ax + by genau die Vielfachen von d .

Hier wird der größte gemeinsame Teiler von 0 und 0 als 0 angenommen. Die ganzen Zahlen x und y heißen Bézout-Koeffizienten für ( a , b ); sie sind nicht einzigartig. Ein Paar von Bézout-Koeffizienten kann durch den erweiterten euklidischen Algorithmus berechnet werden , und dieses Paar ist eines der beiden Paare mit und . Gleichheit tritt nur ein, wenn eines von a und b ein Vielfaches des anderen ist. $|x|\leq |b/d|$ $|y|\leq |a/d|$

Als Beispiel ist der größte gemeinsame Teiler von 15 und 69 3, und 3 kann als Kombination von 15 und 69 geschrieben werden als 3 = 15 × (−9) + 69 × 2, mit Bézout-Koeffizienten −9 und 2.

Viele andere Sätze der elementaren Zahlentheorie, wie das Lemma von Euklid oder der chinesische Restsatz , ergeben sich aus der Identität von Bézout.

Eine Bézout-Domäne ist eine integrale Domäne, in der die Identität von Bézout gilt. Insbesondere gilt die Identität von Bézout in idealen Hauptbereichen . Jeder Satz, der sich aus Bézouts Identität ergibt, ist somit in allen idealen Hauptbereichen wahr.

Struktur der Lösungen

Wenn $a$ und $b$ nicht beide Null sind und ein Paar von Bézout-Koeffizienten $(x, y)$ berechnet wurde (zB unter Verwendung des erweiterten euklidischen Algorithmus ), können alle Paare in der Form

\left(xk{\frac{b}{d}},\y+k{\frac{a}{d}}\right),

wobei $k$ eine beliebige ganze Zahl ist, $d$ der größte gemeinsame Teiler von $a$ und $b$ ist und die Brüche zu ganzen Zahlen vereinfacht werden.

Wenn $a$ und $b$ beide von Null verschieden sind, dann erfüllen genau zwei dieser Paare von Paaren von Bézout-Koeffizienten

|x|\leq \left|{\frac {b}{d}}\right|\quad {\text{and}}\quad |y|\leq \left|{\frac {a}{ d}}\rechts|,

und Gleichheit kann nur auftreten, wenn eines von $a$ und $b$ das andere teilt.

Dies beruht auf einer Eigenschaft der euklidischen Teilung : gegeben zwei von Null ganzen Zahlen $c$ und $d$ , wenn $d$ nicht teilt $c$ , gibt es genau ein Paar $(q, r)$ , so dass $c = dq + r$ und $0 < r <| d |$ , und ein weiteres mit $c = dq + r$ und $-| d | < r < 0$ .

Die beiden Paare von kleinen Bézout-Koeffizienten werden aus dem gegebenen $(x, y) erhalten,$ indem für $k$ in der obigen Formel eine der beiden ganzen Zahlen neben ausgewählt wird . ${\frac {x}{b/d}}$

Der erweiterte euklidische Algorithmus erzeugt immer eines dieser beiden Minimalpaare.

Beispiel

Sei $a = 12$ und $b = 42$ , dann $gcd (12, 42) = 6$ . Dann werden die folgenden Bézout-Identitäten verwendet, wobei die Bézout-Koeffizienten für die minimalen Paare rot und für die anderen blau geschrieben sind.

{\begin{aligned}\vdots \\12&\times ({\color {blau}{-10}})&+\;\;42&\times \color {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 ({\ Farbe {blau}{-3}})&=6\\12&\times \color {blau}{18}&+\;\;42&\times ({\color {blau}{-5}})&= 6\\\vdots \end{aligned}}

Wenn $(x, y) = (18, -5)$ das ursprüngliche Paar von Bézout-Koeffizienten ist, dann erhält man die minimalen Paare über $k$ $= 2$ bzw. $k$ $= 3$ ; das heißt $(18 - 2 7, -5 + 2 2) = (4, -1)$ und $(18 - 3 7, -5 + 3 \cdot 2) = (-3, 1)$ . ${\frac {18}{42/6}}\in [2,3]$

Nachweisen

Gegeben beliebige ganze Zahlen $a$ und $b$ , sei Die Menge $S$ ist nicht leer, da sie entweder $a$ oder $-$ $a enthält$ (mit $x$ $= \pm1$ und $y$ $= 0$ ). Da $S$ eine nicht leere Menge von positiven ganzen Zahlen ist, hat es ein minimales Element , durch das Wohlordnungsprinzip . Um zu beweisen , dass $d$ der größte gemeinsame Teiler von ist $ein$ und $b$ , muss nachgewiesen werden , dass $d$ ein gemeinsamer Teiler von ist $ein$ und $b$ , und dass es aus anderen gemeinsamen Teiler $c$ , hat man $c$ $\leq$ $d$ . $S=\{ax+by\mid x,y\in\mathbb{Z} {\text{ und }}ax+by>0\}.$ $d=as+bt$

Die euklidische Division von $a$ durch $d$ kann geschrieben werden

a=dq+r\quad {\text{mit}}\quad 0\leq r<d.

Der Rest $r$ ist in , weil $S\cup \{0\}$

{\begin{aligned}r&=a-qd\\&=aq(as+bt)\\&=a(1-qs)-bqt.\end{aligned}}

Somit ist $r$ von der Form , und daher . Jedoch ist $0 \leq$ $r$ $<$ $d$ , und $d$ ist die kleinste positive ganze Zahl in $S$ : der Rest $r$ kann daher nicht in $S sein$ , was $r$ notwendigerweise zu 0 macht. Dies impliziert, dass $d$ ein Teiler von $a ist$ . In ähnlicher Weise ist $d$ auch ein Teiler von $b$ und $d$ ist ein gemeinsamer Teiler von $a$ und $b$ . $axt+by$ $r\in S\cup \{0\}$

Nun sei $c$ ein beliebiger gemeinsamer Teiler von $a$ und $b$ ; das heißt, gibt es $u$ und $v$ , so daß $eine = Cu$ und $b = cv$ . So hat man

{\begin{aligned}d&=as+bt\\&=cus+cvt\\&=c(us+vt).\end{aligned}}

Das heißt, $c$ ist ein Teiler von $d$ und daher $c \leq d.$

Verallgemeinerungen

Für drei oder mehr ganze Zahlen

Die Identität von Bézout kann auf mehr als zwei ganze Zahlen erweitert werden: if

\gcd(a_{1},a_{2},\ldots,a_{n})=d

dann gibt es ganze Zahlen mit $x_{1},x_{2},\ldots,x_{n}$

d=a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}

hat folgende Eigenschaften:

d ist die kleinste positive ganze Zahl dieser Form
jede Zahl dieser Form ist ein Vielfaches von d

Für Polynome

Die Identität von Bézout funktioniert für univariate Polynome über einem Körper genauso wie für ganze Zahlen. Insbesondere können die Bézout-Koeffizienten und der größte gemeinsame Teiler mit dem erweiterten euklidischen Algorithmus berechnet werden .

Da die gemeinsamen Wurzeln zweier Polynome die Wurzeln ihres größten gemeinsamen Teilers sind, implizieren Bézouts Identität und der Fundamentalsatz der Algebra das folgende Ergebnis:

Für univariate Polynome f und g mit Koeffizienten in einem Feld existieren Polynome a und b , so daß af + bg = 1 , wenn und nur wenn f und g hat keine gemeinsame Wurzel in jedem algebraisch geschlossenen Feld (üblicherweise der Bereich der komplexen Zahlen ).

Die Verallgemeinerung dieses Ergebnisses auf eine beliebige Anzahl von Polynomen und Unbestimmten ist Hilberts Nullstellensatz .

Für Hauptidealbereiche

Wie in der Einleitung erwähnt, funktioniert Bézouts Identität nicht nur im Ring der ganzen Zahlen, sondern auch in jedem anderen idealen Hauptbereich (PID). Das heißt, wenn R eine PID ist und a und b Elemente von R sind und d ein größter gemeinsamer Teiler von a und b ist , dann gibt es Elemente x und y in R, so dass ax + by = d ist . Der Grund dafür ist, dass das ideale Ra + Rb hauptsächlich und gleich Rd ist .

Ein integraler Bereich, in dem die Identität von Bézout gilt, wird Bézout-Bereich genannt .

Geschichte

Der französische Mathematiker Étienne Bézout (1730–1783) bewies diese Identität für Polynome. Diese Aussage für ganze Zahlen findet sich jedoch bereits im Werk eines früheren französischen Mathematikers, Claude Gaspard Bachet de Méziriac (1581–1638).

Siehe auch

Satz von AF+BG , ein Analogon der Bézout-Identität für homogene Polynome in drei Unbestimmten
Grundsatz der Arithmetik
Euklids Lemma

Anmerkungen

Externe Links

Online-Rechner für die Identität von Bézout.
Weisstein, Eric W. "Bézouts Identität" . MathWorld .

Languages

In other projects