Exemple

Exemple

Soient les polynômes de \(\textrm{R} [X]\) : \(f(X) = X^{4} + 2 X^{3} + X + 1\) et \(g(X) = X^{3} + X - 1\).

On va chercher leur PGCD avec l'algorithme d'Euclide et des polynômes \(U\) et \(V\)tels que \(fU + gV = \textrm{PGCD} (f, g)\).

Le calcul se décompose en deux points.

Premier point : Recherche du PGCD par l'algorithme d'Euclide

Première étape

\(\begin{array}{l|l}\begin{array}{rrrrr}X^{4} & + 2 X^{3} & & +X & + 1\\-X^{4} & & -X^{2} & +X & \\\hline& 2X^{3} & -X^{2} & +2X & +1 \\& -2X^{3} & & -2X & +2 \\\hline& & -X^{2} & +3 &\end{array}&\begin{array}{rrr}X^{3} & +X & -1 \\\hline& X & + 2\\ \\\\ \\\end{array}\end{array}\)

Et donc, \(f=gq_{1} + r_{1}\) avec \(q_{1}(X) = X+2\) et \(r_{1}(X) = -X^{2}+3\).

Deuxième étape

\(\begin{array}{l|l}\begin{array}{rrrr}X^{3} & & +X & -1\\-X^{3} & & 3X & \\\hline& & +4X & -1\end{array}&\begin{array}{rr}-X^{2} && +3 \\\hline& -X & \\ \\\end{array}\end{array}\)

Et donc, \(g = q_{2} r_{1} + r_{2}\) avec \(q_{2} (X) = -X\) et \(r_{2} (X) = 4X - 1\).

Troisième étape

\(\begin{array}{l|l}\begin{array}{rrr}-X^{2} & & + 3 \\+X^{2} & -\frac{1}{4}X & \\\hline& -\frac{1}{4}X & +3 \\& \frac{1}{4}X & -\frac{1}{16}\\\hline& & \frac{47}{16}\end{array}&\begin{array}{rr}4X & -1 \\\hline-\frac{1}{4}X & - \frac{1}{16} \\ \\\\\\\\\end{array}\end{array}\)

Et donc \(r_{1} = q_{3}r_{2} + r_{3}\) avec \(q_{3}(X) = - \frac{1}{4} X - \frac{1}{16}\) et \(r_{3}(X) = \frac{47}{16}\).

Le reste étant constant, l'algorithme est terminé. Le dernier reste non nul est constant, les polynômes \(f\) et \(g\) sont donc premiers entre eux.

Deuxième point : Algorithme de détermination de U et V

On a donc :

\(f=gq_{1} + r_{1}\) avec \(q_{1}(X) = X+2\) et \(r_{1}(X) = -X^{2}+3\),

\(g = q_{2} r_{1} + r_{2}\) avec \(q_{2} (X) = -X\) et \(r_{2} (X) = 4X - 1\),

\(r_{1} = q_{3}r_{2} + r_{3}\) avec \(q_{3}(X) = - \frac{1}{4} X - \frac{1}{16}\) et \(r_{3}(X) = \frac{47}{16}\).

\(\textcolor{red}{\textrm{x}1}\)

\(f = 1f + 0g\)

\(\textcolor{blue}{\textrm{x}1}\)

\(\textcolor{red}{\textrm{x}(-q_{1})}\)

\(g = 0f + 1g\)

\(\textcolor{magenta}{\textrm{x}1}\)

\(\textcolor{blue}{\textrm{x}(-q_{2})}\)

\(\textcolor{red}{r_{1}(X) = f(X) - (X+2)g(X)}\)

Détails du calcul de \(r_1\)

On a \(q_1(X) = X+2\). L'expression de \(r_1\) est alors évidente.

\(\textcolor{magenta}{\textrm{x}(-q_{3})}\)

\(\textcolor{blue}{r_{2}(X) = X f(X) + ( - X^{2} - 2X + 1) g(X)}\)

Détails du calcul de \(r_2\)

On a \(q_2(X) = -X\). Donc,

\(\begin{array}{l l l} r_{2}(X) & = & g(X) - ( - X) \left[ f(X) - (X+2) g(X) \right] \\ & = & X f(X) + \left[ 1 + (-X)(X+2) \right] g(X) \\ & = & X f(X) + (-X^{2} - 2X + 1) g(X) \end{array}\)

\(\textcolor{magenta}{r_{3} = \left( \frac{1}{4}~X^{2} + \frac{1}{16}~X + 1\right) f(X) + \left( - \frac{1}{4}~X^{3} - \frac{9}{16}~X^{2} - \frac{7}{8}~X - \frac{31}{16} \right)~g(X)}\)

Détails du calcul de \(r_3\)

On a \(q_{3}(X) = - \frac{1}{4}~X - \frac{1}{16}\). Donc,

\(\begin{array}{l l l} r_3(X) & = & \left[ f(X) - (X + 2) g(X)\right] - \left( - \frac{1}{4} X - \frac{1}{16}\right) \left[X f(X) + (-X^{2} - 2X +1) g(X) \right] \\ & = & \left[ 1 + \left( \frac{1}{4}~X + \frac{1}{16}\right)~X \right]~f(X) + \left[ \left( - \frac{1}{4}~X - \frac{1}{16}\right) \left( -X^{2} - 2X + 1 \right) \right]~g(X) \\ & = & \left( \frac{1}{4}~X^{2} + \frac{1}{16}~X + 1 \right)~f(X) + \left(-\frac{1}{4}~X^{3} - \frac{9}{16}~X^{2} - \frac{7}{8}~X - \frac{31}{16}\right)~g(X) \end{array}\)

On a donc \(\frac{47}{16} = \left( \frac{1}{4}~X^{2} + \frac{1}{16}~X + 1\right) f(X) + \left( - \frac{1}{4}~X^{3} - \frac{9}{16}~X^{2} - \frac{7}{8}~X - \frac{31}{16} \right) g(X)\),

ce qui peut s'écrire :

\(1 = \frac{16}{47} \left[ \frac{1}{4}~X^{2} + \frac{1}{16}~X + 1 \right] f(X) + \frac{16}{47} \left[ \left( - \frac{1}{4}~X^{3} - \frac{9}{16}~X^{2} - \frac{7}{8}~X - \frac{31}{16} \right) \right] g(X)\)

On a donc bien trouvé deux polynômes \(U\) et \(V\) tels que \(1 = Uf + Vg\), à savoir : \(U = \frac{4}{47}~X^{2} + \frac{1}{47}~X + \frac{16}{47}\) et \(V = -\frac{4}{47}~X^{3} - \frac{9}{47}~X^{2}- \frac{14}{47}~X - \frac{31}{47}\)