Far Eastern Mathematical Journal

To content of the issue

Reachability of inequalities from Lame's theorem

Kan I.D.

2024, issue 1, P. 45-54 DOI: https://doi.org/10.47910/FEMJ202405

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 $(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.

Keywords: Lame's theorem, Euclid's algorithm.

Download the article (PDF-file)

References

[1] Nesterenko Iu.V., Teoriia chisel, Izdatel'skii tsentr “Akademiia”, M., 2008. [2] Knut D.E., Iskusstvo programmirovaniia. T.2, Izdatel'stvo “Dialektika-Vil'iams”, 1998. [3] Vorob'ev N.N., Chisla Fibonachchi, Glavnaia redaktsiia fiziko-matematicheskoi literatury izdatel'stva “Nauka”, M., 1978. [4] Veil' G., “O ravnomernom raspredelenii chisel po moduliu”, Izbrannye trudy, Nauka, M., 1984, 58–93.

To content of the issue