The Number of Steps in the Euclidean Algorithm
Academic Article

 Overview

 Identity

 Additional Document Info

 View All

Overview
abstract

When the Euclidean algorithm is run on a pair (a, b) of positive integers with a < b, the number of steps of the form (a, b) → (b mod a, a) required to extract the gcd is known to be typically close to (12 log 2/π2) log b. Here we sharpen earlier estimates of Dixon [J. Number Theory2 (1970), 414422] and Heilbronn ["Number Theory and Analysis (Papers in Honor of Edmund Landau)," pp. 8796] and show that among pairs (a, b) with 1 ≤ a ≤ b ≤ x as x → ∞, the number of such steps has an asymptotically normal distribution with mean close to (12 log 2/π2) log x and variance close to C1 log x, where C1 = π6(12 log 2/π2)3(d2/ds2) log λ(s)s = 2, with λ(s) denoting a certain pseudo zeta function associated with continued fractions. © 1994 Academic Press Inc.
author list (cited authors)
citation count
publication date
publisher
published in
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue