2M120 ÉLÉMENTS D’ARITHMÉTIQUE LICENCE D’INFORMATIQUE UPMC 2015-2016
2 Corps finis
Exercice 2.1 — Algorithme d’Euclide
1. Soit a et b deux entiers strictement positifs tels que a > b. On pose r0 = a et r1 = b et on fait
des divisions euclidiennes successives :
r0 = r1 q1 + r2 , 0 < r2 < r1
r1 = r2 q2 + r3 , 0 ≤ r3 < r2
.. ..
. .
rn−2 = rn−1 qn−1 + rn , 0 ≤ rn < rn−1
rn−1 = rn qn + 0
Montrer que si d | a et d | b alors pour 0 ≤ i ≤ n : d | ri .
2. Calculer les ri et qi pour a = 1016 et b = 317. Que peut-on en déduire sur ces deux nombres ?
3. Les nombres qi étant construit comme ci-dessus, on définit ui et vi par :
u0 = 1, u1 = 0, et pour i ≥ 1 : ui+1 = ui−1 − ui qi
v0 = 0, v1 = 1, et pour i ≥ 1 : vi+1 = vi−1 − vi qi
Montrer qu’on a pour 0 ≤ i ≤ n : ri = aui + bvi
4. Calculer les ui et vi pour a = 1016 et b = 317, et en déduire u et v tels que au + bv = 1.
5. Autre exemple : a = 571 et b = 258.
Définition 2.2 — définition rapide de Z/nZ, suffisante pour faire des calculs :
— Z/nZ est un ensemble de n éléments notés 0, 1, 2, . . . , n − 1,
— si a ∈/ {0, 1, 2, . . . n − 1} alors a = r où r est le reste de la division euclidienne de a par n,
— en particulier : n = 0,
— si a ∈ Z/nZ et b ∈ Z/nZ on pose a + b = a + b et a × b = ab
Exercice 2.3
1. Écrire les tables d’addition et de multiplication de Z/6Z et de Z/7Z.
2. Vérifier que tout élément non nul de Z/7Z est inversible.
3. Quels sont les éléments inversibles de Z/6Z ?
Exercice 2.4
1. Pour tout élément a de Z/7Z, calculer a2 , a3 , a4 , a5 , a6 .
2. Déterminer le reste de la division euclidienne de 123456 par 7.
2 4 8 2 16 18
3. Dans Z/19Z calculer a = 2 , b = 2 = a2 , c = 2 = b , d = 2 = c2 et en déduire 2 .
Faire de même pour les puissances de 3.
4. Montrer que 2345 + 6789 est divisible par 19.
Exercice 2.5 Calcul rapide de puissances
1. Calculer modulo 71 : a = 32 , b = 34 = a2 , c = 38 = b2 , d = 316 = c2 et e = 332 = d2 .
2. En déduire 335 (mod 71).
3. Quel est l’ordre multiplicatif de 3 dans F∗71 ?
4. Donner un générateur F∗71 .
Exercice 2.6 Montrer que le polynôme P = X 4 + 2X 3 + 2X + 1 admet une racine dans F3 [X].
Factoriser P dans F3 [X].
Laurent Koelblen 3 màj 26 oct., 2015
2M120 ÉLÉMENTS D’ARITHMÉTIQUE LICENCE D’INFORMATIQUE UPMC 2015-2016
Exercice 2.7 Factoriser le polynôme P = 3X 3 + 4X 2 + 2X − 4 dans F5 [X] et dans F7 [X].
Exercice 2.8 Quels sont les polynômes unitaires irréductibles de degré inférieur ou égal à 4 dans
F2 [X] ? Dans F3 [X] ?
Exercice 2.9
1. Effectuer la division euclidienne de X 3 + X 2 + 1 par X 2 + X + 1 dans F2 [X]
2. Trouver une relation de Bézout entre ces deux polynômes.
Exercice 2.10 Soit k un corps et P ∈ k[X] un polynôme unitaire. Donner une définition ra-
pide de k[X]/P k[X], suffisante pour faire des calculs.
Exercice 2.11 Soit P = X 2 + X + 1 ∈ F5 , K = F5 [X]/P F5 [X] et x la classe de X dans K.
1. Quel est le cardinal de K ?
2. Soit f = ax + b ∈ K et g = cx + d ∈ K où a, b, c, d ∈ F5 . Exprimer le produit f × g sous la
forme αx + β où α, β ∈ F5 .
3. Montrer que P n’a pas de racine dans F5 .
4. Montrer que K est un corps.
5. Déterminer l’inverse de x dans K.
6. Soit a ∈ F5 ; faire la division euclidienne de P par X +a et en déduire l’inverse de x+a dans K.
7. Déterminer le plus petit entier n > 0 tel que xn = 1 (càd l’ordre multiplicatif de x dans K ∗ ).
8. Déterminer le plus petit entier m > 0 tel que (x + 1)m = 1 (l’ordre multiplicatif de x + 1).
9. Montrer que x + 2 est un générateur de K ∗ (càd : x + 2 est d’ordre le cardinal de K ∗ ).
Laurent Koelblen 4 màj 26 oct., 2015
