Lineare diophantische Gleichungen

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

Lineare diophantische Gleichungen

Konstante a

Konstante b

Konstante c

berechnen

Gleichung

 

Alle Lösungen für x

 

Alle Lösungen für y

 

x

 

y

 

hidden output

 

hidden output

 

 Link  Abspeichern  Widget

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
,

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 и finden. Dann ergibt dann:

.

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

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

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

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:

.

Durch die Addition von zu und der Subtraktion von from bekommt man:

Das heißt, jegliche Zahlen wie diese:

,

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