Lamé's theorem

Lamé's Theorem is the result of Gabriel Lamé's analysis of the complexity of Euclidean algorithm. Using Fibonacci numbers, he proved in 1844[1][2] that when looking for the greatest common divisor (GCD) of two integers a and b, the algorithm finishes in at most 5k steps, where k is the number of digits (decimal) of b.[3][4]

Statement

The number of division steps in Euclid's algorithm with entries and is less than times the number of decimal digits of .

Proof

Let be two positive integers. Applying to them the Euclidean algorithm provides two sequences and of positive integers such that, setting and one has

for and

The number n is called the number of steps of the Euclidean algorithm, since it is the number of Euclidean divisions that are performed.

The Fibonacci numbers are defined by and

for

The above relations show that and By induction,

So, if the Euclidean algorithm requires n steps, one has

One has for every integer , where is the Golden ratio. This can be proved by induction, starting with and continuing by using that

So, if n is the number of steps of the Euclidean algorithm, one has

and thus

using

If k is the number of decimal digits of , one has and So,

and, as both members of the inequality are integers,

which is exactly what Lamé's theorem asserts.

As a side result of this proof, one gets that the pairs of integers that give the maximum number of steps of the Euclidean algorithm (for a given size of ) are the pairs of consecutive Fibonacci numbers.

See also

References

  1. Lamé, Gabriel (1844). "Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers". Comptes rendus des séances de l'Académie des Sciences (in French). 19: 867–870.
  2. Shallit, Jeffrey (1994-11-01). "Origins of the analysis of the Euclidean algorithm". Historia Mathematica. 21 (4): 401–419. doi:10.1006/hmat.1994.1031. ISSN 0315-0860.
  3. Weisstein, Eric W. "Lamé's Theorem". mathworld.wolfram.com. Retrieved 2023-05-09.
  4. "Lame's Theorem - First Application of Fibonacci Numbers". www.cut-the-knot.org. Retrieved 2023-05-09.

Bibliography

  • Bach, Eric (1996). Algorithmic number theory. Jeffrey Outlaw Shallit. Cambridge, Mass.: MIT Press. ISBN 0-262-02405-5. OCLC 33164327
  • Carvalho, João Bosco Pitombeira de (1993). Olhando mais de cima: Euclides, Fibonacci e Lamé. Revista do Professor de Matemática, São Paulo, n. 24, p. 32-40, 2 sem.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.