Bézout-Koeffizienten: ganze x, y mit a·x + b·y = ggT

Die Identität von Bézout besagt, dass es für beliebige ganze Zahlen a und b, die nicht beide null sind, ganze Zahlen x und y gibt, sodass a mal x plus b mal y dem größten gemeinsamen Teiler von a und b entspricht. Diese Koeffizienten sind das konstruktive Herz linearer diophantischer Gleichungen, modularer Inverser, wenn der ggT eins ist, und schulischer Beweise, dass zwei Zahlen teilerfremd sind.

Was die Identität von Bézout aussagt und warum Koeffizienten zählen

Jedes Paar ganzer Zahlen, das nicht beide null sind, besitzt einen wohldefinierten nichtnegativen größten gemeinsamen Teiler g. Die Identität von Bézout geht weiter: Sie garantiert ganze Zahlen x und y, für die a mal x plus b mal y gleich diesem g ist. Der Existenzbeweis ist konstruktiv und folgt dem euklidischen Restprozess.

Die gewöhnliche Division ersetzt wiederholt ein Paar durch den nächsten Rest, bis null erscheint; der letzte nichtnullte Rest ist der ggT. Verfolgt man, wie jeder Rest als ganzzahlige Linearkombination der ursprünglichen Eingaben geschrieben wird, erhält man die Koeffizienten am Ende. Schulbücher substituieren oft Quotienten aus der Divisionstabelle rückwärts; Produktionscode aktualisiert üblicherweise zwei Koeffizientenpaare in einer einzigen Schleife, ohne einen Restestapel zu speichern.

Beide Ansätze berechnen dasselbe mathematische Objekt. Die Koeffizienten sind nicht eindeutig: Wenn ein Paar funktioniert, funktioniert auch jedes um ganzzahlige Vielfache von b über g und a über g mit entgegengesetzten Vorzeichen verschobene Paar. Dieses Werkzeug liefert eine partikuläre Lösung des iterativen Algorithmus, stets mit nichtnegativem ggT, damit Skripte und Bewerter gegen eine feste Konvention vergleichen können, ohne die allgemeine Lösungsmenge neu abzuleiten.

So rufen Sie den Rechner auf und lesen die Antwort

Senden Sie die ganzen Zahlen a und b. Bei Erfolg enthält die Antwort die normalisierten a und b, den ggT, x, y, ein verschachteltes bezout-Objekt mit denselben Koeffizienten, einen numerischen check gleich a mal x plus b mal y, eine Gleichungzeichenkette wie zweihundertvierzig mal minus neun plus sechsundvierzig mal siebenundvierzig gleich zwei sowie ein identity-Feld mit der allgemeinen Relation.

Typische Prüfungen: für zweihundertvierzig und sechsundvierzig ist der ggT zwei mit einer gültigen Lösung x gleich minus neun und y gleich siebenundvierzig; für ein Primpaar mit ggT eins liefern die Koeffizienten die modulare Inverse von a modulo b nach Reduktion von x. Randfälle mit einer Null und einem nichtnullten Partner ergeben einen ggT gleich dem Absolutbetrag der nichtnullten Eingabe und ein triviales Koeffizientenmuster.

Wo Bézout-Koeffizienten in der Praxis vorkommen

Wettbewerbsprogrammierer lösen a mal x plus b mal y gleich c, indem sie zuerst den ggT und ein Basis-Bézout-Paar berechnen und anschließend die allgemeine Lösung skalieren und parametrisieren, wenn der ggT c teilt. Kryptografie-Studierende gewinnen modulare Inverse für RSA-Lehrbeispiele und affine Chiffren, wenn der ggT von a und m eins ist, indem sie den Koeffizienten von a nach Reduktion modulo m lesen. Lehrkräfte verlangen konstruktive Beweise, dass zwei ganze Zahlen teilerfremd sind, und brauchen ein deterministisches Orakel, das die Linearkombination zeigt, nicht nur ein Ja-Nein-Bit der Teilerfremdheit.

Daten- und Systemingenieure benötigen gelegentlich explizite Linearkombinationen beim Abstimmen periodischer Pläne oder Schritt-Arithmetik. Nutzen Sie das Browser-Werkzeug, um Hausaufgaben rasch zu prüfen, und automatisieren Sie denselben Vertrag, wenn Ihr Dienst massenhafte diophantische Checks braucht. Wenn Sie nur den reinen ggT ohne Koeffizienten brauchen, beantwortet diese Seite diesen Bedarf weiterhin und lehrt zugleich das stärkere konstruktive Bézout-Ergebnis, das Zahlentheorie-Curricula und Interviewfragen zum erweiterten euklidischen Denken trägt.