Travaux pratiques
pgcd(f, g) est non constant. En prenant f = P et g = P , on voit que, si
p ne divise pas le coefficient dominant de P , alors P est sans facteur carré
si et seulement p ne divise pas le résultant de P et P . En particulier, il n’y
a qu’un nombre fini de mauvais p. Par définition, le discriminant de f est
D(f ) =
(−1)
n−1
2 Res(f,f )
a
, où a désigne le coefficient dominant de f . On l’obtient
avec la commande Maple discrim(f,x). La définition du résultant montre
que a 2n−2 divise D(f ), donc a fortiori a. En définitive, si p ne divise pas D(P )
alors P est sans facteur carré. Tester en prenant P = x 9 +x 6 +x 5 −2x 4 −2x−2.
Remarque. Si p ne divise pas le coefficient dominant de f et g, on peut montrer
que pgcd(f , g) = cpgcd(f, g), où c est le coefficient dominant de pgcd(f, g)
calculé dans Z[x] (voir [28], chapitre 6.4).
9. Avant de poursuivre avec la description de l’algorithme à proprement parlé,
faisons une petite digression au sujet des tests modulaires d’irréductibilité :
il s’agit d’exploiter au maximum les factorisations de P modulo différents
nombres premiers (puisque nous savons déjà tester l’irréductibilité et factoriser
sur F p ).
On se donne la liste
L = (x 7 + 2x 5 + 1, x 8 + 2x 5 + 1, x 9 + x 4 + x 3 + 5x 2 + 11, x 4 + 3x 2 + 7x + 4,
x 6 + 2x 3 + 4x 2 + 15, x 7 + x + 1).
– Appliquer le critère par réduction du TR.VIII.B : pour quels polynômes
de la liste L peut-on conclure à l’aide des premiers p inférieur à 20 (obtenus par exemple via select(isprime([$1..20])) ? On écrira une procédure test1:=proc(f) que l’on appliquera aux éléments de la liste.
– Écrire une procédure test2:=proc(f) renvoyant la liste des degrés des
facteurs dans la décomposition en irréductibles sur F p , pour les différents p premiers inférieurs à 20 tels que cette décomposition soit sans
facteur carré (et que p ne divise pas le coefficient dominant de P ). Peuton conclure, à l’aide de ces renseignements, pour tous les cas non tranchés
par le test précédent ?
– Proposer un argument pour le cas restant.
La factorisation des polynômes sur Q[x] est possible par des méthodes modulaires grâce au théorème suivant (consulter [20] pour une preuve) :
Théorème 1. Soit P = QR avec P =
i a i x i , Q =
i b i x i et R des polynômes
de Z[x]. On note d le degré de Q et P la norme euclidienne de P , c’est-àdire P = (
i |a i | 2 ) 1/2 . Alors |b i |
d
i
P .
257
pgcd(f, g) est non constant. En prenant f = P et g = P , on voit que, si
p ne divise pas le coefficient dominant de P , alors P est sans facteur carré
si et seulement p ne divise pas le résultant de P et P . En particulier, il n’y
a qu’un nombre fini de mauvais p. Par définition, le discriminant de f est
D(f ) =
(−1)
n−1
2 Res(f,f )
a
, où a désigne le coefficient dominant de f . On l’obtient
avec la commande Maple discrim(f,x). La définition du résultant montre
que a 2n−2 divise D(f ), donc a fortiori a. En définitive, si p ne divise pas D(P )
alors P est sans facteur carré. Tester en prenant P = x 9 +x 6 +x 5 −2x 4 −2x−2.
Remarque. Si p ne divise pas le coefficient dominant de f et g, on peut montrer
que pgcd(f , g) = cpgcd(f, g), où c est le coefficient dominant de pgcd(f, g)
calculé dans Z[x] (voir [28], chapitre 6.4).
9. Avant de poursuivre avec la description de l’algorithme à proprement parlé,
faisons une petite digression au sujet des tests modulaires d’irréductibilité :
il s’agit d’exploiter au maximum les factorisations de P modulo différents
nombres premiers (puisque nous savons déjà tester l’irréductibilité et factoriser
sur F p ).
On se donne la liste
L = (x 7 + 2x 5 + 1, x 8 + 2x 5 + 1, x 9 + x 4 + x 3 + 5x 2 + 11, x 4 + 3x 2 + 7x + 4,
x 6 + 2x 3 + 4x 2 + 15, x 7 + x + 1).
– Appliquer le critère par réduction du TR.VIII.B : pour quels polynômes
de la liste L peut-on conclure à l’aide des premiers p inférieur à 20 (obtenus par exemple via select(isprime([$1..20])) ? On écrira une procédure test1:=proc(f) que l’on appliquera aux éléments de la liste.
– Écrire une procédure test2:=proc(f) renvoyant la liste des degrés des
facteurs dans la décomposition en irréductibles sur F p , pour les différents p premiers inférieurs à 20 tels que cette décomposition soit sans
facteur carré (et que p ne divise pas le coefficient dominant de P ). Peuton conclure, à l’aide de ces renseignements, pour tous les cas non tranchés
par le test précédent ?
– Proposer un argument pour le cas restant.
La factorisation des polynômes sur Q[x] est possible par des méthodes modulaires grâce au théorème suivant (consulter [20] pour une preuve) :
Théorème 1. Soit P = QR avec P =
i a i x i , Q =
i b i x i et R des polynômes
de Z[x]. On note d le degré de Q et P la norme euclidienne de P , c’est-àdire P = (
i |a i | 2 ) 1/2 . Alors |b i |
d
i
P .
257