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

Erweiterter euklidischer Algorithmus (ax + by = ggT(a, b)) | Kostenloses Online-Tool | Elysia Tools

Leitfaden zur Tool-Nutzung

Erfahren Sie, wann dieses Tool passt, was es unterstützt und wie Nutzer es anwenden.

Wichtige Fakten

Kategorie: Math & Numbers
Eingabetypen: text, select
Ausgabetyp: text
Sample-Abdeckung: 4
API bereit: Ja

Ü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.

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.

So funktioniert es

1Geben Sie die ganzzahligen Werte für a und b ein (negative Vorzeichen werden unterstützt).
2Geben Sie optional einen Zielwert c ein, falls Sie eine diophantische Gleichung ax + by = c lösen möchten.
3Wählen Sie den Ausgabestil (vollständige Divisionsschritte oder kompakte Verifikation).
4Das 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.

Beispiele

1. Bézout-Identität für 240 und 46

Mathematikstudent

Hintergrund

In einer Vorlesung über elementare Zahlentheorie soll der ggT von 240 und 46 als Linearkombination dargestellt werden.

Aufgabe

Berechnung aller Zwischenschritte und der Bézout-Koeffizienten für a = 240 und b = 46.

Verwendung

Trage 240 in Feld a und 46 in Feld b ein, wähle den Stil 'Divisionsschritte anzeigen' und starte die Berechnung.

a = 240, b = 46, style = steps

Ergebnis

Erhält ggT(240, 46) = 2, kgV = 5520 sowie die Identität 240·(-9) + 46·47 = 2 mit vollständiger Schritt-Tabelle.

2. Lineare diophantische Gleichung 240x + 46y = 4

Kryptographie-Entwickler

Hintergrund

Ein Entwickler benötigt eine ganzzahlige Lösung für eine Gleichung mit Zielwert c = 4.

Aufgabe

Prüfung der Lösbarkeit und Ermittlung der allgemeinen Lösungsformel über den ganzen Zahlen.

Verwendung

Gib a = 240, b = 46 und c = 4 ein und wähle den Ausgabestil 'Ergebnis und Verifikation'.

FAQ

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.

a = 240, b = 46, c = 4, style = result

Dieses Tool ausführen

Beispiele zu diesem Tool

Mit verwandten Tools und Themen fortfahren

Erfahren Sie, wann dieses Tool passt, was es unterstützt und wie Nutzer es anwenden.

Wichtige Fakten

Überblick

Wann verwenden

So funktioniert es

Anwendungsfälle

Beispiele

1. Bézout-Identität für 240 und 46

2. Lineare diophantische Gleichung 240x + 46y = 4

FAQ

Web Python Bildverarbeitung Beispiele

Android Java Bildverarbeitungsbeispiele

Android Kotlin Bildverarbeitungsbeispiele

Web Rust Bildverarbeitungsbeispiele

Boolescher Vereinfacher (Karnaugh-Veitch-Diagramm)

Verdünnungsverhältnis-Konverter (1:X ↔ 1/X ↔ %)

Modularer Inversen-Rechner (erweiterter Euklid)

Modulararithmetik-Rechner (Addition / Subtraktion / Multiplikation / Inverses / Potenz)