Lineare diophantische Gleichungen: Aufgaben mit Lösungen

Hier suchst du ganzzahlige Lösungen von Gleichungen. Wähle oben eine Aufgabenart oder lass sie gemischt. Mit „Neue Aufgaben“ entsteht ein neues Blatt.

Das brauchst du

• Lösbarkeit: a x + b y = c hat genau dann ganzzahlige Lösungen, wenn ggT(a, b) die Zahl c teilt.
• Lösen: Dividiere durch den ggT. Dann ist a x ≡ c (mod b), und x ≡ c · a⁻¹ (mod b) mit dem modularen Inversen von a. Alle Lösungen für x unterscheiden sich um Vielfache von b/ggT.
• Nichtnegative Lösungen: Probiere alle x mit a x ≤ c und prüfe, ob c − a x durch b teilbar ist.
• Münzproblem: Für teilerfremde a und b ist a·b − a − b der größte Betrag, der sich nicht mit den Münzen a und b zahlen lässt.
• Pythagoreische Tripel: Zu m > n gehört das Tripel (m² − n², 2mn, m² + n²).

Alles steht auf der Seite Diophantische Gleichungen bei Lösbarkeit, dem erweiterten euklidischen Algorithmus, den positiven Lösungen und den pythagoreischen Tripeln.