Shortest division chains in unique factorization domains

摘要

We investigate the problem on the validity of the Lazard theorem analogue (or the Kronecker-Vahlen theorem), which states that the least remainder Euclidean Algorithm (EA) has the shortest length over any other versions of EA, in unique factorization domains. There is obtained the existence criterion to represent a fixed element of the fractions field of a unique factorization domain in the form of a continued fraction of a fixed length. This criterion enables to obtain a formula for the length of the least remainder (on norm) EA as a function of elements, with respect to which EA is applied. This result gives us the class T of unique factorization domains, for which the Lazard theorem analogue is valid. We propose algorithms to check whether the given unique factorization domain belongs to the class T. We find the necessary and sufficient conditions under which the number of steps in the worst case of the least remainder EA grows not faster than logarithm. In particular, these results hold for the least remainder EA in any Euclidean quadratic domain. We provide counterexamples, which show the essentiality of the conditions in the obtained theorems. (C) 2016 Elsevier Ltd. All rights reserved.