Wenn a*x + b*y = c mit ganzen positiven Zahlen a, b und c gegeben ist und alle ganzzahligen Lösungspaare (x, y) mit x>0 und y>0 gesucht sind, kann man so vorgehen: Zuerst teilt man beide Seiten der Gleichung durch den größten gemeinsamen Teiler t = ggT(a,b) von a und b und erhält die Gleichung
A*x + B*y=C mit A=a/t, B=b/t und C=c/t.
Dabei bleibt die linke Seite der Gleichung ganzzahlig und wenn C nicht ganzzahlig ist, dann gibt es offenbar keine Lösungspaare (x, y). Ist C ganzzahlig, dann hat man das Ausgangsproblem mit der Eigenschaft, dass A und B teilerfremd sind.
Vorerst sollen die Bedingungen x>0 und y>0 ignoriert werden und überhaupt ganzzahlige Lösungen gesucht werden. Angenommen (X,Y) wäre eine Lösung von A*X+B*Y=C, dann sind auch (X+k*B, Y-k*A) für beliebige ganzzahlige k weitere Lösungen, wie man durch Einsetzen sofort sieht. Damit hat man aber auch schon alle Lösungen gefunden, denn wäre (X+l, U) eine Lösung, dann gilt A(X+l)+B*U=C. Subtrahiert man davon A*X+B*Y=C, dann erhält man:
A*l+B*(U-Y)=0 oder A*l=B*(Y-U) und da A und B teilerfremd sind, muss l ein Vielfaches von B sein. Also l=k*B. Dann ist A*k*B=B*(Y-U) also U=Y-k*A. Damit hat man schon gezeigt, dass alle Lösungen gefunden sind. D.h. ausgehend von einer einzigen Lösungen sind alle weiteren sofort bekannt. So eine einzelne Lösung findet man sehr schnell mit dem erweiterten Euklidschen Algorithmus. Der liefert sehr effizient ein Paar (s, t) für A*s+B*t=ggT(A,B)=1. Multipliziert man diese Gleichung mit C, dann erhält man A*X+B*Y=C mit X=s*C und Y=t*C. Jetzt kann man die Lösungsmenge noch für x>0 und y>0 einschränken:
x = X+k*B > 0 --> k > -X/B und y = Y-k*A > 0 --> k < Y/A. Hier wurde benutzt, dass sowohl A>0 als auch B>0 ist. Schon ist man fertig.