Note:
Introduction. Given a pair
(x, y) of positive real numbers, then one iteration of the Euclidean algorithm
replaces the larger number by its least non-negative residue modulo the smaller
number. If the two numbers are linearly dependent, the repetition of this
process will eventually terminate with a pair in which one of the elements is
zero. (If the original pair were integers, then the remaining non-zero element
is their greatest common divisor.)
Another property of the
Euclidean algorithm, fundamental to the study of continued fractions, is that it
produces increasingly good rational approximations to the original pair of real
numbers.
We will construct an
iterative algorithm for n-tuples, generalizing both the terminating and
approximating features of the Euclidean algorithm. Thus, if the original n-tuple
of elements are Z-linearly dependent, the algorithm will necessarily terminate
and discover the Z-relation among the elements of the original n-tuple. If the
original n-tuple elements are not Z-linearly dependent, then the algorithm will
"absolutely approximate" by producing lattice points arbitrarily close
to the line generated by the original n-tuple.
We emphasize that a major
difficulty in the problem of constructing a generalization of the Euclidean
algorithm is to give an iterative algorithm.
