Travaux pratiques
Démonstration. Soit tout d’abord P un diviseur irréductible de F p [x] de degré un
diviseur d de n. Il s’agit de démontrer que P divise x p n − x. On a déjà vu que
α p d = α pour tout élément α d’un corps fini de cardinal p d (TR.IX.A). Comme
K = F p [x]/(P ) est un tel corps, on peut appliquer ce fait à la classe x de x
dans K. Ensuite, sachant que d divise n, on en déduit que x p n = x (on itère le
Frobenius ϕ p d : a → a p d qui est l’identité sur K), donc que P divise x p n − x.
Réciproquement, supposons que P soit un facteur irréductible de x p n − x et
démontrons que le degré d de P divise n. Considérons l’ensemble K des éléments
α du corps K = F p [x]/(P ) tels que α p n = α. Le fait que K soit un corps découle
directement du fait que ϕ p n est un morphisme de corps. De plus, il contient la
classe de x modulo P , car P divise x p n − x ; c’est donc K tout entier.
D’autre part, on a vu que le groupe des inversibles d’un corps est cyclique
(TR.IX.A). Il existe donc un élément α de K × d’ordre p d − 1. Comme α p n = α,
ou encore α p n −1 = 1, on voit que p d − 1 divise p n − 1. Cela implique que d divise
n : écrivons n = dq + r ; alors p n − 1 = p dq p r − 1 = (p dq − 1)p r + p r − 1. Comme
p d − 1 divise p dq − 1 et que p r − 1 < p d − 1, on voit que p r − 1 est le reste de la
division euclidienne de p n − 1 par p d − 1. Or ce reste est nul, donc r = 0.
Ainsi apparaissent dans la décomposition en irréductibles de x p n − x tous les
polynômes irréductibles unitaires de F p [x] de degré divisant n et uniquement ceuxlà. Il reste à prouver que ces facteurs sont tous de multiplicité un. On considère
pour cela le polynôme dérivé p n x p n −1 − 1 = −1 ; il est premier avec x p n − x, d’où
le résultat.
Cela démontre le critère. Existe-t-il pour autant de tels polynômes ?
Proposition 2. Pour tout nombre premier p et tout entier n 1, il existe des
polynômes irréductibles de degré n dans F p [x].
On a besoin, afin de construire les corps finis, d’une preuve effective. La méthode utilisée en pratique est surprenante au premier abord : on tire au hasard
un polynôme unitaire de degré n dans F p [x], on teste son irréductibilité, et on
recommence en cas d’échec.
En effet, notant I(n, p) le nombre de polynômes irréductibles unitaires de
F p [x] de degré n 1, il résulte du lemme précédent que
d|n dI(d, p) = p n . On
en déduit la majoration I(n, p) p n /n que l’on applique également aux I(d, p)
pour d < n divisant n. Ainsi
p
n
− nI(n, p)
d|n,d
d
E(n/2)
d=1
p
d = p(p
E(n/2)
− 1)/(p − 1) < p
E(n/2)+1 ,
251
Démonstration. Soit tout d’abord P un diviseur irréductible de F p [x] de degré un
diviseur d de n. Il s’agit de démontrer que P divise x p n − x. On a déjà vu que
α p d = α pour tout élément α d’un corps fini de cardinal p d (TR.IX.A). Comme
K = F p [x]/(P ) est un tel corps, on peut appliquer ce fait à la classe x de x
dans K. Ensuite, sachant que d divise n, on en déduit que x p n = x (on itère le
Frobenius ϕ p d : a → a p d qui est l’identité sur K), donc que P divise x p n − x.
Réciproquement, supposons que P soit un facteur irréductible de x p n − x et
démontrons que le degré d de P divise n. Considérons l’ensemble K des éléments
α du corps K = F p [x]/(P ) tels que α p n = α. Le fait que K soit un corps découle
directement du fait que ϕ p n est un morphisme de corps. De plus, il contient la
classe de x modulo P , car P divise x p n − x ; c’est donc K tout entier.
D’autre part, on a vu que le groupe des inversibles d’un corps est cyclique
(TR.IX.A). Il existe donc un élément α de K × d’ordre p d − 1. Comme α p n = α,
ou encore α p n −1 = 1, on voit que p d − 1 divise p n − 1. Cela implique que d divise
n : écrivons n = dq + r ; alors p n − 1 = p dq p r − 1 = (p dq − 1)p r + p r − 1. Comme
p d − 1 divise p dq − 1 et que p r − 1 < p d − 1, on voit que p r − 1 est le reste de la
division euclidienne de p n − 1 par p d − 1. Or ce reste est nul, donc r = 0.
Ainsi apparaissent dans la décomposition en irréductibles de x p n − x tous les
polynômes irréductibles unitaires de F p [x] de degré divisant n et uniquement ceuxlà. Il reste à prouver que ces facteurs sont tous de multiplicité un. On considère
pour cela le polynôme dérivé p n x p n −1 − 1 = −1 ; il est premier avec x p n − x, d’où
le résultat.
Cela démontre le critère. Existe-t-il pour autant de tels polynômes ?
Proposition 2. Pour tout nombre premier p et tout entier n 1, il existe des
polynômes irréductibles de degré n dans F p [x].
On a besoin, afin de construire les corps finis, d’une preuve effective. La méthode utilisée en pratique est surprenante au premier abord : on tire au hasard
un polynôme unitaire de degré n dans F p [x], on teste son irréductibilité, et on
recommence en cas d’échec.
En effet, notant I(n, p) le nombre de polynômes irréductibles unitaires de
F p [x] de degré n 1, il résulte du lemme précédent que
d|n dI(d, p) = p n . On
en déduit la majoration I(n, p) p n /n que l’on applique également aux I(d, p)
pour d < n divisant n. Ainsi
p
n
− nI(n, p)
d|n,d
d
E(n/2)
d=1
p
d = p(p
E(n/2)
− 1)/(p − 1) < p
E(n/2)+1 ,
251