Travaux pratiques
mod n). Alors les facteurs irréductibles dans la décompositon du polynôme cyclotomique Φ n sur F q sont tous de degré r et de multiplicité un.
Démonstration. Les facteurs irréductibles étant tous de multiplicité un en vertu de
la proposition précédente, il reste à démontrer qu’ils sont de degré r. Soit donc P
un tel facteur et s son degré. On considère le corps K = F q [x]/(P ), de cardinal
q s . Tout élement non nul α ∈ K vérifie α q s −1 = 1. Soit ζ la classe de x dans
F q [x]/(P ) : cet élément annule l’image de P , donc l’image de Φ n dans K. C’est
donc une racine primitive n-ième dans K. Puisque ζ q s −1 = 1 et puisque ζ est
primitive, n divise q s − 1, i.e. q s ≡ 1 mod n. Cela démontre que s est un multiple
de l’ordre r de q dans U(Z/nZ) et, en particulier, s r.
Démontrons maintenant que s r. Puisque ζ n = 1 et puisque n divise q r − 1,
on a ζ q r −1 = 1, donc ζ q r = ζ. On considère l’ensemble des racines dans K de
l’équation x q r = x. C’est un sous-corps de K contenant F q et ζ, qui est un
élément primitif de l’extension K/F q . Il s’agit donc de K tout entier. Comme
x q r − x possède au plus q r racines distinctes, le cardinal q s de K est plus petit
que q r , d’où s r.
Corollaire 1. Φ n est irréductible sur F q si et seulement si la classe de q est un
générateur de U(Z/nZ).
Par exemple, les polynômes Φ 3 et Φ 5 sont irréductibles sur F 2 .
Corollaire 2. Le polynôme Φ p r −1 se décompose sur F p en un produit de polynômes
irréductibles unitaires de degré r, deux à deux distincts. En particulier, il existe
des polynômes irréductibles sur F p de n’importe quel degré r.
Les polynômes cyclotomiques peuvent être calculés de façon efficace grâce aux
formules ci-dessous :
(i) Si p est un nombre premier ne divisant pas n alors Φ pn (x)Φ n (x) = Φ p (x p )
(démontrer que P
1/p
n
= {x ∈ C, x p ∈ P n } est l’union disjointe P pn
P n ).
(ii) Si chaque diviseur premier de k divise n, alors Φ kn (x) = Φ n (x k ).
On en déduit l’algorithme suivant de construction de Φ n :
– on détermine les diviseurs premiers p 1 , . . . , p m (distincts) de n ;
– on définit par récurrence f i (x) = f i−1 (x p i )/f i−1 (x) à partir de f 0 (x) = x−1 ;
– alors Φ n (x) = f m (x
n
p 1 ...pm ).
389
mod n). Alors les facteurs irréductibles dans la décompositon du polynôme cyclotomique Φ n sur F q sont tous de degré r et de multiplicité un.
Démonstration. Les facteurs irréductibles étant tous de multiplicité un en vertu de
la proposition précédente, il reste à démontrer qu’ils sont de degré r. Soit donc P
un tel facteur et s son degré. On considère le corps K = F q [x]/(P ), de cardinal
q s . Tout élement non nul α ∈ K vérifie α q s −1 = 1. Soit ζ la classe de x dans
F q [x]/(P ) : cet élément annule l’image de P , donc l’image de Φ n dans K. C’est
donc une racine primitive n-ième dans K. Puisque ζ q s −1 = 1 et puisque ζ est
primitive, n divise q s − 1, i.e. q s ≡ 1 mod n. Cela démontre que s est un multiple
de l’ordre r de q dans U(Z/nZ) et, en particulier, s r.
Démontrons maintenant que s r. Puisque ζ n = 1 et puisque n divise q r − 1,
on a ζ q r −1 = 1, donc ζ q r = ζ. On considère l’ensemble des racines dans K de
l’équation x q r = x. C’est un sous-corps de K contenant F q et ζ, qui est un
élément primitif de l’extension K/F q . Il s’agit donc de K tout entier. Comme
x q r − x possède au plus q r racines distinctes, le cardinal q s de K est plus petit
que q r , d’où s r.
Corollaire 1. Φ n est irréductible sur F q si et seulement si la classe de q est un
générateur de U(Z/nZ).
Par exemple, les polynômes Φ 3 et Φ 5 sont irréductibles sur F 2 .
Corollaire 2. Le polynôme Φ p r −1 se décompose sur F p en un produit de polynômes
irréductibles unitaires de degré r, deux à deux distincts. En particulier, il existe
des polynômes irréductibles sur F p de n’importe quel degré r.
Les polynômes cyclotomiques peuvent être calculés de façon efficace grâce aux
formules ci-dessous :
(i) Si p est un nombre premier ne divisant pas n alors Φ pn (x)Φ n (x) = Φ p (x p )
(démontrer que P
1/p
n
= {x ∈ C, x p ∈ P n } est l’union disjointe P pn
P n ).
(ii) Si chaque diviseur premier de k divise n, alors Φ kn (x) = Φ n (x k ).
On en déduit l’algorithme suivant de construction de Φ n :
– on détermine les diviseurs premiers p 1 , . . . , p m (distincts) de n ;
– on définit par récurrence f i (x) = f i−1 (x p i )/f i−1 (x) à partir de f 0 (x) = x−1 ;
– alors Φ n (x) = f m (x
n
p 1 ...pm ).
389