Algorithme d'Euclide
Rappelons tout d'abord qu'un algorithme est une suite finie de règles à appliquer dans un ordre déterminé à un nombre fini de données pour arriver avec certitude (i.e sans indétermination ou ambiguïté) en un nombre fini d'étapes à un certain résultat et cela indépendamment des données : il résout donc une classe de problèmes ne différant que par les données mais gouvernés par les mêmes prescriptions.
L'algorithme d'Euclide permet de déterminer le PGCD de deux polynômes.
La méthode est basée sur le théorème suivant :
Théorème : Moteur de l'algorithme d'Euclide
Soient \(P_1\) et \(P_2\) deux polynômes non nuls et \(R\) le reste de la division euclidienne de \(P_1\) par \(P_2\). Alors :
Si \(R = 0\), \(P_2\) divise \(P_1\) et le PGCD de \(P_1\) et \(P_2\) est \(a^{-1} P_2\) où \(a\) est le coefficient dominant de \(P_2\).
Si \(R \neq 0\), les diviseurs communs à \(P_1\) et \(P_2\) sont les diviseurs communs à \(P_2\) et \(R\).
Donc, si le reste \(R\) de la division euclidienne de \(P_1\) par \(P_2\) est non nul, le PGCD de \(P_1\) et \(P_2\) est égal au PGCD de \(P_2\) et de \(R\).
Cela résulte immédiatement de la relation \(P_1 = P_2 Q + R\).
Cela conduit à l'algorithme d'Euclide.
Description de l'algorithme :
Soient \(f\) et \(g\) deux polynômes non nuls ; supposons par exemple que \(\textrm{deg}(f) \geq \textrm{deg}(g)\).
On effectue la division euclidienne de \(f\) par \(g\) :
\(f = gq_{1} + r_{1}\) avec \(r_{1} = 0\) ou \(\textrm{deg}(r_{1}) < \textrm{deg}(g)\). Alors
si \(r_{1} = 0\), c'est terminé, d'après le point \(1.\) du lemme,
si \(r_{1} \neq 0\), le point \(2.\) du lemme montre que le PGCD de \(f\) et \(g\) est égal au PGCD de \(g\) et \(r_{1}\) avec \(\textrm{deg}(r_{1}) < \textrm{deg}(g)\).
On répète cette opération et puisque le degré du reste décroît d'au moins une unité à chaque division euclidienne effectuée, on aboutit au bout de n divisions au plus (où \(n = \textrm{deg}(g)\)) à un reste nul.
Alors le dernier reste non nul est (à un facteur constant non nul multiplicatif près) le PGCD cherché (si c'est une constante, les polynômes sont premiers entre eux).
Remarque :
Il est plus simple, du point de vue des calculs, de diviser par un polynôme unitaire.
De plus on sait que, si au moins un des deux polynômes \(P\) ou \(Q\) est non nul, et si \(\lambda\) est une constante non nulle, on a l'égalité : \(\textrm{PGCD}~(\lambda P, Q) = \textrm{PGCD}~(P, Q)\).
On peut donc, dans la pratique, remplacer la division du reste \(r_{k-1}\) par \(r_{k}\) par la division de \(r_{k-1}\) par \(\frac{1}{\textrm{Dom}~(r_{k})} r_{k}\), où \(\textrm{Dom}(r_k)\) est le coefficient dominant de \(r_k\); le polynôme \(\frac{1}{\textrm{Dom}(r_{k})} r_{k}\) est un polynôme unitaire. Cela ne changera rien pour la détermination du PGCD cherché.
Présentation algorithmique
Entrer \(f\) et \(g\),
Initialiser \(f = r_{-1}\), \(g = r_{0}\),
Tant que \(r_{0} \neq 0\)
Trouver le reste \(r_{1}\) de la division euclidienne de \(r_{-1}\) par \(r_{0}\) :
\(r_{-1} \leftarrow r_{0}\) ;
\(r_{0} \leftarrow r_{1}\) :
Fin
Le résultat dans \(r_{-1}\).
Exemple :
\(f(X) = X^{3} - 2\) ; \(g(X) = 2 X^{2} - 3\)
En effectuant les différentes divisions indiquées, on trouve :
\(X^{3} - 2 = (2 X^{3} - 3)(1 / 2)X + \color{green} (3/2)X - 2 \\ \color{black}2X^{3} - 3 = \left[\color{green}(3/2)X - 2 \color{black}\right] \left[(4/3)X + (16/9) \right] + \color{red} 5/9 \\ \color{black} (3/2)X - 2 = (\color{red}5/9\color{black}) \left[ (27/10) X - (18/5)\right]\)
Le dernier reste non nul est le polynôme constant (5/9).
Le PGCD de \(f\) et \(g\) est donc 1.
Présentation algorithmique :
Itération | \(r_{1}\) | \(r_{0}\) |
0 | \(X^{3}-2\) | \(2X^{2}-3\) |
1 | \(2X^{2}-3\) | \((3/2)X - 2\) |
2 | \((3/2) X - 2\) | \((5/9)\) |
\((5/9)\) | \(0\) |