Algèbre T1
7. La situation est plus simple qu’en caractéristique p : sur l’exemple
f = x
12 + x
11
− x
9
− 2x
8 + x
5 + x
4
calculer u = f / pgcd(f, f ), factoriser en irréductibles f /u, puis recommencer
en remplaçant f par u, etc. Observer les facteurs des quotients f /u successifs
et en déduire un algorithme donnant la décomposition sans facteur carré. L’implémenter au sein d’une procédure Sans2Fact0:=proc(f), tester et comparer
avec la commande sqrfree de Maple.
Remarque. En fait, la commande sqrfree renvoie la décomposition sans facteur
carré de P dans Z[x], i.e. l’écriture P = λh 1
1 h 2
2 . . . h s
s où λ ∈ Z et les h i ∈ Z[x]
sont primitifs sans facteur carré et premiers deux à deux. La décomposition
en irréductibles dans Z[x] (cf. chapitre VIII) assure l’existence et l’unicité de
cette décomposition.
8. Nous allons réduire P modulo un nombre premier p. Pour appliquer l’algorithme de Berlekamp, il faut s’assurer que la réduction P est sans facteur
carré. Le but de cette question est d’expliquer quels nombres p conviennent,
c’est-à-dire comment choisir p sans avoir à calculer pgcd(P , P
) et recommencer avec un nouveau p si l’on ne trouve pas un polynôme constant.
Calculer gcd(2*x,2); gcd(-2*x,2); gcd(x/2,1/2); Gcd(2*x,2) mod 3;
Quelle normalisation du pgcd Maple utilise-t-il ?
Calculer gcd(f,g) mod 3; Gcd(f,g) mod 3; pour f = 18x 3 − 42x 2 + 30x − 6
et g = −12x 2 + 10x − 2. Calculer également les résultants suivants :
resultant(f,g,x) mod 2; Resultant(f,g,x) mod 2; pour f = 4x 3 − x et
g = 2x + 1 (voir TR.VIII.C pour une définition du résultant, ou la partie du
TP.XI qui y est consacrée).
Le pgcd et le résultant de deux polynômes ne se comportent donc pas bien
a priori vis-à-vis de la réduction modulo p. Cependant, on voit facilement que
si p ne divise pas le coefficient dominant des deux polynômes, alors le résultant
réduit modulo p coïncide avec le résultant des réductions modulo p. On voit
également que si p ne divise pas le coefficient dominant de l’un des polynômes,
alors le résultant réduit modulo p n’est pas nul si et seulement si le résultant
n’est pas divisible par p.
D’autre part, on a vu que le résultant de f et g (tous les deux non nuls),
calculé sur un corps (Q ou F p ), est nul si et seulement si pgcd(f, g) est non
constant (TR.VIII.C). Ainsi, si p ne divise pas le coefficient dominant de l’un
des polynômes f et g, alors pgcd(f, g) est non constant si et seulement si
256
7. La situation est plus simple qu’en caractéristique p : sur l’exemple
f = x
12 + x
11
− x
9
− 2x
8 + x
5 + x
4
calculer u = f / pgcd(f, f ), factoriser en irréductibles f /u, puis recommencer
en remplaçant f par u, etc. Observer les facteurs des quotients f /u successifs
et en déduire un algorithme donnant la décomposition sans facteur carré. L’implémenter au sein d’une procédure Sans2Fact0:=proc(f), tester et comparer
avec la commande sqrfree de Maple.
Remarque. En fait, la commande sqrfree renvoie la décomposition sans facteur
carré de P dans Z[x], i.e. l’écriture P = λh 1
1 h 2
2 . . . h s
s où λ ∈ Z et les h i ∈ Z[x]
sont primitifs sans facteur carré et premiers deux à deux. La décomposition
en irréductibles dans Z[x] (cf. chapitre VIII) assure l’existence et l’unicité de
cette décomposition.
8. Nous allons réduire P modulo un nombre premier p. Pour appliquer l’algorithme de Berlekamp, il faut s’assurer que la réduction P est sans facteur
carré. Le but de cette question est d’expliquer quels nombres p conviennent,
c’est-à-dire comment choisir p sans avoir à calculer pgcd(P , P
) et recommencer avec un nouveau p si l’on ne trouve pas un polynôme constant.
Calculer gcd(2*x,2); gcd(-2*x,2); gcd(x/2,1/2); Gcd(2*x,2) mod 3;
Quelle normalisation du pgcd Maple utilise-t-il ?
Calculer gcd(f,g) mod 3; Gcd(f,g) mod 3; pour f = 18x 3 − 42x 2 + 30x − 6
et g = −12x 2 + 10x − 2. Calculer également les résultants suivants :
resultant(f,g,x) mod 2; Resultant(f,g,x) mod 2; pour f = 4x 3 − x et
g = 2x + 1 (voir TR.VIII.C pour une définition du résultant, ou la partie du
TP.XI qui y est consacrée).
Le pgcd et le résultant de deux polynômes ne se comportent donc pas bien
a priori vis-à-vis de la réduction modulo p. Cependant, on voit facilement que
si p ne divise pas le coefficient dominant des deux polynômes, alors le résultant
réduit modulo p coïncide avec le résultant des réductions modulo p. On voit
également que si p ne divise pas le coefficient dominant de l’un des polynômes,
alors le résultant réduit modulo p n’est pas nul si et seulement si le résultant
n’est pas divisible par p.
D’autre part, on a vu que le résultant de f et g (tous les deux non nuls),
calculé sur un corps (Q ou F p ), est nul si et seulement si pgcd(f, g) est non
constant (TR.VIII.C). Ainsi, si p ne divise pas le coefficient dominant de l’un
des polynômes f et g, alors pgcd(f, g) est non constant si et seulement si
256