Lamé's theorem
id:
lam-s-theorem-278-4188321
title:
Lamé's theorem
text:
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 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.
brand slug:
wiki
category slug:
encyclopedia
description:
Theorem related to the Euclidean algorithm.
original url:
https://en.wikipedia.org/wiki/Lam%C3%A9%27s_theorem
date created:
date modified:
2023-10-31T18:23:10Z
main entity:
{"identifier":"Q10380294","url":"https://www.wikidata.org/entity/Q10380294"}
image:
fields total:
13
integrity:
14