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 auch direkt darin ändern. Mit „Gesuchte Lösungen“ schränken Sie auf positive ganzzahlige Lösungen ein.

Koeffizient a von x

Koeffizient b von y

Konstante c (rechte 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 Graph

Geben Sie links die Koeffizienten a, b und c ein und klicken Sie auf „Berechnen“. Hier erscheinen dann die ganzzahligen Lösungen und ein Graph.

Inhaltsverzeichnis

[ Schließen X ]

Das können Sie auf dieser Seite
Wofür braucht man diese Berechnung?
Anleitung
Formeln und Graphen
Symbole und Begriffe
- Symbole
- Begriffe
Das sollten Sie vorher wissen
So berechnen Sie es in Excel
So berechnen Sie es in Google Tabellen
So berechnen Sie es in Python
So schreiben Sie die Formel in LaTeX und anderen Formelsprachen (zum Kopieren)
So lassen Sie ChatGPT rechnen
Die Vorteile von DataChef
Verwandte Funktionen
Alle Rechner von NumberChef

Das können Sie auf dieser Seite

Sie geben die ganzzahligen Koeffizienten \(a\), \(b\) und \(c\) ein und erhalten die Zahlenpaare \((x \mid y)\), die \(ax + by = c\) erfüllen (die ganzzahligen Lösungen)
Ist \(c\) kein Vielfaches des ggT von \(a\) und \(b\), gibt es keine ganzzahligen Lösungen. Der Rechner prüft das und zeigt auch, warum
Die Divisionstabelle des euklidischen Algorithmus und die Tabelle, die rückwärts über die Reste eine spezielle Lösung aufbaut, sehen Sie Zeile für Zeile
Sie erhalten nicht nur ein Paar, sondern die allgemeine Lösung \(x = x_0 + \dfrac{b}{g}t,\ y = y_0 - \dfrac{a}{g}t\) (\(t\) beliebige ganze Zahl) und eine Tabelle mit Lösungen für verschiedene \(t\)
Sie können auf positive oder nichtnegative Lösungen einschränken. So lösen Sie direkt Aufgaben wie „Wie viele Karten zu 50 € und zu 80 € ergeben zusammen genau 1.000 €?“

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

Wofür braucht man diese Berechnung?

Kombinationen für einen genauen Betrag oder eine genaue Anzahl finden

Nur mit Karten zu 50 € und zu 80 € genau 1.000 € ausgeben, mit nur zwei Sorten von Gewichtsstücken ein Gewicht abwiegen, aus Stücken fester Länge genau eine bestimmte Länge legen: Solche Aufgaben – „Dinge fester Größe so kombinieren, dass genau ein Zielwert herauskommt“ – sind genau die Suche nach ganzzahligen Lösungen von \(ax + by = c\).
Eine negative Anzahl von Karten kann man nicht kaufen. In der Praxis steht die Antwort deshalb erst fest, wenn man auf positive ganzzahlige Lösungen eingeschränkt hat.

Erkennen, welche Stückzahlen sich genau verpacken lassen

Gibt es nur Kartons zu 6 und zu 10 Stück, hängt die Frage, ob eine Bestellung von genau \(c\) Stück aufgeht, davon ab, ob \(6x + 10y = c\) eine Lösung mit ganzen Zahlen ab 0 hat. Der ggT von 6 und 10 ist 2 – eine ungerade Stückzahl lässt sich also nie genau verpacken, egal wie man die Kartons kombiniert.
Beim Verpacken von Lebensmitteln oder Teilen zeigt Ihnen das, 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- und einem 3-Liter-Gefäß genau 4 Liter abzumessen (berühmt aus dem Film „Stirb langsam 3“), entspricht den ganzzahligen Lösungen von \(5x + 3y = 4\) (\(x\) und \(y\) zählen mit Vorzeichen, wie oft mit jedem Gefäß zugegossen oder abgegossen wird). Wegen \(\operatorname{ggT}(5;\ 3) = 1\) verrät die Gleichung schon vorab, dass sich mit diesen beiden Gefäßen jede ganze Literzahl abmessen lässt.
Das ist dieselbe Mathematik, die im Labor oder in der Küche hinter der Frage steckt: „Kann ich die nötige Menge mit dem Werkzeug abmessen, das ich habe?“

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

Die RSA-Verschlüsselung, die Onlinebanking und Onlineshopping schützt, bestimmt den privaten Schlüsselwert \(d\) aus dem öffentlichen Schlüsselwert \(e\), indem sie die lineare diophantische Gleichung \(e d + \varphi k = 1\) löst (\(\varphi\) ist eine ganze Zahl, die vom Schlüssel abhängt). Das Werkzeug dafür ist derselbe erweiterte euklidische Algorithmus wie auf dieser Seite.
Dieses Verfahren löst die Gleichung auch für Zahlen mit Hunderten von Stellen sofort – einer der Gründe, warum die Verschlüsselung praxistauglich ist.

Produktionsplanung, die das Material restlos aufbraucht

Produkt A braucht \(a\) kg Material pro Stück, Produkt B \(b\) kg, und die vorhandenen \(c\) kg sollen genau aufgebraucht werden. Dieser Plan ist die Suche nach Lösungen von \(ax + by = c\) in ganzen Zahlen ab 0. Ein halbes Produkt kann man nicht herstellen, also muss die Antwort ganzzahlig sein.
Das Fachgebiet für Planungsaufgaben, deren Antworten ganze Zahlen sein müssen, heißt ganzzahlige Optimierung. Sie wird für Produktionsplanung, Dienstpläne, Tourenplanung und mehr eingesetzt.

Formeln und Graphen

Wann es ganzzahlige Lösungen gibt

Graph

Mathematische Schreibweise (die übliche Formel)

\(c\) \(=\) \(\operatorname{ggT}(a;\ b)\) \(\times\) \(m\)

In Worten (Symbole durch Wörter ersetzt)

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

Die Formel in Worten

① Man multipliziert den \(g\): ggT von \(a\) und \(b\)

② mit \(m\): einer ganzen Zahl

③ Kann dieses Produkt genau gleich der \(c\): Konstante rechts sein (ist also \(c\) ein Vielfaches von \(g\)), gibt es ganzzahlige Lösungen, sonst keine

Einfaches Beispiel

\(2x + 4y = 6\) hat ganzzahlige Lösungen, \(2x + 4y = 5\) dagegen keine einzige (bei beiden ist \(\operatorname{ggT}(2;\ 4) = 2\))

Konstante rechts (6) \(=\) ggT (2) \(\times\) ganze Zahl (3)

\(\operatorname{ggT}(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 Grundgedanke

Warum muss \(c\) ein Vielfaches von \(g\) sein? Sowohl \(a\) als auch \(b\) sind Vielfache von \(g\), also kann man \(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 \(c\) rechts kein Vielfaches von \(g\), können also keine ganzen Zahlen die beiden Seiten gleich machen. Ist \(c\) dagegen ein Vielfaches von \(g\), gibt es immer eine Lösung (das garantiert das Lemma von Bézout, die nächste Formel). Im Graphen ist der Unterschied, ob die Gerade \(ax + by = c\) durch Gitterpunkte geht (Punkte, deren \(x\)- und \(y\)-Koordinate beide ganzzahlig sind) oder durch die Lücken dazwischen schlüpft.

Lemma von Bézout (ein Zahlenpaar aus dem euklidischen Algorithmus)

Mathematische Schreibweise (die übliche Formel)

\(a x_1\) \(+\) \(b y_1\) \(=\) \(\operatorname{ggT}(a;\ b)\)

In Worten (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

① Man addiert 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

③ und kann die Summe gleich dem \(g\): ggT von \(a\) und \(b\) machen. Solche ganzen Zahlen \(x_1,\ y_1\) gibt es immer; man findet sie durch Rückwärtsrechnen im euklidischen Algorithmus

Einfaches Beispiel

Euklidischer Algorithmus für \(7\) und \(5\), dann rückwärts über die Reste (\(\operatorname{ggT}(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 Grundgedanke

Jeder Rest im euklidischen Algorithmus lässt sich als Summe ganzzahliger Vielfacher der beiden Ausgangszahlen 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 für beliebige zwei Zahlen Schritt für Schritt. Das gefundene Paar \(x_1,\ y_1\) ergibt den ggT \(g\), nicht \(c\) – es ist also noch keine Lösung Ihrer Gleichung. Multipliziert man beide Seiten mit \(\dfrac{c}{g}\), erhält man eine Lösung der gesuchten Gleichung. \(x_0 = \dfrac{c}{g} x_1, \quad y_0 = \dfrac{c}{g} y_1\) Bei \(7x + 5y = 3\) zum Beispiel multipliziert man die Gleichung oben mit 3 und erhält \(7 \times (-6) + 5 \times 9 = 3\); also ist \((x_0 \mid y_0) = (-6 \mid 9)\) eine Lösung. Dieser Rechner verschiebt die gefundene Lösung vor der Anzeige auf kleinere, übersichtlichere Zahlen (von welchem Paar man auch ausgeht – die allgemeine Lösung unten ergibt dieselbe Lösungsmenge).

Alle ganzzahligen Lösungen (allgemeine Lösung)

Graph

Mathematische Schreibweise (die übliche Formel)

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

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

In Worten (Symbole durch Wörter ersetzt)

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

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

Die Formel in Worten

① Man startet bei der \(x_0\): speziellen Lösung

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

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

④ Gleichzeitig startet man bei der \(y_0\): speziellen Lösung

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

Einfaches Beispiel

Bei \(3x + 4y = 10\) ist \((x_0 \mid y_0) = (2 \mid 1)\) eine Lösung, und \(\operatorname{ggT}(3;\ 4) = 1\). Also gilt

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

\(y\): ganzzahlige Lösung \(=\) spezielle 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 \mid y) = (6 \mid -2), \quad 3 \times 6 + 4 \times (-2) = 10\)

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

Der Grundgedanke

Warum ändert sich \(x\) nur in Schritten von \(\dfrac{b}{g}\) und \(y\) nur in Schritten von \(\dfrac{a}{g}\)? Sind \((x \mid y)\) und \((x_0 \mid 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}\) keinen Teiler mit \(\dfrac{b}{g}\) gemeinsam hat, muss \(x - x_0\) selbst ein Vielfaches von \(\dfrac{b}{g}\) sein. Also ist \(x - x_0 = \dfrac{b}{g}t\), und daraus folgt die Formel für \(y\). Im Graphen liegen die Gitterpunkte auf der Geraden \(ax + by = c\) in gleichen Abständen: \(\dfrac{b}{g}\) zur Seite und \(\dfrac{a}{g}\) nach oben oder unten.

Auf positive ganzzahlige Lösungen einschränken

Graph

Mathematische Schreibweise (die übliche Formel)

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

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

In Worten (Symbole durch Wörter ersetzt)

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

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

Die Formel in Worten

① Die \(x_0\): spezielle Lösung

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

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

④ die \(y_0\): spezielle 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 – dann haben Sie alle positiven ganzzahligen Lösungen

Einfaches Beispiel

Genau 47 Stück nur mit Packungen zu 3 und zu 5 Stück (\(3x + 5y = 47\), \((x_0 \mid y_0) = (4 \mid 7)\)):

spezielle Lösung (4) \(+\) Schrittweite (5) ganze Zahl \(t\) \(\geq 1\)

spezielle 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 \mid y) = (4 \mid 7);\ (9 \mid 4);\ (14 \mid 1)\)

Der Grundgedanke

Bei Aufgaben, in denen Karten, Stück oder Personen gezählt werden, kommen nur positive ganze Zahlen (oder ganze Zahlen ab 0) infrage. Setzt man die allgemeine Lösung in Ungleichungen ein und bestimmt den Bereich von \(t\), bleiben nur die passenden Lösungen übrig. Weil \(t\) ganzzahlig ist, kann man eine Grenze wie \(t \geq -\dfrac{3}{5}\) auf die nächste ganze Zahl innerhalb des Bereichs verschärfen (hier \(t \geq 0\)). Das ist der entscheidende Schritt. Haben \(a\) und \(b\) dasselbe Vorzeichen (zum Beispiel beide positiv), liefert eine Ungleichung eine untere und die andere eine obere Grenze – es gibt also immer endlich viele Lösungen. Bei verschiedenen Vorzeichen (zum Beispiel \(3x - 5y = 1\)) zeigen beide Grenzen 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 ist beliebig. 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 genau dann ganzzahlige Lösungen, wenn \(c\) ein Vielfaches von \(g\), dem ggT von \(a\) und \(b\), ist. Dann baut man durch Rückwärtsrechnen im euklidischen Algorithmus eine spezielle Lösung \((x_0 \mid y_0)\) auf. Alle anderen Lösungen sind \(x = x_0 + \dfrac{b}{g}t,\ y = y_0 - \dfrac{a}{g}t\) (\(t\) beliebige ganze Zahl).

Symbole und Begriffe

Symbole

\(a,\ b\)	a, b	Die Koeffizienten vor \(x\) und \(y\). 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 (von lateinisch constans, „feststehend“). Sie ist die Summe, die herauskommen soll; ob sie ein Vielfaches des ggT ist, entscheidet, ob es Lösungen gibt.
\(x,\ y\)	x, y	Die gesuchten Unbekannten. Buchstaben vom Ende des Alphabets für Unbekannte zu verwenden, soll Descartes populär gemacht haben. Auf dieser Seite zählen nur ganzzahlige Werte als Lösung.
\(\operatorname{ggT}(a;\ b)\)	g-g-T von a und b	Der größte gemeinsame Teiler von \(a\) und \(b\), nach den Anfangsbuchstaben von „größter gemeinsamer Teiler“. In englischsprachigen Texten und Programmen heißt er \(\gcd(a, b)\) (greatest common divisor).
\(g\)	g	Kurzname für den ggT von \(a\) und \(b\). Er 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 spezielle Lösung, also die erste gefundene ganzzahlige Lösung. Die kleine 0 kennzeichnet sie als Ausgangspunkt, „Lösung Nummer 0“. Alle ganzzahligen Lösungen werden von hier aus geschrieben.
\(x_1,\ y_1\)	x eins, y eins	Das Zahlenpaar, das man durch Rückwärtsrechnen im euklidischen Algorithmus findet. Es erfüllt \(a x_1 + b y_1 = g\). Mit \(\dfrac{c}{g}\) multipliziert ergibt es die spezielle Lösung \((x_0 \mid 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 für \(t\) liefert eine weitere Lösung.
\(m\)	m	Die ganze Zahl, die angibt, das Wievielfache von \(g\) die Zahl \(c\) ist. Für ganze Zahlen nimmt man oft \(m\), \(n\) oder \(k\); \(m\) soll vom englischen „multiple“ (Vielfaches) kommen. Ganzzahlige Lösungen gibt es genau dann, wenn sich \(c = g \times m\) schreiben lässt.
\(q\)	q	Der Quotient einer Division, nach dem 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, nach dem englischen „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 Ungleichheitszeichen für „die linke Seite ist größer als oder gleich der rechten“. \(x \geq 1\) heißt: \(x\) ist mindestens 1. Das Gegenstück \(\leq\) heißt „kleiner oder gleich“.

Begriffe

lineare diophantische Gleichung	Eine lineare Gleichung mit zwei Unbekannten, aber nur einer Gleichung, etwa \(ax + by = c\), bei der ganzzahlige Lösungen gesucht sind. In den reellen Zahlen ist jeder Punkt der Geraden eine Lösung, die Lösung ist also nicht eindeutig. Selbst wenn man nur ganzzahlige Lösungen zulässt, gibt es meist unendlich viele. Sie ist die einfachste Art einer diophantischen Gleichung.
diophantische Gleichung	Bezeichnung für Gleichungen, deren Lösungen ganze Zahlen sein müssen. Der Name geht auf Diophantos von Alexandria zurück, einen Mathematiker der Antike. Die lineare diophantische Gleichung auf dieser Seite ist die einfachste Art.
ganzzahlige Lösung	Eine Lösung der Gleichung, bei der \(x\) und \(y\) beide ganze Zahlen sind. Bei Größen, die man nicht teilen kann – Anzahlen von Karten, Stück oder Personen –, sind nur ganzzahlige Lösungen sinnvoll.
spezielle Lösung	Das erste gefundene Paar unter den unendlich vielen ganzzahligen Lösungen (auch partikuläre Lösung). Jedes Paar ist geeignet. Von ihm aus beschreibt die allgemeine Lösung alle Lösungen.
allgemeine Lösung	Alle ganzzahligen Lösungen, zusammengefasst in einer Formel mit einer ganzen Zahl \(t\). Jede ganze Zahl für \(t\) 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, ob es Lösungen gibt, als auch, wie weit sie auseinanderliegen.
euklidischer Algorithmus	Ein Verfahren, den ggT zu bestimmen: Man teilt die größere Zahl durch die kleinere und ersetzt das Paar durch Divisor und Rest – immer wieder. Der Divisor im Schritt mit Rest 0 ist der ggT. Er steht in Euklids „Elementen“ aus der Zeit um 300 v. Chr. und gilt oft als ältester Algorithmus der Welt.
erweiterter euklidischer Algorithmus	Ein Verfahren, 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. Damit baut man eine spezielle Lösung einer linearen diophantischen Gleichung auf.
Lemma von Bézout	Der Satz, dass es immer ganze Zahlen \(x_1,\ y_1\) mit \(a x_1 + b y_1 = \operatorname{ggT}(a;\ b)\) gibt (auch Bézout-Identität). Er ist nach dem französischen Mathematiker Étienne Bézout benannt und der Grund, warum sich eine lineare diophantische Gleichung lösen lässt.
teilerfremd	Zwei ganze Zahlen sind teilerfremd, wenn ihr ggT 1 ist, zum Beispiel 3 und 4. \(\dfrac{a}{g}\) und \(\dfrac{b}{g}\) sind immer teilerfremd – deshalb liegen die Lösungen in gleichen Abständen.
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 0 und negative Zahlen zählen als Vielfache.
Rest	Was übrig bleibt, wenn eine ganzzahlige Division nicht aufgeht. \(13 : 5\) ergibt den Quotienten \(2\) und den Rest \(3\). Der euklidische Algorithmus arbeitet nur mit diesen Resten.
Quotient	Bei der ganzzahligen Division die Zahl, die angibt, wie oft der Divisor ganz hineinpasst. In \(13 = 5 \times 2 + 3\) ist der Quotient \(2\).
Gitterpunkt	Ein Punkt im Koordinatensystem, dessen \(x\)- und \(y\)-Koordinate beide ganzzahlig sind, wie die Kreuzungspunkte auf Karopapier. Die ganzzahligen Lösungen einer linearen diophantischen Gleichung sind genau die Gitterpunkte auf der Geraden \(ax + by = c\).
Parameter	Eine frei wählbare Variable, mit der man eine ganze Lösungsmenge in einer Formel schreibt. Auf dieser Seite ist \(t\) der Parameter.
Koeffizient	Die Zahl vor einem Buchstaben. In \(3x\) ist der Koeffizient \(3\). Steht keine Zahl davor, wie bei \(x\), ist der Koeffizient 1.
Ungleichung	Eine Aussage, die zwei Werte der Größe nach vergleicht, etwa \(t \geq 0\). Mit ihr schränkt man auf die positiven ganzzahligen Lösungen ein.

Das sollten Sie vorher wissen

Damit Sie die Rechnung auf dieser Seite nicht nur per Knopfdruck, sondern mit echtem Verständnis nutzen, hilft Ihnen dieses Vorwissen.
Wenn Sie nicht weiterkommen, ist es am schnellsten, diese Themen noch einmal zu wiederholen.

Division mit Rest (Klasse 3–5, 8–11 Jahre)	Sie wissen, dass \(13 : 5\) „Quotient \(2\), Rest \(3\)“ ergibt, und können das als eine Gleichung \(13 = 5 \cdot 2 + 3\) schreiben Sie wissen, dass der Rest immer kleiner als der Divisor ist (mindestens \(0\) und kleiner als der Divisor)
Teiler, Vielfache und ggT (Klasse 5–6, 10–12 Jahre)	Sie können „\(6\) ist ein Vielfaches von \(3\)“ und „\(3\) ist ein Teiler von \(6\)“ ineinander übersetzen Sie können bestimmen, dass der ggT von \(12\) und \(18\) gleich \(6\) ist (auch per Primfaktorzerlegung) Sie wissen, dass zwei Zahlen mit dem ggT \(1\) „teilerfremd“ heißen
Terme und lineare Gleichungen (Klasse 7–8, 12–14 Jahre)	Sie wissen, dass in einem Term wie \(ax + by\) die Zahlen \(a\) und \(b\) Koeffizienten und \(x\) und \(y\) Unbekannte sind Sie können eine Gleichung wie \(3 \cdot 2 + 5y = 1\) nach \(y\) auflösen Sie können einen gemeinsamen Faktor ausklammern, etwa \(4x + 6y = 2(2x + 3y)\)
Lineare Gleichungen mit zwei Variablen und ihr Graph (Klasse 8–9, 13–15 Jahre)	Sie wissen, dass \(ax + by = c\) im Koordinatensystem eine Gerade ist Sie wissen, dass es bei zwei Unbekannten und nur einer Gleichung keine eindeutige Lösung gibt und jeder Punkt der Geraden eine Lösung ist
Ungleichungen (Klasse 7–9, 12–15 Jahre)	Sie können \(5t \geq 1\) zu \(t \geq \dfrac{1}{5}\) umformen Sie wissen, dass sich das Ungleichheitszeichen umdreht, wenn man beide Seiten durch eine negative Zahl teilt Sie wissen, dass man \(t \leq \dfrac{5}{3}\) für ganzzahlige \(t\) zu \(t \leq 1\) verschärfen kann
Bruchrechnung (Klasse 6–7, 11–13 Jahre)	Sie können kürzen wie bei \(\dfrac{80}{10} = 8\) Sie können negative Brüche wie \(-\dfrac{3}{8}\) auf dem Zahlenstrahl der Größe nach einordnen

So berechnen Sie es in Excel

Kopieren Sie die ganze Tabelle und fügen Sie sie in Zelle A1 von Excel ein – dann funktioniert sie direkt.

Tabelle, die prüft, ob es ganzzahlige Lösungen gibt

Koeffizient a von x	50
Koeffizient b von y	80
Konstante c (rechte 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 Probe 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, die Lösungen aus der allgemeinen Lösung erzeugt

Koeffizient a von x	50
Koeffizient b von y	80
Konstante c (rechte Seite)	1000
ggT g	=GGT(B1;B2)
Spezielle Lösung x0	4
Spezielle 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 zum Einschränken auf positive ganzzahlige Lösungen

Koeffizient a von x	50
Koeffizient b von y	80
ggT g	=GGT(B1;B2)
Spezielle Lösung x0	4
Spezielle Lösung y0	10
Untergrenze von t (aus x ≥ 1)	=-GANZZAHL((B4-1)/(B2/B3))
Obergrenze von t (aus y ≥ 1)	=GANZZAHL((B5-1)/(B1/B3))
Anzahl positiver ganzzahliger Lösungen	=MAX(0;B7-B6+1)

Nach dem Einfügen sind die oberen Zeilen (Koeffizienten und spezielle Lösung) Ihre Eingaben; die unteren Zeilen werden automatisch berechnet. GGT liefert den ggT, REST den Rest einer Division, und GANZZAHL schneidet die Nachkommastellen ab (rundet ab).
Die erste Tabelle verwendet das Beispiel 50x + 80y = 1000. Der ggT ist 10, und 1000 : 10 lässt den Rest 0, also erscheint „Lösungen vorhanden“. Ändern Sie 1000 in 1001, wechselt die Anzeige zu „Keine Lösungen“.
Die zweite Tabelle prüft, ob 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, also genau der ggT.
Die dritte Tabelle liefert eine Lösung aus der allgemeinen Lösung. Mit t = 1 erhalten Sie x = 12 und y = 5, und die Probe ergibt wieder 1000. Probieren Sie auch andere ganze Zahlen für t.
Die vierte Tabelle schränkt auf positive ganzzahlige Lösungen ein. Die Untergrenze von t ist 0, die Obergrenze 1, also gibt es 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 dreht sich die Richtung der Ungleichung um – Vorsicht.

So berechnen Sie es in Google Tabellen

Kopieren Sie die ganze Tabelle und fügen Sie sie in Zelle A1 von Google Tabellen ein – dann funktioniert sie direkt.

Tabelle, die prüft, ob es ganzzahlige Lösungen gibt

Koeffizient a von x	50
Koeffizient b von y	80
Konstante c (rechte 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 Probe 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, die Lösungen aus der allgemeinen Lösung erzeugt

Koeffizient a von x	50
Koeffizient b von y	80
Konstante c (rechte Seite)	1000
ggT g	=GGT(B1;B2)
Spezielle Lösung x0	4
Spezielle 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 zum Einschränken auf positive ganzzahlige Lösungen

Koeffizient a von x	50
Koeffizient b von y	80
ggT g	=GGT(B1;B2)
Spezielle Lösung x0	4
Spezielle Lösung y0	10
Untergrenze von t (aus x ≥ 1)	=-GANZZAHL((B4-1)/(B2/B3))
Obergrenze von t (aus y ≥ 1)	=GANZZAHL((B5-1)/(B1/B3))
Anzahl positiver ganzzahliger Lösungen	=MAX(0;B7-B6+1)

Dieselben Formeln wie in Excel funktionieren unverändert (GGT, REST, GANZZAHL, MAX und WENN haben in Google Tabellen dieselben Namen und dieselbe Wirkung). Kopieren Sie die ganze Tabelle, fügen Sie sie in Zelle A1 ein und ersetzen Sie die Koeffizienten durch Ihre eigenen Zahlen.

So berechnen Sie es in Python

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 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)   # spezielle Lösung (eine ganzzahlige Lösung)
    step_x, step_y = b // g, a // g       # Schrittweite von x und Schrittweite von y
    # verschieben, bis x der kleinste Wert ab 0 ist, für eine übersichtliche Lösung
    n = x0 // step_x
    x0, y0 = x0 - n * step_x, y0 + n * step_y
    print(f"Spezielle Lösung: (x, y) = ({x0}, {y0})")
    print(f"Allgemeine Lösung: x = {x0} + {step_x}t, y = {y0} - {step_y}t (t 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 (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)])

Sie brauchen nur math.gcd aus der Standardbibliothek (gcd ist der englische Name des ggT) und einen rekursiv geschriebenen erweiterten euklidischen Algorithmus. Das Beispiel ist 50x + 80y = 1000. Beim Ausführen erscheinen die spezielle Lösung (4, 10), die allgemeine Lösung x = 4 + 8t, y = 10 − 5t und die positiven ganzzahligen Lösungen [(4, 10), (12, 5)] – Python schreibt Zahlenpaare mit Komma, (4, 10) entspricht (4 | 10). Ändern Sie die Koeffizienten und probieren Sie es aus (der letzte Teil für positive Lösungen ist für den Fall geschrieben, dass a und b beide positiv sind).

So schreiben Sie die Formel in LaTeX und anderen Formelsprachen (zum Kopieren)

Wann es ganzzahlige Lösungen gibt

c = ggT(a; b) × m

c = \operatorname{ggT}(a;\ b) \times m

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>c</mi>
    <mo>=</mo>
    <mi>ggT</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 = ggT(a;b) × m

Lemma von Bézout (ein Zahlenpaar aus dem euklidischen Algorithmus)

a·x₁ + b·y₁ = ggT(a; b)

a x_1 + b y_1 = \operatorname{ggT}(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>ggT</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 = ggT(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 einschränken

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

So lassen Sie ChatGPT rechnen

Sie sind ein Rechenassistent für Zahlentheorie (Eigenschaften ganzer Zahlen). 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 Ausführungsergebnis (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 ggT 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 spezielle 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

Rechnen Sie in Python exakt mit math.gcd und dem erweiterten euklidischen Algorithmus und zeigen Sie die verwendeten Formeln und die Zahlen aus dem Ausführungsergebnis.

Anleitung

1

Werte eingeben

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

Berechnen

Klicken Sie auf die Schaltfläche „Berechnen“
3

Ergebnis ansehen

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