Répétitions de Mathématiques Discrètes
Année Académique 2016-2017

Chapitre 1 : Champs finis

Avant de commencer...

Opérations classiques

2+2

2*2

2-2

6/3

%(*Donne le dernier output de Mathematica*)

2*4==8

2*4==5

x=4;y=3;

x+y

x==y

Clear[x,y]

Opérations sur les listes

list={1,2,3} (*Liste ou vecteur*)

Last[list]

First[list]

On commence à numéroter à 1 dans Mathematica...

list[[0]]

list[[1]]

Length[list] (*Longueur d'une liste*)

{a,b,c,a}/.a-> 4 (*Attribue la valeur 4 à tous les a de la liste*)

{a,b,c}.{1,2,3} (*Produit scalaire*)

PadLeft[{a,b,c},6](*Ajoute des 0 à gauche pour obtenir une liste de longueur 6*)

PadLeft[{a,b,c},2]

PadRight[{a,b,c},6](*Ajoute des 0 à droite pour obtenir une liste de longueur 6*)

{{a,b},{c,d}} (*Une liste de liste est une...matrice !*)

MatrixForm[{{a,b},{c,d}}]

Det[{{a,b},{c,d}}] (*Déterminant*)

M={{a,b},{c,d}};
v={x,y};

M.v (*Produit matriciel avec un point*)

Création de liste avec Table

Table[i,{i,1,10}] (

Table[list[[i]], {i,1,Length[list]}]

Table[i+j, {i,0,2},{j,1,4}] (*On fixe d'abord i puis on laisse varier j.*)

Flatten[{{{1,0,1},{1,0,0}},{{1,0,0,0},{1,0,0,1}}},1]

Flatten[{{{1,0,1},{1,0,0}},{{1,0,0,0},{1,0,0,1}}},2]

f[x_,y_]:=x^2+y^2

f[2,3]

g:=#^2& (*Fonction avec une seule variable*)

g[4]

h:=#1^2 +#2^2&

h[2,3]

GCD[6,3] (*PGCD*)

Select[{1,2,3,4,5,6}, #>3&](*Séléctionne dans une liste les composantes > 3*)

Opérations modulaires

?Mod

Mod[8,3]

Opérations sur les polynômes

PolynomialMod[2X^6+X^4+3X+1,X^2+1] (*Reste de la division d'un polynome par un autre*)

PolynomialRemainder[2X^6+X^4+3X+1,X^2+1,X](*Reste de la division d'un polynome par un autre*)

PolynomialQuotient[2X^6+X^4+3X+1,X^2+1,X] (*Quotient de la division d'un polynome par un autre*)

Expand[(1-(X^2)+2 (X^4))(X^2+1)+3 X]

PolynomialMod[2X^6+X^4+3X+1,{X^2+1,3}] (*Reste de la division d'un polynome par plusieurs autres*)

?PolynomialMod

PolynomialGCD[X^4-4, X^4+4X^2+4](*Donne le PGCD des polynomes*)

PolynomialGCD[X^4-4, X^4+4X^2+4, Modulus->2](*Donne le PGCD des polynomes modulo 2*)

Exercice 1

Démontrer que le polynôme P (X) = X^2 + 2X est réductible sur Z_2.

Exercice 2

Démontrer que les polynômes P_1 (X) = X^7 + X + 1 et P_2 (X) = X^6 + X^3 + 1 sont irréductibles sur Z_2. Trouver un générateur du groupe multiplicatif du champ Z_2[X]/ <P_i > pour i ∈ {1, 2} .

Exercice 3

Même question, mais en travaillant sur Z_3 avec les polynômes P_1 (X) = X^3 + 2X + 1, P_2(X) = X^3 + X^2 + 2 et P_3 (X) = X^4 + X^2 + 2 .

Exercice 4

Construire la table de multiplication dans Z_5 . Les éléments non nuls forment-ils un groupe ?

Exercice 5

Construire la table de multiplication dans Z_6 . Combien d’éléments inversibles possède Z_6 et quels sont-ils ? Représenter la fonction φ d’Euler pour les entiers entre 1 et 50.

Exercice 6

Dans cet exercice, on demande de construire des champs finis.
(a) Construire F_7 , un champ à 7 éléments, et donner des générateurs.
(b) Construire F_25 , un champ à 25 = 5^2 éléments, et donner des générateurs. Pour chaque o ∈ {1, 2, 3, 4, 6, 8, 12} , donner un élément de F_25 d’ordre o .

Exercice 7

Considérons le champ F_9=Z_3 [X]/ <P> où P (X) = X^2 + 1. Vérifier que P est irréductible sur Z_3. L’élément 2X en est-il un générateur ?

Exercice 8

Générer Z_3[X]/ <P> où P(X)=X 2+X+1. S’agit-il d’un champ?

Exercice 9

Générer tous les polynômes de degré au plus d,en commençant par ceux de degré exactement d.

Exercice 10

Utiliser le théorème de Wilson pour démontrer que 127 est premier.

Théorème (Wilson) Pour tout m>1, m est premier ssi (m-1)! est congru à -1 modulo m.

Exercice 11

Illustrer la structure des champs finis avec F_24.