Arithmétique dans K[X]

Soit \(f\) et \(g\) deux polynômes non nuls. L'algorithme d'Euclide permet de donner un procédé pratique pour trouver des polynômes \(U\) et \(V\) tels que : \(fU + gV = D\) où \(D\) est le PGCD de \(f\) et \(g\).

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 \(f\) et de \(g\), en explicitant à chaque étape les polynômes "coefficients" de \(f\) et de \(g\) mais en gardant \(f\) et de \(g\), sans les expliciter.

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

• \(f = gq_{1} + r_{1} \Longrightarrow r_{1} = f - q_{1}g\)

  Donc, on a \(r_{1}\) en faisant la somme du produit de \(f\) par \(1\) et de \(g\) par \(-q_{1}\).

• \(g = r_{1}q_{2} + r_{2} \Longrightarrow r_{2} = g - q_{2}r_{1}\)

  Donc, on a \(r_{2}\) en faisant la somme du produit de \(g\) par \(1\) et de \(r_{1}\) par \(-q_{2}\).

• \(r_{1} = r_{2} q_{3} + r_{3} \Longrightarrow r_{3} = r_{1} - q_{3} r_{2}\)

  Donc, on a \(r_{3}\) en faisant la somme du produit de \(r_{1}\) par \(1\) et de \(r_{2}\) par \(-q_{3}\).

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

• \(r_{n-2} = r_{n-1}q_{n} + r_{n} \Longrightarrow r_{n} = r_{n-2} - q_{n} r_{n-1}\)

  Donc, on a \(r_{n}\) en faisant la somme du produit de \(r_{n-2}\) par \(1\) et de \(r_{n-1}\) par \(-q_{n}\).

  \(r_{n-1} = r_{n}q_{n+1}\)

Alors, le PGCD de \(f\) et \(g\) est \(\frac{1}{\textrm{Dom} (r_{n})}~r_{n}\) où \(r_{n}\) est le dernier reste non nul de l'algorithme d'Euclide et \(\textrm{Dom}(r_{n})\) son coefficient dominant.

Donc, si on part des égalités \(\left| \begin{array}{l} f = 1 f + 0 g \\ g = 0 f + 1 g \end{array} \right.\) et si à chaque étape on effectue les calculs indiqués en "gardant" \(f\) et \(g\), on obtient \(r_{n}\) sous la forme \(r_{n} = fU + gV\).