On the number of divisions of the Euclidean algorithm applied to Gaussian integers
type: Item
instance of: scholarly article
title: On the number of divisions of the Euclidean algorithm applied to Gaussian integers
zbMATH Open document ID: 0609.12001
DOI: 10.1016/S0747-7171(86)80027-X
author: Heinrich Rolletschek
published in: Journal of Symbolic Computation
publication date: 1986-01-01T00:00:00Z
review text: 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)\).
Mathematics Subject Classification ID: 11R04
Mathematics Subject Classification ID: 11A05
Mathematics Subject Classification ID: 11R11
zbMATH DE Number: 3985348
zbMATH Keywords: Euclidean algorithm
zbMATH Keywords: Gaussian number field
zbMATH Keywords: Gaussian integer
zbMATH Keywords: divisor chains
reviewed by: Marcel G. de Bruin
MaRDI profile type: Publication
cites work: The inhomogeneous minima of binary quadratic forms. I
cites work: Q3916662
cites work: Euclid's Algorithm in real Quadratic Fields
cites work: A weakening of the euclidean property for integral domains and applications to algebraic number theory. I.
cites work: Q3259107
cites work: Q3728091
cites work: Q5585020
cites work: Q4108436
cites work: Q3322188
cites work: Fast computation of continued fraction expansions.
Recommended article: Q3322188
Recommended article: On the set of divisors of Gaussian integers
Recommended article: A fast Euclidean algorithm for Gaussian integers
Recommended article: Divisor problem in special sets of Gaussian integers
Recommended article: The divisibility of Gaussian integers by large Gaussian primes
Recommended article: Divisors of the Gaussian integers in an arithmetic progression
Recommended article: Q3315598
Recommended article: On the distribution of the greatest common divisor of Gaussian integers
Recommended article: Q3754698
Recommended article: A Paper-and-Pencil gcd Algorithm for Gaussian Integers
description: scientific article; zbMATH DE number 3985348