Les corps finis

Table des matières

1 Structure des corps finis 2

2 Construction de corps finis 4

2.1 Existence et unicité d’un corps de cardinal pn . . . . . . . . . . . . . . 4
2.2 Corps finis comme quotient de Fp [X]. . . . . . . . . . . . . . . . . . . 5
2.3 Polynômes irréductibles sur Fp . . . . . . . . . . . . . . . . . . . . . . 6

3 Dénombrement et Existence 8
3.1 Dénombrement des polynômes irréductibles sur Fp . . . . . . . . . . . 8

4 Polynômes cyclotomiques 9
4.1 Racines de l’unité et ψn . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.2 Racines de ψn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.3 L’irréductibilité sur Q des polynômes cyclotomiques . . . . . . . . . . 12

5 Décomposition des polynômes dans Fp [X]. 15

5.1 Polynômes sans facteurs multiples . . . . . . . . . . . . . . . . . . . . 15
5.2 Algorithme de Berlekamp . . . . . . . . . . . . . . . . . . . . . . . . 15

1
AG: CPAM1 CRMEF-CPA Fès-Mekness

1 Structure des corps finis

Remarque 1.0.1. 1. Soit K un corps de caractéristique p ̸= 0 soit r entier > 0.

r
Alors k := {α ∈ K, αp = α} est un sous-corps de K.
2. Soit p un entier premier tel que pr − 1 divise pn − 1, alors r divise n.

Corps premiers
.

Théorème 1.0.2. Soit K un corps fini.

1. La caractéristique de K est un nombre premier et |K| = pn où n entier
> 0.
n
2. On a αp = α pour tout α ∈ K ; on a dans l’anneau K[X] la relation
n
Y
Xp − X = (X − α).
α∈K

3. Le groupe K ∗ est cyclique d’ordre pn − 1.

4. Si k est sous-corps de K, alors |k| = pr avec r divise n.
5. Inversement, pour tout diviseur r de n, il existe un unique sous-corps
r
de K à pr éléments : c’est l’ensemble des α ∈ K tels que αp = α. On
le note GF (pr ) dit le corps de Galois d’ordre pr . L’unicité est à
isomorphisme près.

Démonstration. 1. Puisque K est fini, son corps premier ne peut être Q, et p ̸= 0.

Alors K est un Fp -espace vectoriel. Donc |K| = |Fp |dimFp (K) .
n
2. D’après le Théorème de Lagrange, pour tout α ∈ K, αp = α. Donc tout α ∈ K
n
est un zéro du polynôme X p − X de degré pn et possédant pn zéros.
3. On va démontrer ici que si K corps commutatif et G un sous-groupe fini
de K ∗ , alors G est cyclique.
En effet :
Posons n = |G|.
Soit d un diviseur de n. S’il existe a ∈ G d’ordre d, alors G a un sous-groupe
H = (a) d’ordre d. Soit y ∈ H, on a y d = 1, et donc y est racine du polynôme
X d − 1 ∈ K[X], qui a au moins d racines puisque K est intègre. Ce polynôme
a d’autre part au plus d racines, ce qui signifie qu’il a exactement d racines,
qui ne sont que les éléments de H. Or le nombre d’éléments d’ordre d de H
est φ(d).
Ainsi, pour tout diviseur d de |G|, le nombre Nd des éléments de G d’ordre d
est soit 0 soit φ(d). Donc Nd ⩽ φ(d). Or on sait l’ordre de tout élément de G
divise n, donc on a :
X X
n = |G| = Nd ⩽ φ(d).
d|n d|n

2 [Link]
AG: CPAM1 CRMEF-CPA Fès-Mekness

X
Or on sait que n = φ(d). On en déduit donc que tout diviseur d de n, on
d|n
a Nd = φ(d). En particulier Nn = φ(n) > 0, c’est à dire que G contient un
élément d’ordre n, par conséquent G est cyclique.
4. Soit k un sous-corps de K. d’après (1) |k| = pr . On peut voir que K est un
k-espace vectoriel de dimension r >, donc |K| = |k|m avec m entier. Donc
pn = prm . Donc r divise n. On peut aussi voir l’ordre du groupe k ∗ qui est
pr − 1 divise l’ordre du groupe K ∗ , donc r divise n. Notons de plus que, pour
r
tout α ∈ k, on a αp = α, mais cette équation admet au plus pr solutions, qui
sont donc les éléments de k. Cela montre que k est l’ensemble des racines dans
K de l’équation précédente.
5. Inversement, soit r un diviseur de n. Notons k l’ensemble des α ∈ K tels
r
que αp = α. C’est un sous-corps et il a au plus pr éléments. Puisque K ∗ est
cyclique d’ordre pn − 1 et que pr − 1 divise pn − 1, alors K ∗ possède un élément
d’ordre pr − 1, disons a, ce qui implique l’équation définissant k a au moins pr
2 r
solutions (0, a, a , ...., ap −1 ). Ainsi k a pr éléments.

Remarque 1.0.3. Posons q = pr le cardinal de Fp . On note Fp la clôture algébrique

de Fp . Soit R l’ensemble des zéros de f (X) := X q − X ∈ Fp [X]. On f ′ (X) = −1.
Ainsi toutes les racines de f sont simples., par conséquent |R| = q.
Il est clair que R est un corps, donc sous-corps de Fp de cardinal q.
L’unicité à isomorphisme près.
Soit E un corps à q éléments. Son sous-corps premier est nécessairement iso-
morphe à Fp . Le groupe multiplicatif E ∗ est cyclique d’ordre q − 1, donc xq−1 = 1
pour tout x ∈ E ∗ . On en déduit que ∀x ∈ E, xq = x. L’extension Fp ⊂ est algébrique,
donc E se plonge dans Fp à l’aide de

τ : E −→ Fp .

Ainsi tous les éléments de τ (E) sont des zéros de f (X) = X q − X dans Fp . Donc
τ (E) ⊂ R, et comme |τ (E)||E| = |R|, on déduit que τ (E) = R. Donc E ≃ R.

Corps premiers
.

Théorème 1.0.4. Théorème de l’élément primitif

Soit K un corps fini de caractéristique p > 0. Il existe un élément primitive
de K sur Fp .

Démonstration. On a déjà vu que K ∗ est cyclique, soit ω un générateur de ce groupe

K ∗ = (ω). Alors tout élément non nul de K est une puissance de ω, et tout sous-
anneau contenant ω coı̈ncide avec K.

3 [Link]
AG: CPAM1 CRMEF-CPA Fès-Mekness

2 Construction de corps finis

Soit p un nombre premier ⩾ 2.

On considère dans cette section que p ⩾ 2 est un nombre premier.

2.1 Existence et unicité d’un corps de cardinal pn .

Thème de développement

Thème de développement : Existence et unicité d’un corps fini

Théorème 2.1.1. Soit n ∈ N∗ . On note q = pn .

(i) Il existe un corps fini à q éléments. Il est corps de décomposition sur Fp
n
du polynôme X p − X.
(ii) Deux corps à q éléments, sont Fp -isomorphes.

Démonstration. (i) • Soit K un corps de décomposition de X q − X sur Fp , et

soit k l’ensemble des racines dans K de X q − X. L’application h de K dans
K définie
∀t ∈ K, h(t) = tq
est un automorphisme de K. Par suite k := {x ∈ K; h(x) = x} est un sous-
corps de K. Donc k contient Fp , sous-corps premier de K. Comme (X q −
X)′ = qX q−1 − 1 = −1 ̸= 0, il s’ensuit que toutes les racines de X q − X
sont simples. Ainsi card(k) = q, et donc k est un corps à q éléments. Et on a
k = K = DFp (X q − X).
(ii) • Soit K un corps à q éléments. Puisque la caractéristique de K est un entier
premier divisant q, alors char(K) = p et le sous-corps premier de K est Fp . Or
(K ∗ , ×) est un groupe à q − 1 éléments, ce qui entraine d’après le théorème de
Lagrange que ∀x ∈ K ∗ , xq−1 = 1 et donc ∀x ∈ K, xq = x. Or le polynôme
X q −X ∈ Fp [X] de degré q, admet au plus q racines distinctes dans K. Puisque
tout élément de K est une racine de X q − X, on déduit que K est un corps de
décomposition sur Fp de X q − X.
Ainsi comme deux corps de décomposition d’un polynôme sur un corps K sont
K-isomorphes, on déduit (ii).

Y
Remarque 2.1.2. On a x = −1. En effet, si on note Fp = {ai ; 0 ⩽ i ⩽ q − 1},
x∈F∗p
alors
q−1
Y
q−1
X −1= (X − ak ).
k=0

4 [Link]
AG: CPAM1 CRMEF-CPA Fès-Mekness

q−1
Y
Ce qui donne ak = −1.
k=0

2.2 Corps finis comme quotient de Fp [X].

Soit p un nombre premier ⩾ 2 et n un entier non nul.

Corps finis

Théorème 2.2.1. Soit K un corps fini de cardinal pn . Il existe un polynôme

p [X]
P irréductible dans Fp [X] de degré n, tel que les corps K et F(P )
soient
isomorphes.

Démonstration. Soit α un générateur de K ∗ . Considérons l’application


 Fp [X]X −→ K X
Ψ: P = a i X i
−
7 → ai α i

i i

Les ai sont identifiés avec n’importe quel entier relatif dont la classe modulo p est
ai . Cela est permis car K est de caractéristique p. Ψ est un morphisme d’anneaux
surjectif car α générateur de K ∗ . Alors ker Ψ est un idéal de Fp [X], il existe alors
P ∈ Fp [X] non nul tel que ker Ψ = (P ) Puisque Fp [X]/(P ) est isomorphe à K,
alors Fp [X]/(P ) est un corps et par suite P est irréductible de Fp [X]. Soit m son
degré,alors le cardinal de Fp [X]/(P ) est pm = pn c’ qui donne m = n.

Les corps finis de cardinal pn s’obtiennent exclusivement à partir des

polynômes irréductibles de degré n sur Fp [X].

Plus précisément on a :

Existence de corps finis

Théorème 2.2.2. Soient p un nombre premier et n entier ⩾ 1. Les deux

assertions suivantes sont équivalentes :
(a) Il existe un corps à pn éléments.
(b) Il existe un polynôme irréductible de degré n dans Fp [X].

Il s’agit maintenant de démontrer l’existence de polynômes irréductibles

de tout degré n ⩾ 1 dans Fp [X] et ensuite de prouver que si U et V des
polynômes irréductibles de degré n dans Fp [X], alors les corps Fp [X]/(U )
et Fp [X]/(V ) sont isomorphes.

5 [Link]
AG: CPAM1 CRMEF-CPA Fès-Mekness

2.3 Polynômes irréductibles sur Fp .

Pour tout entier n ∈ N∗ , on note In (p) l’ensemble de tous les polynômes irréductibles
unitaires de degré n dans Fp [X] et mn (p) le cardinal de In (p).
On sait que pour toutP ∈ In (p), le quotient Fp [X]/(P ) est une Fp -algèbre de
k
dimension n de base X . C’est un corps fini de cardinal pn .
0 ⩽ k ⩽ n−1

Dans ce qui suit on va démontrer qu’il existe dans Fp [X] des polynômes
irréductibles de tout degré n ⩾ 1. Ceci permet de construire des corps
finis à pn éléments. Pour cela on note :
n
Pn (X) = X p − X ∈ Fp [X].

n
Thème de de développement : Factorisation de X p − X.

Théorème 2.3.1. Thème de développement

Tout diviseur de Pn dans Fp [X] est de degré divisant n. Réciproquement, pour

tout diviseur r de n, tout polynôme Q ∈ Ir (p) divise Pn .
Plus précisément on a
n
Y
Xp − X = Q.
où Q parcourt l’ensemble des polynômes irréductibles unitaires de Fp [X] dont
le degré divise n.

Démonstration. Soit P ∈ Id (p) divisant P

n . kAlors Pn = 0 dans Fpd = Fp [X]/(P ),
pn

ce qui revient à dire X = X. Comme X est une base du Fp -espace
0 ⩽ k ⩽ d−1
vectoriel Fpd , tout élément Q de Fpd s’écrit de la manière suivante
d−1
X k
Q= ak X
k=0

avec ak ∈ Fp et on a :

d−1
!pn d−1
pn X k X n
 n
k p
Q = ak X = apk X
k=0 k=0

n
car la caractéristique du corps est p. D’autre part apk = ak dans Fp et
 p n  p n k k
Xk = X =X .

Ce qui nous donne

6 [Link]
AG: CPAM1 CRMEF-CPA Fès-Mekness

pn
Q = Q.
Par conséquent :
pn −1
∀Q ∈ F∗pd , Q = 1.
Comme F∗pd cyclique d’ordre pd − 1, alors pd − 1 divise pn − 1, ce qui entraine
que d divise n.
Réciproquement, pour tout P ∈ Id (p), avec d divisant n, le corps Fpd := Fp [X]/(P )
est de cardinal pd , donc F∗pd est cyclique d’ordre pd − 1, d’après le Théorème de La-
pd pkd
grange, on déduit que X = X. Par récurrence, onn en déduit que X = X pour
p
tout k ∈ N. Comme d divise n, il s’ensuit que X = X dans Fp [X]/(P ), ce qui
n
revient à dire que P divise Pn (X) = X p − X.
Autre démonstration :
Soit F ∈ Fp [X] un polynôme irréductible unitaire de degré r. Montrons
n
F divise X p − X ⇔ r|n.
Considérons un corps de rupture L de F sur Fp et α une racine de F dans
r
L = Fp (α) = Fp [X]/(F ). On a r est le plus petit entier ⩾ 1 tel que αp = α et on a
r−1
i
Y
F (X) = (X − αp )
i=0

Par ailleurs
ir
αp = α ∀i ∈ N.
n n
Supposons que F divise X p − X. Puisque F (α) = 0, on a αp = α. Écrivons
n = rt + s avec 0 ⩽ s < r. Alors
n ir s s
αp = (αp )p = αp = α.
Ce qui contredit la minimalité de r. Donc s = 0 et r divise n.
n
Inversement si r divise n, on déduit que αp = α. autrement dit α est une racine
n
de X p − X. Les éléments
r−1
α, · · · , αp
n
sont donc des racines deux à deux distinctes de X p − X. Il en résulte alors que F
n
divise X p − X.

Exemple 2.3.2. La décomposition de X 8 − X dans F2 [X] en produit de polynômes

irréductibles sur F2 est donnée par l’égalité.
X 8 − X = X(X + 1)(X 3 + X + 1)(X 3 + X 2 + 1).
De même, la décomposition de X 9 −X ∈ F3 [X] en produit de polynômes irréductibles
unitaires sur F3 est
X 9 − X = X(X + 1)(X + 2)(X 2 + 1)(X 2 + X + 2)(X 2 + 2X + 2).

7 [Link]
AG: CPAM1 CRMEF-CPA Fès-Mekness

3 Dénombrement et Existence
3.1 Dénombrement des polynômes irréductibles sur Fp .
On considère dans cette section un corps fini de cardinal q. Pour tout entier
n ⩾ 1, on note mn (p) le nombre de polynômes irréductibles et unitaires de degré n
dans K[X].
La formule
n
Y Y
Xp − X = F.
d|n F ∈Id (p)

Permet de montrer que X

pn = dmd (p).
d|n

Le nombre des polynômes irréductibles sur Fp [X].

Théorème 3.1.1. On a
pn − p⌊n/2⌋+1 pn
⩽ mn (p) ⩽ .
n n

X
Démonstration. De la formule pn = dmd (p), on tire pn ⩾ nmn (p) d’où
d|n

pn
mn (p) ⩽ .
n
D’après la formule précédente
X
pn = nmn (p) + [Link] (p),
d|n,d̸=n

ce qui implique
⌊n/2⌋
X X p⌊n/2⌋+1 − 1
n
p ⩽ nmn (p)+ d
p ⩽ nmn (p)+ pd ⩽ nmn (p)+ ⩽ nmn (p)+p⌊n/2⌋+1 .
k=0
p−1
d|n,d̸=n

On obtient, alors
pn − p⌊n/2⌋+1 pn
⩽ mn (p) ⩽ .
n n

8 [Link]
AG: CPAM1 CRMEF-CPA Fès-Mekness

Existence d’un corps fini

Corollaire 3.1.2. Pour tout entier n ⩾ 1 et tout nombre premier p, il existe

un corps de cardinal pn .

Démonstration. D’après le Théorème 3.1.1, on a :

n
[Link] (p) p 2 +1 1
n
− 1 < n = n −1 ,
p p p 2

ce qui montre que

[Link] (p)
lim = 1,
n−→+∞ pn
et donc
pn
mn (p) ∼n .
n
On déduit alors que, mn (p) > 0. Ce qui prouve l’existence d’un polynôme P
irréductible unitaire de degré n sur K. Le Théorème 3.1.1 prouve alors l’existence
de Fp [X]/(P ) un corps fini de cardinal pn .

4 Polynômes cyclotomiques
4.1 Racines de l’unité et ψn .
Soient K un corps et n ∈ N∗ , on considère le polynôme Pn (X) = X n − 1.
On suppose que
n ∧ char(K) = 1.
On note
Un,K := {ζ ∈ K|ζ n = 1}
le groupe des racines niemes de l’unité. C’est un groupe cyclique d’ordre r ⩽ n.
On note Kn un corps de décomposition de Pn sur K.
On a alors
card(Un,Kn ) = n,

Racine n-ième primitive

.

Définition 4.1.1. Une racine n-ième primitive de 1 est un élément ζ ∈ Kn

générateur du groupe cyclique Un,K .

9 [Link]
AG: CPAM1 CRMEF-CPA Fès-Mekness

Remarque 4.1.2. Un élément ω ∈ Un,K est une racine n-ième primitive de l’unité
si et seulement si ω est d’ordre n dans le groupe Un,K : c’est à dire

ω n = 1 et ∀d < n, ω d ̸= 1.

De plus
µn = {ω k ∈ Un,K |k ∧ n = 1}.

Polynômes cyclotomique
.

Définition 4.1.3. Soit n ∈ N∗ . Le nieme polynôme cyclotomique ψn (X) ∈

Kn [X] est défini par : Y
ψn,K (X) = (X − ζ).
ζ∈µn

Remarque 4.1.4. 1. Si ζ est une racine n-ième de l’unité, alors les autres sont
ζ m avec m ∧ n = 1.
2. On deg(ψn ) = ϕ(n).
3. pour n ∧ char(K) = 1, on a Pn′ (X) = nX n−1 .

Factorisation de X n − 1 comme produit cyclotomique

.

Théorème 4.1.5. On a
Y
Xn − 1 = ψd,K (X).
d|n

X
Démonstration. Les deux polynômes sont unitaires de même degré, car n = φ(d).
d|n
Il suffit de montrer que
Un (Kn ) = ∪d|n µn .
L’inclusion ∪d|n µn ⊂ Un est évidente. Soit ω élément de Un (Kn ), Soit d l’ordre
de ω, on a d|n. Donc ω ∈ µd . D’où
!
Y Y Y Y
Xn − 1 = (X − ω) = (X − ω) = ψd (X).
ω∈Un d|n ω∈µd d|n

10 [Link]
AG: CPAM1 CRMEF-CPA Fès-Mekness

Exemple 4.1.6.

ψ1 (X) = X − 1, ψ2 (X) = X + 1, ψ3 (X) = X 2 + X + 1, ψ4 (X) = X 4 + 1.

Soit p premier, alors

ψp (X) = X p−1 + X p−2 + .... + 1.

On a
Xn − 1
ψn (X) = Y .
(ψd (X)
d|n,d̸=n

On note Y
F (X) = (ψd (X).
d|n,d̸=n

ψn,Q (X) ∈ Z[X].

.

Proposition 4.1.7. On a
1. ψn,Q (X) ∈ Z[X].
2. Soit k un corps quelconque et σ : Z −→ K l’homomorphisme canonique.
Alors
ψn,K (X) = σ(ψn,Q (X)).

Démonstration. 1. Par récurrence sur n.

2. Par récurrence sur n. Pour n = 1 c’est trivial. Dans Z[X] on a

X n − 1 = ψn,Q (X).F (X).

Comme σ est un homomorphisme, on a, dans Kn [X], X n − 1 = σ(X n − 1) =

σ(ψn,Q )σ(F ). Mais par hypothèse de récurrence, on a
Y Y
σ(F ) = σ(ψd,Q )(X) = ψd,K (X),
d|n,d̸=n d|n,d̸=n

Y
et comme par définition X n − 1 = ψd,K (X), il en résulte, puisque K[X]
d|n,d̸=n
est intègre, qu’on a bien
ψn,K = σ(ψn,Q ).

11 [Link]
AG: CPAM1 CRMEF-CPA Fès-Mekness

4.2 Racines de ψn .

Racines nième primitives

.

Lemme 4.2.1. Soit A un anneau intègre et n un entier > 0 tel que n.1A ̸= 0.
i Les racines nième de l’unité dans A sont des racines simples de X n − 1.
Plus généralement il n’existe pas de polynômes non constant Q ∈ A[X]
tel que Q2 divise X n − 1.
ii Les racines de ψn dans A sont exactement les racines primitives n-ième
de l’unité dans A.

Démonstration. Écrivons X n − 1 = Q2 (X)R(X) et dérivons : on obtient

nX n−1 = Q(X) (2Q′ (X)R(X) + Q(X)R(X))

Par combinaison, on obtient dans A[X] la relation

n.1A = X(nX n−1 ) − n(X n − 1)

= Q(X) (2XQ′ (X)R(X) + XQ(X)R′ (X) − nQ(X)R(X))

et Q(X), divisant la constante non nulle n.1A , est constant. Cela prouve (i).
Une racine n-ième de l’unité dans A, c’est à dire une racine du polynôme X n − 1,
est une racine d’exactement d’un des polynômes ψd pour d divisant n et distinct
de n, mais l’ensemble des racines de ψd pour d divisant n et distinct de n est aussi
l’ensemble des racines de X d − 1 pour d divisant n et distinct de n, c’est-à-dire
l’ensemble des racines n-ièmes de l’unité qui ne sont pas primitives. Cela prouve
(ii).

4.3 L’irréductibilité sur Q des polynômes cyclotomiques

Lemme 4.3.1. Soient P et Q deux polynômes non nuls de Q[X], et z ∈ C

tel que P (z) = Q(z) = 0. Si Q est irréductible dans Q[X], il divise P.

Démonstration. Puisque Q est irréductible, il s’agit de prouver que P et Q ne sont

pas premiers entre eux, dans le cas contraire, il existerait a, b dans Q[X] tels que
1 = a(X)P (X)+b(X)Q(X) et, prenant X = z, on obtiendrait une contradiction.

12 [Link]
AG: CPAM1 CRMEF-CPA Fès-Mekness

Lemme 4.3.2. Soient f et g deux polynômes unitaires de Q[X] tels que

f (X)g(X) ∈ Z[X], alors f, g ∈ Z[X].

Démonstration. Soit d (resp., e) un dénominateur commun pour les coefficients de

f (resp., g). Puisque le terme dominant de df est d, alors le contenu d′ := c(df )
divise d. De même le contenu e′ := c(eg) divise e. Dans Z[X], on a [Link] = de(f.g).
Comme f g est unitaire et à coefficients dans Z[X], alors c(f g) = 1. Le lemme de
Gauss, montre alors que de = d′ e′ . Par conséquent d′ = d, e′ = e. Ce qui implique
df eg
que f = ′ et g = ′ sont dans Z[X].
d e

ϕn est à coefficients entiers

Théorème 4.3.3. Pour tout n ∈ N∗ , on a :

ψn (X) ∈ Z[X].

Démonstration. Par récurrence sur n et par utilisation du Lemme 4.3.2.

Pour n = 1, on a ψ1 (X) = X + 1 ∈ Z[X].
Y k < n. Alors ψd (X) ∈ Z[X]
Soit n ⩾ 2. Supposons le théorème pour les entiers
pour tout diviseur de n distinct de n. Donc Q := ψd (X) ∈ Z[X]. Or
d|n

P := X n − 1 = Q(X)ψn (X).

Puisque X n − 1 ∈ Z[X] et Q ∈ Z[X], et sont unitaires, on déduit du Lemme 4.3.2,

que ψn (X) ∈ Z[X].

Thème de Développement :L’irréductibilité de ψn

Théorème 4.3.4. Pour tout n ∈ N∗ , le polynôme ψn (X) est irréductible dans

Z[X] et dans Q[X]. C’est le polynôme minimal de toute racine primitive nième
de l’unité ω ∈ µn sur Q.

Démonstration. Soit P un facteur irréductible de ψn (X) dans Q[X] et soit Q ∈ Q[X]

tels que ψn (X) = P (X)Q(X). D’après le Lemme 5.2.1, on a P, Q ∈ Z[X]. Notons que
puisque ψn est unitaire, alors les coefficients dominants P et Q sont dans {−1, 1}.
On peut donc supposer que P et Q sont unitaires.

13 [Link]
AG: CPAM1 CRMEF-CPA Fès-Mekness

Il s’agit de montrer que ψn = P. Pour cela, on montre que toute racine primitive
nième de l’unité est une racine de P. Si ζ et ζ ′ sont deux racines primitives nième
de l’unité, alors on peut écrire ζ ′ = ζ m avec m premier avec n.
Montrons l’assertion suivante :

Si le nombre premier p ne divise pas n et si P (ζ) = 0, alors P (ζ p ) = 0.

Remarquons d’abord qu’on peut écrire X n − 1 = P (X)Q(X) avec Q(X) ∈ Q[X],

ce qui d’après le Lemme 4.3.2, entraine que P ∈ Z[X] et Q ∈ Z[X]. Pour prouver
notre assertion, il suffit de justifier que Q(ζ p ) ̸= 0. Dans le cas contraire le polynôme
Q(X p ) aurait ζ comme racine, il sera donc multiple de P, et on pourrait écrire
Q(X p ) = P (X)R(X). D’après le Lemme 4.3.2, on aura R ∈ Z[X]. Finalement, on
dispose d’un nombre premier p à n et de trois polynômes P, Q et R de Z[X] avec :

X n − 1 = P (X)Q(X), Q(X p ) = P (X)R(X).

Réduisons maintenant tout ceci modulo p. On obtient dans (Z/pZ) [X] des iden-
tités analogues, soit

X n − 1 = P (X)Q(X), Q(X p ) = P (X)R(X).

p p
Mais, Q(X p ) = Q(X) . Ainsi, tout facteur irréductible T (X) de P divise Q donc
Q, donc T 2 divise X n − 1 dans (Z/pZ) [X], ce contredit le Lemme 4.2.1.

Corps cyclotomiques

Définition 4.3.5. Fixons un entier n > 0. On appelle corps cyclotomique

de niveau n, et on note Rn , le plus petit sous-corps de C contenant toutes
les racines n-ièmes de l’unité. Il contient donc Q.

Q[X]
Rn ≃ .
(ψn )

Q[X]
Proposition 4.3.6. Le corps Rn est isomorphe à l’anneau quotient .
(ψn )
c’est un Q-espace vectoriel de dimension ϕ(n) et B := {ζ i , 0 ⩽ i ⩽ ϕ(n) − 1}
en est une base, pour toute racine n-ième primitive ζ.

Démonstration. On remarque ζ racine de ψn qui est irréductible sur Q[X], donc le

Q[X]
plus petit sous-corps contenant ζ est identifié à . Comme les racines n-ième de
(ψn )
l’unité sont exactement les puissances de ζ, elles appartiennent à ce corps, qui est
Rn .

14 [Link]
AG: CPAM1 CRMEF-CPA Fès-Mekness

5 Décomposition des polynômes dans Fp[X].

Cette section est consacrée à des algorithmes de décomposition de polynômes
en facteurs irréductibles. Partant d’un polynôme P, on puisse justifier qu’il est
irréductible, ou fournir un facteur non trivial, disons Q/ il n’y à appliquer suc-
cessivement l’algorithme à Q et P/Q.

5.1 Polynômes sans facteurs multiples

Fixons un corps K et P un polynôme unitaire de K[X]. On sait que P admet
une décomposition de la forme
n
Y
P = Pimi ,
i=1

où les mi sont des entiers > 0.

5.2 Algorithme de Berlekamp

Soit p un nombre premier, q = ps et Fq le corps fini à q éléments. On considère
un polynôme P ∈ Fp [X] sans facteur carré : On écrit :
r
Y
P = Pi
i=1

où les Pi sont des polynômes irréductibles premiers entre eux deux à deux.
On note
x ≡ (X mod P )
Fq [X]
dans (P )
et considérons la base

B := {1, x, ..., xdeg(P )−1 }

q [X]
de F(P )
.
L’algorithme de Berlekamp calcul le nombre r des facteurs irréductibles de P et,
lorsque r ⩾ 2 donne explicitement les Pi .

15 [Link]
AG: CPAM1 CRMEF-CPA Fès-Mekness

Algorithm1 : Algorithme de Berlekamp

1. On considère l’application

 Fq [X] Fq [X]
−→
Sp : (P ) (P )
Q(X) mod (P ) 7−→ Q(X p ) mod(P )


On calcul la matrice de Sp − I dans B.

2. Le nombre de facteur irréductibles de P est

r = dim(ker(Sp − I)))deg(P ) − rg(Sp − I)

On calcul r avec pivot de Gauss.

3. if r = 1 then
4. P est irréductible et on a fini.
5. else
Fp [X]
6. On choisit V non constant de tel que V ∈ ker(Sp − I).
(P )
7. Calcul du pgcd(P, V − α), où α ∈ Fq à l’aide de l’algorithme d’Euclide. On a
lors Y
P = pgcd(P, V − α).
α∈Fq

8. On applique l’algorithme( à partir de 1) aux facteurs non triviaux de ce produit

s’ils existent.
9. end if.
On commence par démontrer les lemmes suivants :

Linéarité de Sp .

Lemme 5.2.1. L’application Sp est linéaire.

Démonstration. On sait que l’application


Fq [X] −→ Fq [X]
δ:
Q(X) 7−→ Q(X q )

est l’unique morphisme tel que δ(a) = a pour tout a ∈ Fq et δ(X) = X q . De plus,
on remarque que pour tout Q ∈ Fq [X],

= Q(X q ) =
δ(Q) |{z} =
|{z} Qq
déf inition ∀a∈Fq ,aq =a

Fp [X]
Soient π : Fp [X] −→ la surjection canonique et ψ = δ ◦ π. Comme π est
(P )
un morphisme d’anneaux, on a

ψ(P ) = π(δ(P )) = π(P q ) = (π(P ))q = 0

16 [Link]
AG: CPAM1 CRMEF-CPA Fès-Mekness

Par passage aux quotients, ψ passe au quotient par (P ) pour donner Sp , elle est
donc bien définie.
Montrons que Sp correspond à l’élévation à la puissance q :

Sp (Q) = Sp (π(Q))
= π(Q(X q )
= π(Qq )
= Qq

On obtient donc le résultat.

Le nombre des irréductibles

r
Y
Lemme 5.2.2. Soit P = Pi , où Pi sont irréductibles et premiers entre
i=1
eux deux ç deux, r est alors le nombre de polynômes irréductibles de P. Alors
r = dim ker(Sp − I).

17 [Link]