Intorno all' algoritmo di Euclide. (Q1505126): Difference between revisions

Verf. behandelt die Aufgabe, bei gegebenen \(a_0,a_1\) \((a_0>a_1)\) a priori anzugeben, ob die Anzahl \(k\) der Quotienten beim \textit{Euklid}ischen Algorithmus \[ a_0=q_1a_1+ a_2,\dots a_{k-2} = q_{k-1}a_{k-1}+a_k, a_{k-1}=q_ka_k \] gerade oder ungerade ist. Sein Resultat lautet: Wenn \(a_0\) und \(a_1\) teilerfremd sind, ist \(k\) gerade oder ungerade, je nachdem die kleinste positive Wurzel \(y\) der Kongruenz \(a_0y \equiv 1\) (mod.\,\(a_1\)) kleiner oder größer als \(\frac 12 a_1\) ist. Hieraus folgt ein analoges Kriterium für den Fall, daß \(a_0\) und \(a_1\) einen gemeinsamen Teiler \(> 1\) besitzen.