Fibonacci et pgcd

[mathelot]

Salut,

il y a un prof qui nous avait parlé d'un truc sublime

Soit n,m deux entiers naturels

Avec l'algo d'Euclide, on calcule le pgcd(n,m)
C'est là qu'intervient la suite de Fibonacci.
Elle permet d'obtenir a-priori un majorant du nombre d'étapes de l'algorithme

Quelqu'un connait ?

[Le_chat]

J'ai eu ça en dm d'info l'année dernière je te dis si je le retrouve :we:

[mathelot]

J'ai eu ça en dm d'info l'année dernière je te dis si je le retrouve :we:

merci...........

[ft73]

c'est le théorème de Lamé, qui dit que le nombre d'itérations nécessaires à Euclide est où n est le plus grand des deux nombres.