Algorithme de détermination des polynômes U et V

Soit et deux polynômes non nuls. L'algorithme d'Euclide permet de donner un procédé pratique pour trouver des polynômes et tels que : est le PGCD de et .

Il existe de nombreuses façons de représenter de manière algorithmique la démarche effectuée.

Nous en avons choisi une qui suit naturellement le déroulement de l'algorithme d'Euclide.

Le principe est d'exprimer à chaque étape de l'algorithme d'Euclide les restes successifs en fonction de et de , en explicitant à chaque étape les polynômes "coefficients" de et de mais en gardant et de , sans les expliciter.

Rappel de l'algorithme d'Euclide et expression du reste à chaque étape :

  • Donc, on a en faisant la somme du produit de par et de par .

  • Donc, on a en faisant la somme du produit de par et de par .

  • Donc, on a en faisant la somme du produit de par et de par .

.................................................................

  • Donc, on a en faisant la somme du produit de par et de par .

Alors, le PGCD de et est est le dernier reste non nul de l'algorithme d'Euclide et son coefficient dominant.

Donc, si on part des égalités et si à chaque étape on effectue les calculs indiqués en "gardant" et , on obtient sous la forme .

Remarque

Si l'on veut déterminer et par ce procédé, il faut faire toutes les divisions comme elles se présentent, même si l'on est amené à diviser par des polynômes non unitaires (voir la remarque à la fin de la description de l'algorithme d'Euclide).

On peut aussi présenter le calcul de la façon suivante :

s'écrit sous la forme

s'écrit sous la forme

s'écrit sous la forme

A partir de la troisième ligne, le calcul d'une ligne utilise les résultats des deux lignes précédentes : on multiplie par , par l'opposé du dernier quotient.

La somme s'écrit alors sous la forme et donne le reste correspondant.

Dans ce calcul, on explicite, à chaque étape, et comme des polynômes en , mais surtout pas et .

Par exemple, , avec et .

Et l'on continue ainsi jusqu'à .

Légende :
Apprendre
S'évaluer
S'exercer
Observer
Simuler
Réalisé avec Scenari (nouvelle fenêtre)