Lineare diophantische Gleichung ax + by = c lösen (ganzzahlige Lösungen, mit euklidischem Algorithmus)

Geben Sie die Koeffizienten der linearen diophantischen Gleichung ax + by = c ein. Die Gleichung darunter ist mit den Eingabefeldern verknüpft, Sie können die Zahlen also auch direkt in ihr ändern. Wenn Sie „Gesuchte Lösungen“ ändern, werden nur die positiven ganzzahligen Lösungen gezeigt.

Koeffizient a von x

Koeffizient b von y

Konstante c auf der rechten Seite

Gesuchte Lösungen

Geben Sie nur ganze Zahlen ein (keine Dezimalzahlen oder Brüche). Negative Zahlen sind möglich. Fehlt der x- oder y-Term, geben Sie für seinen Koeffizienten 0 ein.

Ergebnis und Diagramm

Geben Sie links die Koeffizienten a, b und c ein und klicken Sie auf „Berechnen“. Die ganzzahligen Lösungen und ein Diagramm erscheinen hier.

Inhaltsverzeichnis

[ Schließen X ]

Was Sie auf dieser Seite tun können
Wofür ist diese Berechnung nützlich?
Anleitung
Formeln und Diagramme
Symbole und Begriffe
- Symbole
- Begriffe
Was Sie vorab wissen sollten
Mit Excel berechnen
Mit Google Tabellen berechnen
Mit Python berechnen
Die Formel in LaTeX und anderen mathematischen Schreibweisen (zum Kopieren)
Die Berechnung von ChatGPT ausführen lassen
Die Vorteile von DataChef
Verwandte Funktionen
Alle NumberChef-Rechner

Was Sie auf dieser Seite tun können

Geben Sie die ganzzahligen Koeffizienten \(a,\ b,\ c\) ein und erhalten Sie die Paare ganzer Zahlen \(x,\ y\), die \(ax + by = c\) erfüllen (die ganzzahligen Lösungen)
Ist \(c\) kein Vielfaches des größten gemeinsamen Teilers von \(a\) und \(b\), gibt es keine ganzzahligen Lösungen. Die Seite prüft das und zeigt auch, warum
Sie können die Divisionstabelle des euklidischen Algorithmus und die Tabelle, die die Reste rückwärts durchläuft und daraus eine partikuläre Lösung aufbaut, Zeile für Zeile nachvollziehen
Die Antwort ist nicht nur ein Paar: Sie erhalten die allgemeine Lösung \(x = x_0 + \dfrac{b}{g}t,\ y = y_0 - \dfrac{a}{g}t\) (mit einer beliebigen ganzen Zahl \(t\)) und eine Tabelle der Lösungen für verschiedene Werte von \(t\)
Sie können sich auf die positiven oder nur auf die nichtnegativen Lösungen beschränken. So lassen sich Aufgaben wie „Wie viele Eintrittskarten zu 50 € und zu 80 € ergeben genau 1.000 €?“ direkt lösen

Als Koeffizienten sind nur ganze Zahlen erlaubt (keine Dezimalzahlen oder Brüche). Jeder Koeffizient darf höchstens 15 Stellen haben, und \(a\) und \(b\) dürfen nicht beide 0 sein.

Wofür ist diese Berechnung nützlich?

Kombinationen finden, die einen genauen Betrag oder eine genaue Stückzahl ergeben

Genau 1.000 € mit Eintrittskarten zu 50 € und zu 80 € ausgeben, etwas mit nur zwei Sorten Gewichten wiegen oder eine genaue Länge aus Stücken fester Länge zusammensetzen: Aufgaben wie diese, „feste Größen so kombinieren, dass ein Ziel genau erreicht wird“, sind genau das Problem, ganzzahlige Lösungen von \(ax + by = c\) zu finden.
Man kann keine negative Anzahl von Karten kaufen, deshalb erhält man die Antwort in der Praxis erst, wenn man auf die positiven ganzzahligen Lösungen eingrenzt.

Erkennen, welche Bestellmengen sich genau verpacken lassen

Haben Sie nur Kartons zu 6 Stück und Kartons zu 10 Stück, hängt es davon ab, ob \(6x + 10y = c\) eine Lösung in ganzen Zahlen ab 0 hat, ob Sie eine Bestellung über genau \(c\) Stück verpacken können. Der ggT von 6 und 10 ist 2, eine Bestellung über eine ungerade Stückzahl lässt sich also nie genau verpacken, egal wie Sie die Kartons kombinieren.
Beim Verpacken von Lebensmitteln oder Bauteilen zeigt das Wissen, welche Stückzahlen möglich sind, welche Bestellungen Sie annehmen können und welche Kartongrößen Sie vorrätig halten sollten.

Mit Gefäßen ohne Skala eine genaue Menge abmessen

Das bekannte Rätsel, mit nur einem 5-Liter-Gefäß und einem 3-Liter-Gefäß genau 4 Liter abzumessen, entspricht den ganzzahligen Lösungen von \(5x + 3y = 4\) (\(x\) und \(y\) zählen mit Vorzeichen, wie oft jedes Gefäß gefüllt oder geleert wird). Wegen \(\gcd(5,\ 3) = 1\) sagt Ihnen die Gleichung im Voraus, dass sich mit diesen beiden Gefäßen jede ganze Zahl von Litern abmessen lässt.
Es ist dieselbe Mathematik, die Sie im Labor oder in der Küche nutzen, wenn Sie fragen: „Kann ich die Menge, die ich brauche, mit den Geräten abmessen, die ich habe?“

Schlüssel für die RSA-Verschlüsselung im Internet erzeugen

Die RSA-Verschlüsselung, die Online-Banking und Online-Shopping schützt, berechnet den Wert \(d\) des privaten Schlüssels aus dem Wert \(e\) des öffentlichen Schlüssels, indem sie die lineare diophantische Gleichung \(e d + \varphi k = 1\) löst (\(\varphi\) ist eine vom Schlüssel abhängige ganze Zahl). Das Werkzeug dafür ist derselbe erweiterte euklidische Algorithmus wie auf dieser Seite.
Dieses Verfahren löst die Aufgabe sofort, selbst bei Zahlen mit Hunderten von Stellen, und das ist eines der Dinge, die die Verschlüsselung praxistauglich machen.

Produktionsplanung, die das Material restlos aufbraucht

Angenommen, Produkt A braucht \(a\) kg Material pro Stück und Produkt B \(b\) kg, und Sie wollen genau die \(c\) kg aufbrauchen, die Sie haben. Diese Planung ist das Problem, Lösungen von \(ax + by = c\) in ganzen Zahlen ab 0 zu finden. Ein halbes Produkt kann man nicht herstellen, die Antwort muss also eine ganze Zahl sein.
Das Gebiet, das Planungsaufgaben mit ganzzahligen Lösungen behandelt, heißt ganzzahlige Optimierung. Man nutzt es für Produktionsplanung, Dienstpläne, Tourenplanung und mehr.

Formeln und Diagramme

Wann es ganzzahlige Lösungen gibt

Diagramm

Mathematische Schreibweise (die übliche Schreibweise)

\(c\) \(=\) \(\gcd(a,\ b)\) \(\times\) \(m\)

In Worten (die Symbole durch Wörter ersetzt)

③ \(c\): Konstante auf der rechten Seite \(=\) ① \(g\): ggT von \(a\) und \(b\) \(\times\) ② \(m\): eine ganze Zahl

Die Formel in Worten

① Multiplizieren Sie den \(g\): ggT von \(a\) und \(b\)

② mit \(m\): eine ganze Zahl

③ Kann dieses Produkt genau gleich der \(c\): Konstante auf der rechten Seite sein (das heißt, ist \(c\) ein Vielfaches von \(g\)), gibt es ganzzahlige Lösungen. Sonst gibt es keine

Einfaches Beispiel

\(2x + 4y = 6\) hat ganzzahlige Lösungen, \(2x + 4y = 5\) dagegen kein einziges Paar (in beiden ist \(\gcd(2,\ 4) = 2\))

Konstante auf der rechten Seite (6) \(=\) ggT (2) \(\times\) ganze Zahl (3)

\(\gcd(2,\ 4) = 2\)

\(6 = 2 \times 3 \quad \Rightarrow \quad 2 \times 1 + 4 \times 1 = 6\)

\(5 = 2 \times 2 + 1 \quad \Rightarrow \quad 2x + 4y \neq 5\)

Der Kerngedanke

Warum muss \(c\) ein Vielfaches von \(g\) sein? \(a\) und \(b\) sind beide Vielfache von \(g\), Sie können also \(a = g a'\) und \(b = g b'\) schreiben. Dann wird die linke Seite zu \(ax + by = g(a'x + b'y)\) Solange \(x\) und \(y\) ganze Zahlen sind, ist die linke Seite immer ein Vielfaches von \(g\) und nichts anderes. Ist also \(c\) auf der rechten Seite kein Vielfaches von \(g\), kann man mit keinen ganzen Zahlen beide Seiten gleich machen. Ist \(c\) dagegen ein Vielfaches von \(g\), gibt es immer eine Lösung (das Lemma von Bézout in der nächsten Formel garantiert das). Im Diagramm besteht der Unterschied darin, ob die Gerade \(ax + by = c\) durch Gitterpunkte (Punkte, deren \(x\)- und \(y\)-Koordinate beide ganze Zahlen sind) läuft oder durch die Lücken zwischen ihnen schlüpft.

Lemma von Bézout (ein Paar ganzer Zahlen aus dem euklidischen Algorithmus)

Mathematische Schreibweise (die übliche Schreibweise)

\(a x_1\) \(+\) \(b y_1\) \(=\) \(\gcd(a,\ b)\)

In Worten (die Symbole durch Wörter ersetzt)

① \(a x_1\): \(a\) mal die ganze Zahl \(x_1\) aus dem euklidischen Algorithmus \(+\) ② \(b y_1\): \(b\) mal die ganze Zahl \(y_1\) aus dem euklidischen Algorithmus \(=\) ③ \(g\): ggT von \(a\) und \(b\)

Die Formel in Worten

① Addiert man den Term \(a x_1\): \(a\) mal die ganze Zahl \(x_1\) aus dem euklidischen Algorithmus

② und den Term \(b y_1\): \(b\) mal die ganze Zahl \(y_1\) aus dem euklidischen Algorithmus

③ so kann die Summe gleich dem \(g\): ggT von \(a\) und \(b\) sein. Solche ganzen Zahlen \(x_1,\ y_1\) gibt es immer, und man findet sie, indem man den euklidischen Algorithmus rückwärts durchläuft

Einfaches Beispiel

Wendet man den euklidischen Algorithmus auf \(7\) und \(5\) an und geht die Reste rückwärts durch, erhält man (\(\gcd(7,\ 5) = 1\))

\(7\) mal die ganze Zahl \(-2\) \(+\) \(5\) mal die ganze Zahl \(3\) \(=\) ggT (1)

\(7 = 5 \times 1 + 2, \quad 5 = 2 \times 2 + 1\)

\(1 = 5 - 2 \times 2 = 5 - (7 - 5) \times 2 = 3 \times 5 - 2 \times 7\)

\(7 \times (-2) + 5 \times 3 = -14 + 15 = 1\)

Der Kerngedanke

Jeden Rest im euklidischen Algorithmus kann man als Summe ganzzahliger Vielfacher der beiden ursprünglichen Zahlen schreiben. Tatsächlich ist \(2 = 7 - 5\), und setzt man das für die \(2\) im nächsten Schritt \(1 = 5 - 2 \times 2\) ein, wird \(1\) zu einer Summe ganzzahliger Vielfacher von \(7\) und \(5\). Der erweiterte euklidische Algorithmus macht das Schritt für Schritt für beliebige zwei Zahlen. Das gefundene Paar \(x_1,\ y_1\) ergibt den ggT \(g\), nicht \(c\), ist also noch keine Lösung Ihrer Gleichung. Multipliziert man beide Seiten mit \(\dfrac{c}{g}\), erhält man eine Lösung der gewünschten Gleichung. \(x_0 = \dfrac{c}{g} x_1, \quad y_0 = \dfrac{c}{g} y_1\) Für \(7x + 5y = 3\) ergibt zum Beispiel die Multiplikation der obigen Gleichung mit 3 die Gleichung \(7 \times (-6) + 5 \times 9 = 3\), also ist \((x_0\,|\,y_0) = (-6\,|\,9)\) eine Lösung. Dieser Rechner verschiebt die gefundene Lösung vor der Anzeige zu kleineren, besser lesbaren Zahlen (von welchem Paar Sie auch ausgehen, die allgemeine Lösung unten liefert dieselbe Lösungsmenge).

Alle ganzzahligen Lösungen (allgemeine Lösung)

Diagramm

Mathematische Schreibweise (die übliche Schreibweise)

\(x\) \(=\) \(x_0\) \(+\) \(\dfrac{b}{g}\) \(t\)

\(y\) \(=\) \(y_0\) \(-\) \(\dfrac{a}{g}\) \(t\)

In Worten (die Symbole durch Wörter ersetzt)

\(x\): ganzzahlige Lösung \(=\) ① \(x_0\): partikuläre Lösung \(+\) ② \(\dfrac{b}{g}\): Schrittweite von \(x\) ③ \(t\): eine beliebige ganze Zahl

\(y\): ganzzahlige Lösung \(=\) ④ \(y_0\): partikuläre Lösung \(-\) ⑤ \(\dfrac{a}{g}\): Schrittweite von \(y\) \(t\): eine beliebige ganze Zahl

Die Formel in Worten

① Beginnen Sie mit der \(x_0\): partikuläre Lösung

② und addieren Sie die \(\dfrac{b}{g}\): Schrittweite von \(x\)

③ multipliziert mit \(t\): eine beliebige ganze Zahl . Das ergibt die ganzzahlige Lösung \(x\)

④ Gleichzeitig beginnen Sie mit der \(y_0\): partikuläre Lösung

⑤ und subtrahieren die \(\dfrac{a}{g}\): Schrittweite von \(y\) multipliziert mit demselben \(t\). Das ergibt die ganzzahlige Lösung \(y\). Jede ganze Zahl, die Sie für \(t\) einsetzen, liefert eine weitere Lösung, und zusammen sind das alle ganzzahligen Lösungen

Einfaches Beispiel

Für \(3x + 4y = 10\) ist \((x_0\,|\,y_0) = (2\,|\,1)\) eine Lösung, und es ist \(\gcd(3,\ 4) = 1\), also

\(x\): ganzzahlige Lösung \(=\) partikuläre Lösung (2) \(+\) Schrittweite (4) ganze Zahl \(t\)

\(y\): ganzzahlige Lösung \(=\) partikuläre Lösung (1) \(-\) Schrittweite (3) ganze Zahl \(t\)

\(3 \times 2 + 4 \times 1 = 10\)

\(x = 2 + 4t, \quad y = 1 - 3t\)

\(t = 1 \ \Rightarrow \ (x\,|\,y) = (6\,|\,-2), \quad 3 \times 6 + 4 \times (-2) = 10\)

\(t = -1 \ \Rightarrow \ (x\,|\,y) = (-2\,|\,4), \quad 3 \times (-2) + 4 \times 4 = 10\)

Der Kerngedanke

Warum ändert sich \(x\) nur in Schritten von \(\dfrac{b}{g}\) und \(y\) nur in Schritten von \(\dfrac{a}{g}\)? Sind \((x\,|\,y)\) und \((x_0\,|\,y_0)\) beide Lösungen, ergibt die Differenz der beiden Gleichungen \(a(x - x_0) = -b(y - y_0)\) Teilt man beide Seiten durch \(g\), erhält man \(\dfrac{a}{g}(x - x_0) = -\dfrac{b}{g}(y - y_0)\). Dabei sind \(\dfrac{a}{g}\) und \(\dfrac{b}{g}\) teilerfremd (ihr einziger gemeinsamer Teiler ist 1). Die linke Seite muss also ein Vielfaches von \(\dfrac{b}{g}\) sein. Da \(\dfrac{a}{g}\) mit \(\dfrac{b}{g}\) keinen gemeinsamen Teiler hat, muss \(x - x_0\) selbst ein Vielfaches von \(\dfrac{b}{g}\) sein. Das heißt \(x - x_0 = \dfrac{b}{g}t\), und die Formel für \(y\) folgt daraus. Im Diagramm liegen die Gitterpunkte auf der Geraden \(ax + by = c\) in gleichen Abständen: \(\dfrac{b}{g}\) nach rechts und \(\dfrac{a}{g}\) nach oben oder unten.

Auf positive ganzzahlige Lösungen eingrenzen

Diagramm

Mathematische Schreibweise (die übliche Schreibweise)

\(x_0\) \(+\) \(\dfrac{b}{g}\) \(t\) \(\geq 1\)

\(y_0\) \(-\) \(\dfrac{a}{g}\) \(t\) \(\geq 1\)

In Worten (die Symbole durch Wörter ersetzt)

① \(x_0\): partikuläre Lösung \(+\) ② \(\dfrac{b}{g}\): Schrittweite von \(x\) ③ \(t\): eine beliebige ganze Zahl \(\geq 1\)

④ \(y_0\): partikuläre Lösung \(-\) ⑤ \(\dfrac{a}{g}\): Schrittweite von \(y\) \(t\): eine beliebige ganze Zahl \(\geq 1\)

Die Formel in Worten

① Die \(x_0\): partikuläre Lösung

② plus die \(\dfrac{b}{g}\): Schrittweite von \(x\)

③ mal \(t\): eine beliebige ganze Zahl (also die ganzzahlige Lösung \(x\)) muss mindestens 1 sein, und

④ die \(y_0\): partikuläre Lösung

⑤ minus die \(\dfrac{a}{g}\): Schrittweite von \(y\) mal dasselbe \(t\) (also die ganzzahlige Lösung \(y\)) muss ebenfalls mindestens 1 sein. Bestimmen Sie den Bereich von \(t\), der beides erfüllt, und Sie haben alle positiven ganzzahligen Lösungen

Einfaches Beispiel

Um mit Packungen zu 3 Stück und zu 5 Stück genau 47 Stück zusammenzubekommen (\(3x + 5y = 47\), \((x_0\,|\,y_0) = (4\,|\,7)\)), rechnet man so:

partikuläre Lösung (4) \(+\) Schrittweite (5) ganze Zahl \(t\) \(\geq 1\)

partikuläre Lösung (7) \(-\) Schrittweite (3) ganze Zahl \(t\) \(\geq 1\)

\(3 \times 4 + 5 \times 7 = 47\)

\(4 + 5t \geq 1 \ \Leftrightarrow \ t \geq -\dfrac{3}{5} \ \Leftrightarrow \ t \geq 0\)

\(7 - 3t \geq 1 \ \Leftrightarrow \ t \leq 2\)

\(0 \leq t \leq 2 \ \Rightarrow \ (x\,|\,y) = (4\,|\,7);\ (9\,|\,4);\ (14\,|\,1)\)

Der Kerngedanke

Bei Aufgaben, in denen Karten, Stückzahlen oder Personen gezählt werden, muss die Antwort eine positive ganze Zahl sein (oder eine ganze Zahl ab 0). Setzt man die allgemeine Lösung in Ungleichungen ein und bestimmt den Bereich von \(t\), bleiben nur die passenden Lösungen übrig. Da \(t\) eine ganze Zahl ist, kann man eine Grenze, die ein Bruch ist, etwa \(t \geq -\dfrac{3}{5}\), auf die nächste ganze Zahl im Inneren verschärfen (hier \(t \geq 0\)). Das ist der entscheidende Schritt. Haben \(a\) und \(b\) dasselbe Vorzeichen (zum Beispiel beide positiv), liefert die eine Ungleichung eine untere und die andere eine obere Schranke, es gibt also immer nur endlich viele Lösungen. Haben sie verschiedene Vorzeichen (zum Beispiel \(3x - 5y = 1\)), zeigen beide Schranken in dieselbe Richtung, und es gibt unendlich viele positive ganzzahlige Lösungen. Ist ein Koeffizient 0 (zum Beispiel \(0x + 5y = 10\)), hat die andere Variable genau einen Wert, und die Variable mit dem Koeffizienten 0 kann beliebig sein. Erfüllt dieser eine Wert die Bedingung, gibt es unendlich viele Lösungen, sonst keine. Es kann auch vorkommen, dass gar kein \(t\) die Bedingung erfüllt. Dann lautet die Antwort „Es gibt keine passende Kombination“.

Die lineare diophantische Gleichung \(ax + by = c\) hat nur dann ganzzahlige Lösungen, wenn \(c\) ein Vielfaches von \(g\), dem größten gemeinsamen Teiler von \(a\) und \(b\), ist. Ist das der Fall, rechnet man den euklidischen Algorithmus rückwärts durch und erhält eine partikuläre Lösung \((x_0\,|\,y_0)\). Dann ist jede andere Lösung \(x = x_0 + \dfrac{b}{g}t,\ y = y_0 - \dfrac{a}{g}t\) (mit einer beliebigen ganzen Zahl \(t\)).

Symbole und Begriffe

Symbole

\(a,\ b\)	a, b	Die Koeffizienten, mit denen \(x\) und \(y\) multipliziert werden. Für feste Zahlen nimmt man traditionell Buchstaben vom Anfang des Alphabets, \(a,\ b,\ c\). Auf dieser Seite sind beide ganze Zahlen.
\(c\)	c	Die Konstante auf der rechten Seite der Gleichung, vom lateinischen „constans“. Es ist die Summe, die Sie erreichen möchten, und ob sie ein Vielfaches des ggT ist, entscheidet darüber, ob es Lösungen gibt.
\(x,\ y\)	x, y	Die Unbekannten, nach denen Sie auflösen. Für Unbekannte Buchstaben vom Ende des Alphabets zu nehmen, soll auf Descartes zurückgehen. Auf dieser Seite zählen nur ganzzahlige Werte als Antwort.
\(\gcd(a,\ b)\)	ggT von a und b	Der größte gemeinsame Teiler von \(a\) und \(b\). In der Schule schreibt man ihn ggT(a, b), international und in vielen Büchern zur Zahlentheorie gcd(a, b) (von „greatest common divisor“). Manchmal kürzt man ihn auch zu \((a,\ b)\) ab.
\(g\)	g	Eine Kurzschreibweise für den größten gemeinsamen Teiler \(\gcd(a,\ b)\), vom Anfangsbuchstaben von „greatest“. Sie hält Formeln kurz, wie \(\dfrac{b}{g}\) und \(\dfrac{a}{g}\) in der allgemeinen Lösung.
\(x_0,\ y_0\)	x null, y null	Die partikuläre Lösung, also das erste Paar ganzzahliger Lösungen, das Sie finden. Die kleine 0 kennzeichnet es als Ausgangspunkt, als „Lösung Nummer 0“. Von hier aus schreibt man alle ganzzahligen Lösungen auf.
\(x_1,\ y_1\)	x eins, y eins	Das Paar ganzer Zahlen, das Sie finden, wenn Sie den euklidischen Algorithmus rückwärts durchlaufen. Es erfüllt \(a x_1 + b y_1 = g\). Multipliziert man es mit \(\dfrac{c}{g}\), erhält man die partikuläre Lösung \((x_0\,\|\,y_0)\).
\(t\)	t	Eine Variable, die jede ganze Zahl sein darf (ein Parameter). Mit ihr beschreibt eine einzige Formel alle ganzzahligen Lösungen auf einmal. Jede ganze Zahl, die Sie für \(t\) einsetzen, liefert eine weitere ganzzahlige Lösung.
\(m\)	m	Die ganze Zahl, die angibt, wie oft \(g\) in \(c\) enthalten ist. Für ganze Zahlen nimmt man oft Buchstaben wie \(m\), \(n\) und \(k\). Ganzzahlige Lösungen gibt es genau dann, wenn sich \(c = g \times m\) schreiben lässt.
\(q\)	q	Der Quotient einer Division, vom Anfangsbuchstaben von „Quotient“. In der Tabelle des euklidischen Algorithmus ist es die \(2\) in \(13 = 5 \times 2 + 3\).
\(r\)	r	Der Rest einer Division, von „Rest“ (englisch „remainder“). In der Tabelle des euklidischen Algorithmus ist es die \(3\) in \(13 = 5 \times 2 + 3\). Der Algorithmus endet, wenn dieser Rest 0 wird.
\(\geq\)	größer oder gleich	Das Zeichen einer Ungleichung für „die linke Seite ist größer oder gleich der rechten Seite“. \(x \geq 1\) sagt, dass \(x\) mindestens 1 ist. Das Gegenstück \(\leq\) bedeutet „kleiner oder gleich“.

Begriffe

lineare diophantische Gleichung	Eine lineare Gleichung mit zwei Unbekannten, aber nur einer Gleichung, wie \(ax + by = c\). Über den reellen Zahlen ist jeder Punkt der Geraden eine Lösung, die Lösung ist also nicht eindeutig. Auch wenn man nur ganzzahlige Lösungen zulässt, gibt es meist unendlich viele. Sie ist der einfachste Fall einer diophantischen Gleichung.
diophantische Gleichung	Der Name für Gleichungen, deren Lösungen ganze Zahlen sein müssen. Er geht auf Diophantos zurück, einen Mathematiker des antiken Griechenlands. Die lineare diophantische Gleichung auf dieser Seite ist der einfachste Fall.
ganzzahlige Lösung	Eine Lösung der Gleichung, bei der \(x\) und \(y\) beide ganze Zahlen sind. Bei Aufgaben zu Größen, die sich nicht teilen lassen, etwa die Zahl von Karten, Stücken oder Personen, sind nur ganzzahlige Lösungen sinnvoll.
partikuläre Lösung (spezielle Lösung)	Das erste Paar, das Sie unter den unendlich vielen ganzzahligen Lösungen finden. Jedes Paar genügt. Von ihm ausgehend beschreibt die allgemeine Lösung alle Lösungen.
allgemeine Lösung	Alle ganzzahligen Lösungen, geschrieben als eine einzige Formel mit einer ganzen Zahl \(t\). Jede ganze Zahl, die Sie für \(t\) einsetzen, liefert eine weitere Lösung.
ggT (größter gemeinsamer Teiler)	Die größte positive ganze Zahl, die jede von zwei oder mehr ganzen Zahlen teilt. Bei einer linearen diophantischen Gleichung entscheidet dieser Wert sowohl darüber, ob es Lösungen gibt, als auch darüber, wie weit sie auseinanderliegen.
euklidischer Algorithmus	Ein Verfahren, um den ggT zu finden: Man teilt die größere Zahl durch die kleinere und ersetzt das Paar immer wieder durch den Divisor und den Rest. Der Divisor in dem Schritt, in dem der Rest 0 wird, ist der ggT. Er steht schon in Euklids „Elementen“ um das 3. Jahrhundert v. Chr. und gilt oft als ältester Algorithmus der Welt.
erweiterter euklidischer Algorithmus	Ein Verfahren, um den ggT in der Form \(a x_1 + b y_1\) zu schreiben, indem man die Divisionsgleichungen des euklidischen Algorithmus von unten nach oben wieder einsetzt. Man nutzt es, um eine partikuläre Lösung einer linearen diophantischen Gleichung aufzubauen.
Lemma von Bézout (Bézout-Identität)	Der Satz, dass es immer ganze Zahlen \(x_1,\ y_1\) mit \(a x_1 + b y_1 = \gcd(a,\ b)\) gibt. Er ist nach dem französischen Mathematiker Bézout benannt. Er ist der Grund dafür, dass sich eine lineare diophantische Gleichung lösen lässt.
teilerfremd	Zwei ganze Zahlen sind teilerfremd, wenn ihr ggT 1 ist. Zum Beispiel sind 3 und 4 teilerfremd. \(\dfrac{a}{g}\) und \(\dfrac{b}{g}\) sind immer teilerfremd, und das ist der Grund dafür, dass die Lösungen gleich weit auseinanderliegen.
Vielfaches	Eine Zahl, die man erhält, wenn man eine ganze Zahl mit einer anderen ganzen Zahl multipliziert. Die Vielfachen von \(10\) sind \(\dots,\ -20,\ -10,\ 0,\ 10,\ 20,\ \dots\). Auch null und negative Zahlen zählen dazu.
Rest	Das, was übrig bleibt, wenn eine ganzzahlige Division nicht aufgeht. \(13 : 5\) hat den Quotienten \(2\) und den Rest \(3\). Der euklidische Algorithmus arbeitet nur mit diesen Resten.
Quotient	Bei der ganzzahligen Division die ganze Zahl, die angibt, wie oft der Divisor hineinpasst. In \(13 = 5 \times 2 + 3\) ist der Quotient \(2\).
Gitterpunkt	Ein Punkt der Koordinatenebene, dessen \(x\)- und \(y\)-Koordinate beide ganze Zahlen sind, wie die Ecken der Kästchen auf kariertem Papier. Die ganzzahligen Lösungen einer linearen diophantischen Gleichung sind genau die Gitterpunkte auf der Geraden \(ax + by = c\).
Parameter	Eine Variable, die Sie frei verändern können und mit der man eine ganze Lösungsmenge als eine Formel schreibt. Auf dieser Seite ist \(t\) der Parameter.
Koeffizient	Die Zahl vor einem Buchstaben. In \(3x\) ist der Koeffizient \(3\). Steht keine Zahl da, wie in \(x\), ist der Koeffizient 1.
Ungleichung	Eine Aussage, die die Größe zweier Werte vergleicht, zum Beispiel \(t \geq 0\). Man nutzt sie, um auf die positiven ganzzahligen Lösungen einzugrenzen.

Was Sie vorab wissen sollten

Hier steht, was Ihnen hilft, die Berechnung auf dieser Seite mit echtem Verständnis zu nutzen und nicht nur auf die Schaltfläche zu klicken.
Wenn Sie nicht weiterkommen, ist es der schnellste Weg, diese Themen noch einmal durchzugehen.

Division mit Rest (Klasse 3 bis 5, 8–11 Jahre)	Wissen, dass \(13 : 5\) den „Quotienten \(2\), Rest \(3\)“ ergibt, und dies als eine einzige Gleichung \(13 = 5 \times 2 + 3\) schreiben können Wissen, dass der Rest immer kleiner als der Divisor ist (mindestens \(0\) und kleiner als der Divisor)
Teiler, Vielfache und ggT (Klasse 5 bis 6, 10–12 Jahre)	Zwischen „\(6\) ist ein Vielfaches von \(3\)“ und „\(3\) ist ein Teiler von \(6\)“ wechseln können Bestimmen können, dass der größte gemeinsame Teiler von \(12\) und \(18\) gleich \(6\) ist (auch mit der Primfaktorzerlegung) Wissen, dass zwei Zahlen, deren ggT \(1\) ist, „teilerfremd“ heißen
Terme und lineare Gleichungen (Klasse 6 bis 8, 11–14 Jahre)	Wissen, dass in einem Term wie \(ax + by\) die Zahlen \(a\) und \(b\) die Koeffizienten und \(x\) und \(y\) die Unbekannten sind Eine Gleichung wie \(3 \times 2 + 5y = 1\) nach \(y\) auflösen können Einen gemeinsamen Faktor ausklammern können, wie in \(4x + 6y = 2(2x + 3y)\)
Lineare Gleichungen mit zwei Variablen und ihre Graphen (Klasse 8, 13–14 Jahre)	Wissen, dass \(ax + by = c\) in der Koordinatenebene eine Gerade ist Wissen, dass es bei zwei Unbekannten und nur einer Gleichung nicht genau eine Lösung gibt, sondern jeder Punkt der Geraden eine Lösung ist
Ungleichungen (Klasse 7 bis 9, 12–15 Jahre)	\(5t \geq 1\) in die Form \(t \geq \dfrac{1}{5}\) umformen können Wissen, dass sich das Ungleichheitszeichen umkehrt, wenn man beide Seiten durch eine negative Zahl teilt Wissen, dass man bei \(t \leq \dfrac{5}{3}\) und ganzzahligem \(t\) auf \(t \leq 1\) verschärfen kann
Bruchrechnung (Klasse 5 bis 7, 10–13 Jahre)	Einen Bruch wie \(\dfrac{80}{10} = 8\) kürzen können Negative Brüche wie \(-\dfrac{3}{8}\) auf dem Zahlenstrahl der Größe nach vergleichen können

Mit Excel berechnen

Kopieren Sie die gesamte Tabelle unten und fügen Sie sie in Zelle A1 von Excel ein. Sie funktioniert unverändert.

Tabelle zur Prüfung, ob es ganzzahlige Lösungen gibt

Koeffizient a von x	50
Koeffizient b von y	80
Konstante c auf der rechten Seite	1000
ggT g	=GGT(B1;B2)
Rest von c : g	=REST(B3;B4)
Ganzzahlige Lösungen?	=WENN(B5=0;"Lösungen vorhanden";"Keine Lösungen")

Tabelle zur Prüfung des Lemmas von Bézout

Koeffizient a von x	50
Koeffizient b von y	80
x1 aus dem euklidischen Algorithmus	-3
y1 aus dem euklidischen Algorithmus	2
a×x1 + b×y1	=B1B3+B2B4
ggT g	=GGT(B1;B2)

Tabelle, um aus der allgemeinen Lösung Lösungen zu erzeugen

Koeffizient a von x	50
Koeffizient b von y	80
Konstante c auf der rechten Seite	1000
ggT g	=GGT(B1;B2)
Partikuläre Lösung x0	4
Partikuläre Lösung y0	10
Ganze Zahl t	1
x = x0 + (b/g)×t	=B5+(B2/B4)*B7
y = y0 − (a/g)×t	=B6-(B1/B4)*B7
Probe a×x + b×y	=B1B8+B2B9

Tabelle zur Eingrenzung auf positive ganzzahlige Lösungen

Koeffizient a von x	50
Koeffizient b von y	80
ggT g	=GGT(B1;B2)
Partikuläre Lösung x0	4
Partikuläre Lösung y0	10
Untere Schranke von t (aus x ≥ 1)	=-GANZZAHL((B4-1)/(B2/B3))
Obere Schranke von t (aus y ≥ 1)	=GANZZAHL((B5-1)/(B1/B3))
Anzahl der positiven ganzzahligen Lösungen	=MAX(0;B7-B6+1)

Nach dem Einfügen sind die oberen Zeilen (Koeffizienten und partikuläre Lösung) Ihre Eingaben, und die unteren Zeilen werden automatisch berechnet. GGT liefert den größten gemeinsamen Teiler, REST liefert den Rest einer Division, und GANZZAHL schneidet die Nachkommastellen ab (rundet ab).
Die erste Tabelle nutzt das Beispiel 50x + 80y = 1000. Der ggT ist 10, und 1000 : 10 lässt den Rest 0, deshalb steht dort „Lösungen vorhanden“. Ändern Sie 1000 in 1001, wechselt die Anzeige zu „Keine Lösungen“.
Die zweite Tabelle prüft, dass x1 = −3 und y1 = 2, gefunden durch Rückwärtsrechnen im euklidischen Algorithmus, das Lemma von Bézout tatsächlich erfüllen. 50×(−3) + 80×2 = 10, das stimmt mit dem ggT überein.
Die dritte Tabelle entnimmt der allgemeinen Lösung eine Lösung. Geben Sie für t die 1 ein, erhalten Sie x = 12 und y = 5, und die Probezeile ergibt wieder 1000. Probieren Sie andere ganze Zahlen für t aus.
Die vierte Tabelle grenzt auf die positiven ganzzahligen Lösungen ein. Die untere Schranke von t ist 0 und die obere 1, es gibt also 2 positive ganzzahlige Lösungen (t = 0 und t = 1). Diese beiden Formeln gelten für den Fall, dass a und b beide positiv sind. Bei einem negativen Koeffizienten kehrt sich die Richtung der Ungleichung um, seien Sie also vorsichtig.

Mit Google Tabellen berechnen

Kopieren Sie die gesamte Tabelle unten und fügen Sie sie in Zelle A1 von Google Tabellen ein. Sie funktioniert unverändert.

Tabelle zur Prüfung, ob es ganzzahlige Lösungen gibt

Koeffizient a von x	50
Koeffizient b von y	80
Konstante c auf der rechten Seite	1000
ggT g	=GGT(B1;B2)
Rest von c : g	=REST(B3;B4)
Ganzzahlige Lösungen?	=WENN(B5=0;"Lösungen vorhanden";"Keine Lösungen")

Tabelle zur Prüfung des Lemmas von Bézout

Koeffizient a von x	50
Koeffizient b von y	80
x1 aus dem euklidischen Algorithmus	-3
y1 aus dem euklidischen Algorithmus	2
a×x1 + b×y1	=B1B3+B2B4
ggT g	=GGT(B1;B2)

Tabelle, um aus der allgemeinen Lösung Lösungen zu erzeugen

Koeffizient a von x	50
Koeffizient b von y	80
Konstante c auf der rechten Seite	1000
ggT g	=GGT(B1;B2)
Partikuläre Lösung x0	4
Partikuläre Lösung y0	10
Ganze Zahl t	1
x = x0 + (b/g)×t	=B5+(B2/B4)*B7
y = y0 − (a/g)×t	=B6-(B1/B4)*B7
Probe a×x + b×y	=B1B8+B2B9

Tabelle zur Eingrenzung auf positive ganzzahlige Lösungen

Koeffizient a von x	50
Koeffizient b von y	80
ggT g	=GGT(B1;B2)
Partikuläre Lösung x0	4
Partikuläre Lösung y0	10
Untere Schranke von t (aus x ≥ 1)	=-GANZZAHL((B4-1)/(B2/B3))
Obere Schranke von t (aus y ≥ 1)	=GANZZAHL((B5-1)/(B1/B3))
Anzahl der positiven ganzzahligen Lösungen	=MAX(0;B7-B6+1)

Dieselben Formeln wie in Excel funktionieren unverändert (GGT, REST, GANZZAHL, MAX und WENN heißen in Google Tabellen mit deutscher Spracheinstellung genauso und tun dasselbe). Kopieren Sie die gesamte Tabelle, fügen Sie sie in Zelle A1 ein und ersetzen Sie die Koeffizienten durch Ihre eigenen Zahlen.

Mit Python berechnen

from math import gcd

# Koeffizienten von ax + by = c (ganze Zahlen)
a, b, c = 50, 80, 1000

def extended_gcd(x, y):
    # erweiterter euklidischer Algorithmus: liefert den ggT und s, t mit x*s + y*t = ggT
    if y == 0:
        return x, 1, 0
    g, s, t = extended_gcd(y, x % y)
    return g, t, s - (x // y) * t

g = gcd(a, b)
if c % g != 0:
    print(f"{c} ist kein Vielfaches von {g}, also gibt es keine ganzzahligen Lösungen")
else:
    _, s, t = extended_gcd(a, b)
    x0, y0 = s * (c // g), t * (c // g)   # partikuläre Lösung (ein Paar ganzzahliger Lösungen)
    step_x, step_y = b // g, a // g       # Schrittweite von x und Schrittweite von y
    # so weit verschieben, bis x der kleinste Wert ab 0 ist, für eine besser lesbare Lösung
    n = x0 // step_x
    x0, y0 = x0 - n * step_x, y0 + n * step_y
    print(f"Partikuläre Lösung: (x, y) = ({x0}, {y0})")
    print(f"Allgemeine Lösung: x = {x0} + {step_x}t, y = {y0} - {step_y}t (t ist eine beliebige ganze Zahl)")
    for k in range(-2, 3):
        print(f"  t = {k:2}: (x, y) = ({x0 + step_x * k}, {y0 - step_y * k})")
    # nur die positiven ganzzahligen Lösungen behalten (x >= 1 und y >= 1)
    t_low = -((1 - x0) // -step_x)
    t_high = (y0 - 1) // step_y
    print("Positive ganzzahlige Lösungen:", [(x0 + step_x * k, y0 - step_y * k)
                                             for k in range(t_low, t_high + 1)])

Es genügen math.gcd aus der Standardbibliothek und ein rekursiv geschriebener erweiterter euklidischer Algorithmus. Das Beispiel ist 50x + 80y = 1000. Beim Ausführen werden die partikuläre Lösung (4, 10), die allgemeine Lösung x = 4 + 8t, y = 10 − 5t und die positiven ganzzahligen Lösungen [(4, 10), (12, 5)] ausgegeben. Ändern Sie die Koeffizienten und probieren Sie es aus (der letzte Teil für die positiven ganzzahligen Lösungen ist für den Fall geschrieben, dass a und b beide positiv sind).

Die Formel in LaTeX und anderen mathematischen Schreibweisen (zum Kopieren)

Wann es ganzzahlige Lösungen gibt

c = gcd(a, b) × m

c = \gcd(a, b) \times m

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>c</mi>
    <mo>=</mo>
    <mi>gcd</mi><mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
    <mo>&#xD7;</mo>
    <mi>m</mi>
  </mrow>
</math>

c = gcd(a, b) * m

Mod[c, GCD[a, b]] == 0

irem(c, igcd(a, b)) = 0;

mod(c, gcd(a, b)) == 0

c = gcd(a,b) × m

Lemma von Bézout (ein Paar ganzer Zahlen aus dem euklidischen Algorithmus)

a·x₁ + b·y₁ = gcd(a, b)

a x_1 + b y_1 = \gcd(a, b)

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>a</mi><msub><mi>x</mi><mn>1</mn></msub>
    <mo>+</mo>
    <mi>b</mi><msub><mi>y</mi><mn>1</mn></msub>
    <mo>=</mo>
    <mi>gcd</mi><mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
  </mrow>
</math>

a*x_1 + b*y_1 = gcd(a, b)

ExtendedGCD[a, b]

igcdex(a, b, x1, y1);

[g, x1, y1] = gcd(a, b);

a x_1 + b y_1 = gcd(a,b)

Alle ganzzahligen Lösungen (allgemeine Lösung)

x = x₀ + (b/g)t, y = y₀ − (a/g)t

x = x_0 + \frac{b}{g} t, \quad y = y_0 - \frac{a}{g} t

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>x</mi><mo>=</mo><msub><mi>x</mi><mn>0</mn></msub>
    <mo>+</mo>
    <mfrac><mi>b</mi><mi>g</mi></mfrac><mi>t</mi>
    <mo>,</mo><mspace width="1em"/>
    <mi>y</mi><mo>=</mo><msub><mi>y</mi><mn>0</mn></msub>
    <mo>&#x2212;</mo>
    <mfrac><mi>a</mi><mi>g</mi></mfrac><mi>t</mi>
  </mrow>
</math>

x = x_0 + (b/g)t, y = y_0 - (a/g)t

Solve[a x + b y == c, {x, y}, Integers]

isolve(a*x + b*y = c);

S = solve(a*x + b*y == c, [x y], 'Integer', true);

x = x_0 + (b/g)t, y = y_0 - (a/g)t

Auf positive ganzzahlige Lösungen eingrenzen

x₀ + (b/g)t ≥ 1 und y₀ − (a/g)t ≥ 1

x_0 + \frac{b}{g} t \geq 1, \quad y_0 - \frac{a}{g} t \geq 1

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <msub><mi>x</mi><mn>0</mn></msub>
    <mo>+</mo>
    <mfrac><mi>b</mi><mi>g</mi></mfrac><mi>t</mi>
    <mo>&#x2265;</mo><mn>1</mn>
    <mo>,</mo><mspace width="1em"/>
    <msub><mi>y</mi><mn>0</mn></msub>
    <mo>&#x2212;</mo>
    <mfrac><mi>a</mi><mi>g</mi></mfrac><mi>t</mi>
    <mo>&#x2265;</mo><mn>1</mn>
  </mrow>
</math>

x_0 + (b/g)t >= 1 and y_0 - (a/g)t >= 1

Solve[a x + b y == c && x >= 1 && y >= 1, {x, y}, Integers]

isolve({a*x + b*y = c, x >= 1, y >= 1});

S = solve([a*x + b*y == c, x >= 1, y >= 1], [x y], 'Integer', true);

x_0 + (b/g)t ≥ 1, y_0 − (a/g)t ≥ 1

Die Berechnung von ChatGPT ausführen lassen

Sie sind ein Rechenassistent für Mathematik (Eigenschaften ganzer Zahlen, Zahlentheorie). Führen Sie die folgende Berechnung aus, indem Sie tatsächlich Python-Code ausführen, und stützen Sie Ihre Antwort nur auf die Zahlen aus dem Ergebnis der Ausführung (nicht im Kopf rechnen und nicht schätzen).

Bestimmen Sie die ganzzahligen Lösungen der linearen diophantischen Gleichung 50x + 80y = 1000.
Zeigen Sie jeweils:
1. Den größten gemeinsamen Teiler von 50 und 80 und ob 1000 ein Vielfaches davon ist
2. Die Divisionsschritte des euklidischen Algorithmus (bis der Rest 0 ist) und die durch Rückwärtsrechnen gefundenen x1, y1 mit 50×x1 + 80×y1 = ggT
3. Eine partikuläre Lösung (x0, y0) und die allgemeine Lösung x = x0 + (b/g)t, y = y0 − (a/g)t
4. Alle ganzzahligen Lösungen, bei denen x und y beide mindestens 1 sind

Verwenden Sie in Python math.gcd und den erweiterten euklidischen Algorithmus, um exakt zu rechnen, und zeigen Sie die verwendeten Formeln und die Zahlen aus dem Ergebnis der Ausführung.

Anleitung

1

Zahlen eingeben

Geben Sie die Zahlen, mit denen Sie rechnen möchten, in die Eingabefelder ein
2

Berechnen

Klicken Sie auf die Schaltfläche „Berechnen“
3

Ergebnis ablesen

Das Ergebnis erscheint sofort. Auf derselben Seite finden Sie auch den Rechenweg und die Erklärung der Formel