# Erweiterter euklidischer Algorithmus (ax + by = ggT(a, b))

Löst die Bézout-Identität a·x + b·y = ggT(a, b) für ganze Zahlen mit beliebigem Vorzeichen: vollständige Tabelle der Divisionsschritte (jede Zeile erfüllt r = a·s + b·t), ggT und kgV. Mit der optionalen rechten Seite c wird das Werkzeug ein Löser für lineare diophantische Gleichungen: Bei ggT | c Partikularlösung und allgemeine Lösung x = x₀ + (b/g)t, sonst klar gemeldete Unlösbarkeit über den ganzen Zahlen. Klassiker: 240 × (−9) + 46 × 47 = 2.

> Kanonische Seite: https://elysiatools.com/de/tools/extended-euclidean-algorithm

- **Kategorie:** Math & Numbers

- **Schlagwörter:** erweiterter euklid, bézout-identität, bézout-koeffizienten, ggT, diophantische gleichung, lineare diophantische, zahlentheorie

## Überblick

Dieser Online-Rechner führt den erweiterten euklidischen Algorithmus für zwei ganze Zahlen a und b durch, berechnet den größten gemeinsamen Teiler (ggT), das kleinste gemeinsame Vielfache (kgV) und bestimmt die ganzzahligen Bézout-Koeffizienten x und y für die Identität a·x + b·y = ggT(a, b). Mit dem optionalen Parameter c löst das Werkzeug zudem lineare diophantische Gleichungen der Form a·x + b·y = c und liefert sowohl die Partikularlösung als auch die allgemeine Lösung.

## Eingaben

- **Wert a** (text): First integer; negative values are supported.
- **Wert b** (text): Second integer; negative values are supported.
- **Rechte Seite c (optional, löst ax + by = c)** (text): Optional target: solves ax + by = c when gcd(a, b) divides c.
- **Ausgabestil** (select)

## Wann verwenden

- Berechnung der Bézout-Koeffizienten x und y zur Darstellung des ggT zweier ganzer Zahlen.
- Lösung linearer diophantischer Gleichungen a·x + b·y = c über den ganzen Zahlen inklusive Lösbarkeitsprüfung.
- Ermittlung des modularen inversen Elements in der Zahlentheorie und Kryptographie.

## Funktionsweise

- Geben Sie die ganzzahligen Werte für a und b ein (negative Vorzeichen werden unterstützt).
- Geben Sie optional einen Zielwert c ein, falls Sie eine diophantische Gleichung ax + by = c lösen möchten.
- Wählen Sie den Ausgabestil (vollständige Divisionsschritte oder kompakte Verifikation).
- Das Tool berechnet iterativ die Reste r = a·s + b·t, ermittelt ggT(a, b), kgV(a, b) sowie die Lösungsmenge für c.

## Anwendungsfälle

- Studenten und Dozenten der Mathematik zur Schritt-für-Schritt-Verifikation von Übungsaufgaben zur Zahlentheorie.
- Entwickler und Informatiker zur Ermittlung modularer Inversen für kryptographische Verfahren wie RSA.
- Lösen von linearen ganzzahligen Gleichungssystemen und Bestimmen ganzzahliger Linearkombinationen.

## Häufig gestellte Fragen

### Was liefert der erweiterte euklidische Algorithmus?

Er berechnet neben dem größten gemeinsamen Teiler ggT(a, b) auch die ganzzahligen Bézout-Koeffizienten x und y, sodass a·x + b·y = ggT(a, b) erfüllt ist.

### Wann besitzt die diophantische Gleichung ax + by = c ganzzahlige Lösungen?

Eine ganzzahlige Lösung existiert genau dann, wenn der ggT von a und b die rechte Seite c ohne Rest teilt.

### Werden negative Zahlen für a und b unterstützt?

Ja, das Werkzeug akzeptiert positive und negative ganze Zahlen für alle Eingabefelder.

### Wie wird das kleinste gemeinsame Vielfache (kgV) berechnet?

Das kgV ergibt sich direkt aus der Formel kgV(a, b) = |a · b| / ggT(a, b).

### Was unterscheidet die beiden Ausgabestile?

Der Stil 'Divisionsschritte anzeigen' listet jede Zeile der Rest- und Koeffizientenentwicklung auf, während 'Ergebnis und Verifikation' eine kompakte Zusammenfassung ausgibt.

## Ähnliche Tools

- [Boolescher Vereinfacher (Karnaugh-Veitch-Diagramm)](https://elysiatools.com/de/tools/boolean-algebra-simplifier): Vereinfacht Boolesche Funktionen zur minimalen DNF: Ausdruck eingeben (A–D, + ODER, · UND, ' NICHT, ≤ 4 Variablen) oder die Minterm-Liste Σm; der Quine-McCluskey-Algorithmus liefert die Primimplikanten, nimmt die wesentlichen dazu und ergänzt eine exakte Minimalüberdeckung; ausgegeben werden die minimale DNF, das Karnaugh-Diagramm in Gray-Code (2–4 Variablen), die kanonische Form Σm und eine Verifikation über alle Belegungen. Klassiker: AB + A'B → B; Σm(0,1,2,4,5,6) (3 Variablen) → B' + C'.
- [Verdünnungsverhältnis-Konverter (1:X ↔ 1/X ↔ %)](https://elysiatools.com/de/tools/dilution-ratio-converter): Rechnet zwischen den Labor-Schreibweisen für Verdünnungen um: Verhältnis 1:X, Bruch 1/X und Prozent, inklusive Verdünnungsfaktor und Lösungsmittel-/Verdünnungsteile. Unterstützt beide 1:X-Konventionen (X = Gesamteile oder 1 Teil Konzentrat + X Teile Verdünnung); mit Endvolumen werden die Mischvolumina berechnet. Klassiker: 1:5 = 1/5 = 20 %; für 100 mL mischt man 20 mL Konzentrat + 80 mL Verdünnung.
- [Modularer Inversen-Rechner (erweiterter Euklid)](https://elysiatools.com/de/tools/modular-inverse-calculator): Berechnet a⁻¹ mod m mit dem erweiterten euklidischen Algorithmus: liefert die Bézout-Koeffizienten a·x + m·y = gcd(a, m), die vollständige Tabelle der Vorwärtskoeffizienten (jede Zeile erfüllt r = a·s + m·t) und die Verifikation a × a⁻¹ ≡ 1 (mod m). Akzeptiert RSA-große Zahlen (bis 10⁵¹²) und meldet deutlich, wenn gcd(a, m) ≠ 1 kein Inverses zulässt. Klassiker: in RSA ist 17⁻¹ mod 3120 = 2753.
- [Modulararithmetik-Rechner (Addition / Subtraktion / Multiplikation / Inverses / Potenz)](https://elysiatools.com/de/tools/modulo-arithmetic-converter): Berechnet Addition, Subtraktion, Multiplikation, Inverses und schnelle Potenzierung modulo m mit exakter BigInt-Arithmetik (bis 10¹⁸). Die Grundoperationen zeigen die schrittweise Reduktion und liefern den kanonischen Repräsentanten aus \[0, m−1\]; das Inverse nutzt den erweiterten euklidischen Algorithmus und meldet gcd(a, m) ≠ 1 deutlich; die schnelle Potenz zeigt die Quadriere-und-multipliziere-Tabelle zu den Bits des Exponenten. Klassiker: 17⁵ mod 13 = 10; 5⁻¹ mod 18 = 11.
- [Wahrheitstabellen-Generator](https://elysiatools.com/de/tools/truth-table-generator): Erzeugt die vollständige Wahrheitstabelle eines Booleschen Ausdrucks (bis 6 Variablen, 64 Zeilen): unterstützt + ODER, ^ XOR, ·/*/& oder Juxtaposition UND, !/~/' NICHT und Klammern; die Variablen sind alphabetisch sortiert, jede Zeile zeigt die Belegung und den Wert F, zusätzlich die kanonischen Formen Σm (Minterme) und ΠM (Maxterme). Klassiker: AB + A'C hat Σm(1,3,6,7); A ^ B ^ C ist die ungerade Paritätsfunktion Σm(1,2,4,7).
- [Winkelgeschwindigkeits-Umrechner (rad/s / rpm / deg/s / Hz)](https://elysiatools.com/de/tools/angular-velocity-converter): Winkelgeschwindigkeits-Umrechnung: rad/s (SI-Basis) ↔ U/min (1=2π/60 rad/s) ↔ Grad/s (1=π/180 rad/s) ↔ Hz (1 Umdrehung/s=2π rad/s). Hz hier = Umdrehung pro Sekunde. Umrechnung über rad/s mit allen vier Äquivalenten. Ref.: Vinyl 33⅓ U/min≈3,49 rad/s, Leerlauf ~800 U/min≈83,8 rad/s.
- [Kanalquerschnitt-Rechner (Volumenstrom und Geschwindigkeit)](https://elysiatools.com/de/tools/duct-size-calculator): Dimensioniert einen Kanal aus Volumenstrom Q und Auslegungsgeschwindigkeit v: Fläche A=Q/v. Rund: Durchmesser D=√(4A/π). Rechteckig mit Verhältnis r=a/b: b=√(A/r), a=r·b, äquivalenter Durchmesser ASHRAE D_äq=1,30·(a·b)^0,625/(a+b)^0,25. Volumenstrom in m³/s/m³/h/CFM; Ergebnisse in mm und Zoll.
- [Dauerfestigkeitsrechner (Goodman/Gerber/Soderberg)](https://elysiatools.com/de/tools/fatigue-limit-calculator): Sicherheitsfaktor bei Schwingfestigkeit mit Mittelspannungskorrektur. Bei σ_a, σ_m und σ_uts, σ_-1, σ_y liefern drei klassische Kriterien: modifizierte Goodman (linear, konservativ), Gerber (parabolisch, besser für zähe Werkstoffe), Soderberg (über σ_y, am konservativsten). Der kleinste Wert ist maßgebend; additionally ob der Punkt innerhalb der Goodman-Linie liegt.

## Beispiele

- [Web Python Bildverarbeitung Beispiele](https://elysiatools.com/de/samples/web-image-processing-python): Web Python Bildverarbeitungsbeispiele mit PIL/Pillow einschließlich Lesen, Speichern, Skalieren und Formatkonvertierung
- [Android Java Bildverarbeitungsbeispiele](https://elysiatools.com/de/samples/android-image-processing-java): Android Java Bildverarbeitungsbeispiele einschließlich Lesen/Schreiben, Skalierung und Formatkonvertierung
- [Android Kotlin Bildverarbeitungsbeispiele](https://elysiatools.com/de/samples/android-image-processing-kotlin): Android Kotlin Bildverarbeitungsbeispiele einschließlich Lesen/Schreiben, Skalierung und Formatkonvertierung
- [Web Rust Bildverarbeitungsbeispiele](https://elysiatools.com/de/samples/web-image-processing-rust): Web Rust Bildverarbeitungsbeispiele einschließlich Lesen/Schreiben, Skalierung und Formatkonvertierung