Le plus d'étapes avec l'algoritme d'Euclide

superfly

Titre initial : Calculs le plus long possible avec l'algoritme d'Euclide

Bonjour à tous,

Voici une question qu'un collègue m'a posé.
Étant donné deux nombres (disons inférieur à 10000).
Si on veut calculer le pgcd de ces deux nombres, il peut y avoir une ou plusieurs étapes.
On se posait la question quel est le nombre d'étapes maximum qu'il peut y avoir.
En calculant le pgcd de 6765 et 4181 on trouve je crois 18 étapes.
Peut-on faire mieux ?
Quel est le lien entre les nombres et le nombre d'étapes ?

Merci de vos réponses.

nicolas.patrois

Le cas le plus pénible est quand tu choisis deux nombres de la suite de Fibonacci.

Eric

Et ça doit s'appeler le théorème de Lamé.

Guego

On peut même rajouter "successifs".

Remarque : 4181 et 6765 sont deux nombres de Fibonacci successifs et ce sont les plus grands inférieurs à 10 000, donc c'est effectivement le couple qui va donner la plus longue suite.

Gilles old

Tiens, je ne m'étais jamais posé la question !

Un problème guidant la preuve dudit théorème : http://www.maths.univ-bpclermont.fr/irem/ressources/lycee/arithmetique/pdf/lame.pdf

superfly

Merci de toutes ces réponses !