Lineare diophantische Gleichungen

Dieser Rechner löst die lineare diophantische Gleichungen.

Diese Webseite exisiert dank der Arbeit von den folgenden Menschen:

Timur

Timur

Stefan Roesner

Erstellt: 2020-11-27 04:31:35, Letzte Aktualisierung: 2022-01-27 09:31:15
Creative Commons Attribution/Share-Alike License 3.0 (Unported)

Der Inhalt ist unter der Creative Commons Namensnennung / Weitergabe unter gleichen Bedingungen 3.0 (nicht portiert) lizenziert. Dies bedeutet, dass Sie diesen Inhalt unter den gleichen Lizenzbedingungen frei weitergeben oder ändern dürfen, jedoch mit Zuordnung zum Entwickler indem Sie einen Hyperlink auf Ihrer Webseite zu dieser Arbeit https://de.planetcalc.com/3303/ platzieren. Des Weiteren ändern Sie bitte keine Verweise auf das Originalwerk (falls vorhanden) das in diesem Inhlat vorhanden ist.

Wie immer ist hier der Rechner, gefolgt von der Theorie.

PLANETCALC, Lineare diophantische Gleichungen

Lineare diophantische Gleichungen

Gleichung
 
Alle Lösungen für x
 
Alle Lösungen für y
 
x
 
y
 
hidden output
 
hidden output
 

Da dies alles über Mathematik ist, habe ich ein für den Anfang wenig Inhalt von Wikipedia kopiert.

In der Mathematik ist die diophantische Gleichung eine Polynomgleichung, mit einer oder zwei Unbekannten, mit denen man nur nach Ganzzahl-Lösungen suchen kann (eine Ganzzahl-Lösung ist eine Lösung, in der die Unbekannten Ganzzahl-Werte haben). Eine lineare diophantische Gleichung ist eine Gleichung mit zwei Summen von Monomen des nullten oder ersten Grades.

Die einfachste Form einer diophantischen Gleichung ist
ax + by = c,

wobei a, b und c gegebene Ganzzahlen und x, y — Unbekannte sind.

Die Lösungen werden vollständig mit den folgenden Sätzen beschrieben: Diese diophantische Gleichung hat eine Lösung (in der x und y Ganzzahlen sind) wenn, und nur dann, c das Mehrfache vom größten gemeinsamen Teiler von a und b ist. Wenn (x,y) eine Lösung ist, dann haben die weiteren Lösungen die Form (x + kv, y - ku), in der k eine beliebige Ganzzahl ist, und u und v die Quotienten von a und b (respektiv) durch den größten gemeinsamen Nenner von a und b sind.

Um die Lösung zu finden, können Sie Erweiterter euklidischer Algorithmus (außer wenn a = b = 0 ist, wobei es entweder eine unendliche Anzahl von Lösungen oder keine Lösung gibt) nutzen.

Wenn a und b positive Ganzzahlen sind, dann kann man deren größten gemeinsamen Teiler g mit dem erweiterten euklidischen Algorithmus und mit x_g и y_g finden. Dann ergibt dann:

ax_g + by_g = g.

Wenn c das mehrfache von g ist, hat die diophantische Gleichung ax + by = c eine Lösung, ansonsten gibt es keine Lösung.

Das heißt, wenn c das Mehrfache von g ist, dann gilt

a x_g (\frac{c}{g}) + b y_g (\frac{c}{g})=c

Und eine mögliche Lösung wäre:

x_0 = x_g (\frac{c}{g})

y_0 = y_g(\frac{c}{g})

Wenn entweder a oder b negativ ist, kann man die Gleichung mit deren Modul lösen, und dann das Vorzeichen entsprechend ändern.

Wenn man eine der Lösungen kennt, kann man deren allgemeine Form finden.

Nehmen wir mal an g = ggT(a,b), dann haben wir:

ax_0 + by_0 = c.

Durch die Addition von \frac{b}{g} zu x_0 und der Subtraktion von \frac{a}{g} from y_0 bekommt man:

a(x_0 + \frac{b}{g}) + b(y_0 - \frac{a}{g}) = ax_0+by_0 + \frac{ab}{g}-\frac{ba}{g}=c

Das heißt, jegliche Zahlen wie diese:
x = x_0 + k \frac{b}{g}

y = y_0 - k \frac{a}{g},

wobei k eine Ganzzahl ist, sind die Lösungen der linearen diophantischen Gleichung.

URL zum Clipboard kopiert
PLANETCALC, Lineare diophantische Gleichungen

Kommentare