Travaux pratiques
Comme Q[a] Q[x]/(P ) est un corps, a −1 s’exprime également comme un polynôme en a (de degré au plus 4). Tester evala(subs(x=a,R)); et vérifier que
le polynôme obtenu est l’inverse de x modulo P (plus exactement l’inverse de
la classe de x dans Q[x]/(P )). Maple a donc appliqué l’algorithme d’Euclide
(semi-)étendu (commande gcdex) pour calculer le coefficient souhaité d’une
relation de Bezout xu(x) + P (x)v(x) = 1. Tout élément non nul de Q[a] est
inversible : le polynôme (en a) correspondant est premier avec P , donc on peut
écrire l’identité de Bezout. Calculer R(a) −1 .
Remarque. L’idée de l’algorithme euclidien est que si a = bq + r (où b = 0) alors
ou bien r = 0 auquel cas le pgcd est b, ou bien pgcd(a, b) = pgcd(b, r) à une unité
près. En effet, si d divise a et b, alors il divise r = a − bq (et b) ; réciproquement,
s’il divise b et r, il divise a = bq +r (et b). Ainsi le pgcd est le dernier reste non nul.
Finalement, l’algorithme d’Euclide est le suivant : à partir de a 0 = a et b 0 = b,
on effectue les divisions euclidiennes a n = b n q n + r n puis l’on définit a n+1 = b n et
b n+1 = r n tant que r n = 0.
Pour l’algorithme étendu, on cherche à construire deux suites u n et v n telles
que r n = au n + bv n pour tout n, jusqu’au dernier reste non nul où l’on obtient les
coefficients de Bezout. On utilise le fait que a n = r n−2 et b n = r n−1 : on effectue
alors la division euclidienne r n−2 = r n−1 q n + r n et l’on définit u n = u n−2 − u n−1 q n
et v n = v n−2 − v n−1 q n . Pour initialiser, on part de r −2 = a = a.1 + b.0 et
r −1 = b = a.0 + b.1.
La problématique qui nous concerne maintenant est la suivante : soit a une
racine (dans C) d’un polynôme irréductible P de Q[x]. Cela définit une extension
L = Q(a) de Q. Le polynôme minimal de a est P , à une constante près, et la
structure algébrique de Q(a) est définie par l’isomorphisme Q(a) Q[x]/(P ). En
particulier, cela ne dépend pas de la racine complexe choisie ; en notation Maple,
a:=RootOf(P,x) n’en dit pas plus : on travaille dans Q[x]/(P ).
Un autre élément b de Q(a) s’exprime comme un polynôme b = R(a) en a. Il
s’agit de calculer son polynôme minimal sur Q, en fonction de R et P . L’ingrédient
essentiel est le résultant.
La théorie du résultant
Soit A un anneau intègre. Pour tout entier n, on note A[x] n le A-module des
polynômes de degré strictement plus petit que n. C’est donc un A-module libre
de rang n.
291
Comme Q[a] Q[x]/(P ) est un corps, a −1 s’exprime également comme un polynôme en a (de degré au plus 4). Tester evala(subs(x=a,R)); et vérifier que
le polynôme obtenu est l’inverse de x modulo P (plus exactement l’inverse de
la classe de x dans Q[x]/(P )). Maple a donc appliqué l’algorithme d’Euclide
(semi-)étendu (commande gcdex) pour calculer le coefficient souhaité d’une
relation de Bezout xu(x) + P (x)v(x) = 1. Tout élément non nul de Q[a] est
inversible : le polynôme (en a) correspondant est premier avec P , donc on peut
écrire l’identité de Bezout. Calculer R(a) −1 .
Remarque. L’idée de l’algorithme euclidien est que si a = bq + r (où b = 0) alors
ou bien r = 0 auquel cas le pgcd est b, ou bien pgcd(a, b) = pgcd(b, r) à une unité
près. En effet, si d divise a et b, alors il divise r = a − bq (et b) ; réciproquement,
s’il divise b et r, il divise a = bq +r (et b). Ainsi le pgcd est le dernier reste non nul.
Finalement, l’algorithme d’Euclide est le suivant : à partir de a 0 = a et b 0 = b,
on effectue les divisions euclidiennes a n = b n q n + r n puis l’on définit a n+1 = b n et
b n+1 = r n tant que r n = 0.
Pour l’algorithme étendu, on cherche à construire deux suites u n et v n telles
que r n = au n + bv n pour tout n, jusqu’au dernier reste non nul où l’on obtient les
coefficients de Bezout. On utilise le fait que a n = r n−2 et b n = r n−1 : on effectue
alors la division euclidienne r n−2 = r n−1 q n + r n et l’on définit u n = u n−2 − u n−1 q n
et v n = v n−2 − v n−1 q n . Pour initialiser, on part de r −2 = a = a.1 + b.0 et
r −1 = b = a.0 + b.1.
La problématique qui nous concerne maintenant est la suivante : soit a une
racine (dans C) d’un polynôme irréductible P de Q[x]. Cela définit une extension
L = Q(a) de Q. Le polynôme minimal de a est P , à une constante près, et la
structure algébrique de Q(a) est définie par l’isomorphisme Q(a) Q[x]/(P ). En
particulier, cela ne dépend pas de la racine complexe choisie ; en notation Maple,
a:=RootOf(P,x) n’en dit pas plus : on travaille dans Q[x]/(P ).
Un autre élément b de Q(a) s’exprime comme un polynôme b = R(a) en a. Il
s’agit de calculer son polynôme minimal sur Q, en fonction de R et P . L’ingrédient
essentiel est le résultant.
La théorie du résultant
Soit A un anneau intègre. Pour tout entier n, on note A[x] n le A-module des
polynômes de degré strictement plus petit que n. C’est donc un A-module libre
de rang n.
291