RUS  ENG
Full version
JOURNALS // Dal'nevostochnyi Matematicheskii Zhurnal // Archive

Dal'nevost. Mat. Zh., 2024 Volume 24, Number 1, Pages 45–54 (Mi dvmg530)

Reachability of inequalities from Lame's theorem

I. D. Kan

Moscow Aviation Institute (National Research University)

Abstract: In this paper, the following result is proved. The number of steps in Euclid's algorithm for two natural arguments, the smaller of which has $v$ digital digits in the decimal system, does not exceed the integer part of the fraction \linebreak $(v+ \lg ({\sqrt{5}}/ {\Phi}))/ \lg \Phi$, where $\Phi=(1+\sqrt{5})/2$, and this estimate is achieved for every natural $v$. It is also proved that partial or asymptotic reachability is valid for the other two known upper bounds on the length of the Euclid algorithm.

Key words: Lame's theorem, Euclid's algorithm.

UDC: 511.321+511.31

MSC: 11B39

Received: 05.11.2023
Accepted: 24.05.2024

DOI: 10.47910/FEMJ202405



© Steklov Math. Inst. of RAS, 2024