Lamé's theorem
Theorem related to the Euclidean algorithm. / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Lamé’s Theorem?
Summarize this article for a 10 year old
SHOW ALL QUESTIONS
Lamé's Theorem is the result of Gabriel Lamé's analysis of the complexity of the 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]