Algorithme d'Euclide

Posté par jonjon71 jonjon71

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 Camélia Camélia

Bonjour

Une suite strictement décroissante prend forcément une infinité de valeurs. Rigoureusement: l'application est bijective donc l'ensemble est dénombrable comme N. Il ne peut être contenu dans une partie finie!

Posté par jonjon71 jonjon71

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 plumemeteore plumemeteore

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 Camélia Camélia

Bonjour 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 jonjon71 jonjon71

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.

Posté par Camélia Camélia

Oui, bien sur...