Lösungsverfahren für lineare diophantische Gleichungen mit zwei Unbekannten
Gesucht sind alle ganzzahligen Lösungen x, y der Gleichung
px + qy = r
Dabei seien p, q, r ganze Zahlen mit p und q verschieden von Null.
Keine Lösung gibt es, falls g = ggT(p,q) kein Teiler von r ist.
Ansonsten gibt es immer Lösungen. Zunächst sucht man eine irgendeine spezielle ganzzahlige Lösung (xo,yo) der Gleichung
px + qy = g
Diese spezielle Lösung findet man häufig durch (systematisches) Ausprobieren. Dann erhält man alle Lösungen der ursprünglichen Gleichung mit
x = (rxo - qt)/g y = (ryo + pt)/g mit beliebigen ganzzahligen t .
Das folgende Beispiel stammt aus der Maya-Kalenderrechnung von der Monatsbriefmarke:
20x - 13y = b - a
Hier ist g = 1 , also sucht man zuerst eine spezielle Lösung von
20x - 13y = 1
Durch Probieren erhält man schnell (xo,yo) = (2,3) . Da in der ursprünglichen Gleichung p = 20, q = -13, r = b - a ist, lauten alle Lösungen:
x = 2(b - a) + 13t y = 3(b - a) + 20t
Manfred Börgens - Briefmarke des Monats März 2004 - Hinweis - Stand 10.12.2003