Niveau concours

Algorithme d'Euclide

Posté par
jonjon71 14-03-10 à 22:09

Bonjour,

Ma question concerne l'algorithme d'Euclide qui permet de trouver le pgcd de 2 entiers. Je m'explique :

Soient a,b deux entiers avec b non nul. On a

      a = b*q + r avec r < b
      b = r*q₁ + r₁ avec r₁ < r
      r = r₁*q₂ + r₂ avec r₂ < r₁
      ...
      r_n-2 = r_n-1*q_n + r_n avec r_n < r_n-1
      r_n-1 = r_n*q_n+1

On a alors une suite (r_n) strictement décroissante d'entiers naturels donc il existe un n tel que r_n=0 et l'algorithme s'arrête.

Je voudrais avoir une justification rigoureuse de cela. Comment démontrer que la suite est nulle à partir d'un certain rang ?

J'ai pu lire des théorèmes du style :

* Toute suite strictement décroissante dans est stationnaire.

Mais pour moi une suite ne peut pas être à la fois strictement décroissante et stationnaire. Et comment justifier que la valeur finale est 0 ?

Ou encore :

* Il n'existe pas de suite strictement décroissante dans .

Mais là comment s'en sort t'on ?

Si vous utilisez l'un de ces théorèmes comment le démontrez-vous ?

Merci à toute contribution

Posté par re : Algorithme d'Euclide 14-03-10 à 22:51

Bonjour

Une suite strictement décroissante prend forcément une infinité de valeurs. Rigoureusement: l'application $f(n)=r_n$ est bijective donc l'ensemble ${r_n|n\in N}$ est dénombrable comme N. Il ne peut être contenu dans une partie finie!

Posté par re : Algorithme d'Euclide 15-03-10 à 22:03

Merci beaucoup Camélia.

Finalement j'ai réfléchi un petit peu et j'ai réussi à trouver une solution. Comme quoi dès fois on trouve plus facilement par soi-même qu'en regardant à droite ou à gauche !

Posté par re : Algorithme d'Euclide 17-03-10 à 09:18

Bonjour.
On dit le plus souvent que le pgcd est le dernier reste non nul dans l'algorithme d'Euclide. Ne serait-il pas plus naturel de dire que c'est le diviseur de la dernière division (donc celle qui n'a pas de reste) ?

Posté par re : Algorithme d'Euclide 17-03-10 à 14:22

Bonjour $plumemeteore$ Tu n'as pas tort... En fait la plupart du temps on s'arrête même avant, soit parce que le reste vaut 1, soit parce que c'est un nombre premier, et on ne se fatigue pas à écrire la dernière division!

Posté par re : Algorithme d'Euclide 17-03-10 à 15:53

Bonjour,

J'ai une nouvelle question :

Je cherche à démontrer assez simplement que le nombre d'itérations de divisions euclidiennes dans l'algorithme d'Euclide est maximal lorsqu'on prend 2 nombres consécutifs de la suite de Fibonacci.

On a u(n+2) = u(n+1) * 1 + u(n) avec u(n) < u(n+1) donc la formule de récurrence de la suite de Fibonacci donne bien la division euclidienne de deux termes conscutifs.

Suffit-il de dire que c'est parce que l'on obtient toujours des quotients égaux à 1 ?

Merci.