Introduction : Une Généralisation Naturelle
L’algorithme d’Euclide est l’une des procédures les plus anciennes et les plus importantes en mathématiques. Conçu à l’origine pour trouver le plus grand commun diviseur (PGCD) de deux entiers, son génie réside dans sa simplicité et son efficacité. Ce même algorithme peut être transposé presque à l’identique à l’anneau des polynômes à coefficients dans un corps, $K[X]$.
Cette généralisation est possible parce que $K[X]$ est, comme $\mathbb{Z}$, un anneau euclidien. L’existence d’une division euclidienne pour les polynômes, où la « taille » est mesurée par le degré, permet d’appliquer la même suite de divisions itératives pour faire émerger le PGCD. Cet algorithme est un outil fondamental en algèbre, indispensable pour la simplification de fractions rationnelles, la résolution d’équations polynomiales et la théorie des codes.
L’algorithme repose sur une propriété simple mais essentielle de la division euclidienne. Si $A(X)$ et $B(X)$ sont deux polynômes, et que la division de $A$ par $B$ donne un reste $R(X)$ : $$ A(X) = B(X)Q(X) + R(X) $$ Alors, l’ensemble des diviseurs communs à $A$ et $B$ est exactement le même que l’ensemble des diviseurs communs à $B$ et $R$. Par conséquent : $$ \text{pgcd}(A, B) = \text{pgcd}(B, R) $$
En appliquant cette propriété de manière répétée, on réduit le degré des polynômes à chaque étape, jusqu’à tomber sur un reste nul. Le dernier reste non nul est alors le PGCD recherché.
Déroulement de l’Algorithme
Soient $A(X)$ et $B(X)$ deux polynômes de $K[X]$, avec $\deg(A) \ge \deg(B)$.
- On pose $R_0 = A$ et $R_1 = B$.
- On effectue la division euclidienne de $R_0$ par $R_1$ pour obtenir un reste $R_2$.
- On effectue la division euclidienne de $R_1$ par $R_2$ pour obtenir un reste $R_3$.
- On continue ainsi : on divise $R_k$ par $R_{k+1}$ pour obtenir un reste $R_{k+2}$.
- Le processus s’arrête lorsqu’on obtient un reste nul, disons $R_{n+1}=0$.
La suite des divisions s’écrit : $$ R_0 = R_1 Q_1 + R_2, \quad \deg(R_2) < \deg(R_1) $$ $$ R_1 = R_2 Q_2 + R_3, \quad \deg(R_3) < \deg(R_2) $$ $$ \vdots $$ $$ R_{n-1} = R_n Q_n + R_{n+1}, \quad R_{n+1}=0 $$ Le PGCD de $A$ et $B$ est le dernier reste non nul, $R_n$. On le normalise souvent en le divisant par son coefficient dominant pour obtenir le PGCD unitaire.
Exemple Détaillé dans $\mathbb{R}[X]$
Calculons le PGCD de $A(X) = X^4 + X^3 – 3X^2 – 4X – 1$ et $B(X) = X^3 + X^2 – X – 1$.
Étape 1 : Division de A par B
On effectue la division longue de $A(X)$ par $B(X)$. $$ X^4 + X^3 – 3X^2 – 4X – 1 = (X)(X^3 + X^2 – X – 1) + (-2X^2 – 3X – 1) $$ Le quotient est $Q_1(X) = X$ et le premier reste est $R_2(X) = -2X^2 – 3X – 1$.
Étape 2 : Division de B par $R_2$
On divise maintenant $B(X) = X^3 + X^2 – X – 1$ par $R_2(X) = -2X^2 – 3X – 1$. $$ X^3 + X^2 – X – 1 = (-\frac{1}{2}X + \frac{1}{4})(-2X^2 – 3X – 1) + (-\frac{3}{4}X – \frac{3}{4}) $$ Le quotient est $Q_2(X) = -\frac{1}{2}X + \frac{1}{4}$ et le reste est $R_3(X) = -\frac{3}{4}X – \frac{3}{4}$.
Étape 3 : Division de $R_2$ par $R_3$
On divise $R_2(X) = -2X^2 – 3X – 1$ par $R_3(X) = -\frac{3}{4}X – \frac{3}{4}$. $$ -2X^2 – 3X – 1 = (\frac{8}{3}X + \frac{4}{3})(-\frac{3}{4}X – \frac{3}{4}) + 0 $$ Le reste est nul.
Conclusion
Le dernier reste non nul est $R_3(X) = -\frac{3}{4}X – \frac{3}{4}$. C’est le PGCD.
Pour obtenir le PGCD unitaire, on divise ce polynôme par son coefficient dominant, $-\frac{3}{4}$ :
$$ \text{PGCD unitaire} = \frac{-\frac{3}{4}X – \frac{3}{4}}{-\frac{3}{4}} = X+1 $$
Le PGCD de $X^4 + X^3 – 3X^2 – 4X – 1$ et $X^3 + X^2 – X – 1$ est donc $X+1$.