On the number of divisions of the Euclidean algorithm applied to Gaussian integers (Q1086616): Difference between revisions

The author considers a modification of the Euclidean algorithm for the ring of integers \(\mathbb Z[i]\) in the Gaussian number field \(\mathbb Q(i)\): at each step the condition that the norm of the remainder \(r\) in the division \(x=sy+r\) \((x,y,r,s\in\mathbb Z[i])\) should be minimal or less than that of \(y\) is dropped. The first result is: if at each step the Gaussian integer \(s\) is chosen in such a way that \(N(r)\) is minimal, then the total number of divisions until termination is minimal. The proof uses so-called divisor chains and is quite intricate. After that a minimal sequence of exact length \(n\) is constructed and finally an upper bound on the number of divisions in a minimal remainder version of the Euclidean algorithm is given in terms of an upper bound on the norm of the input \((u,v)\).