A note on the linear diophantine equation. (Q2579844)

Die Auflösung der linearen diophantischen Gleichung \(a_0 x - a_1y = 1\) mit Kettenbrüchen nach Lagrange geht bekanntlich so vor, daß \(a_0/a_1\) in einen Kettenbruch entwickelt wird; die Teilnenner des Kettenbruchs dienen zur Herstellung von zwei rücklaufenden (rekurrenten) Folgen, die die Zähler und die Nenner der Näherungsbrüche des Kettenbruchs liefern; Zähler und Nenner des vorletzten Näherungsbruchs (wobei \(a_0/a_1\) selbst als letzter gilt) sind, mit passenden Vorzeichen versehen, die Werte von \(y\) und \(x\). Verf. (nicht zu verwechseln mit D. N. Lehmer) macht darauf aufmerksam, daß man mit \textit{einer} rücklaufenden Folge ausreicht. Nimmt man nämlich die Teilnenner des Kettenbruchs in umgekehrter Reihenfolge, so hat der so entstehende Kettenbruch, wie bekannt, zum Wert den Quotienten der letzten beiden Näherungsnenner des ursprünglichen Kettenbruchs; daher sind umgekehrt seine letzten beiden Näherungsnenner \(a_1\) und \(a_0\). Folglich sind seine letzten beiden Näherungszähler, mit passenden Vorzeichen versehen, die Werte von \(x\) und \(y\). Es genügt also, die Folge dieser Näherungszähler aufzustellen. Eine Abkürzung des Verfahrens kann man ferner erreichen, indem man auch negative Teilquotienten zuläßt. -- Lineare diophantische. Gleichungen mit mehr als zwei Unbekannten können ebenfalls statt mit dem Jacobischen Algorithmus nach einem freieren Verfahren, bei dem auch eine der rücklaufenden Folgen erspart wird, behandelt werden. Es wird in einer bequem zusammenfassenden Form, die aber doch hier etwas zu viel Raum beanspruchen würde, beschrieben.