Solutions des Exercices du cours de Theorie de l'Information et Codage cours du mai

Description

Solutions des Exercices du cours de Theorie de l'Information et Codage cours 11 du 17 mai 2011. 1. Pour tout entier positif m, on definit ?(m) comme le nombre d'entiers positifs ≤ m qui sont premiers avec m. (i) Montrer que ?(m) = m ∏ p|m ( 1? 1p ) , ou les p sont premiers. (ii) Montrer que si a ?m = 1 alors a?(m) ? 1(mod m). • On a clairement pour p premier: ?(p) = p? 1 et plus generalement pour k ≥ 1, ?(pk) = pk ?pk?1. Pour deux nombres premiers entre eux p et q, on ?(pq) = ?(p)?(q). Donc pour m = ∏? i=1 pkii ou les pi sont des nombres premiers distincts, on a: ?(m) = ? ∏ i=1 pkii (1? 1 pi ) = m ? ∏ i=1 (1? 1pi ). • Les entiers b premiers avec m inferieur a m constituent un sous-groupe multiplicatif de Z/mZ (l'inversibilite decoule de l'identite de Bezout). Ce sous-groupe a pour ordre ?(m) et d'apres le Theoreme de Lagrange, l'ordre de tout element de ce groupe divise ?(m) d'ou le resultat.

• qm ?


• ms avec ms


• polynome minimal


• racines de l'unite


• nom polynome


• code reed-solomon


• polynome generateur


• polynome minimal de ?s defini

Sujets

• Polynôme minimal
• Racine de l'unité

Informations

• Publié par: pefav
• Publié le: 01 mai 2011
• Nombre de lectures: 65
• Langue: Français

Extrait

SolutionsdesExercicesducoursdeThe´oriedel’InformationetCodage cours 11 du 17 mai 2011. 1. Pourtout entier positifmtinefid´on,ϕ(m) comme le nombre d’entiers positifs≤mqui sont premiers avecm. (i)Montrer que   Y 1 ϕ(m) =m1−, p p|m ou`lesp(ii) Montrer que sisont premiers.a∧m= 1 alors ϕ(m) a≡1(modm). k •On a clairement pourppremier:ϕ(p) =p−e´´nrelameneptuor1etplusgk≥1,ϕ(p) = k k−1 p−p. Pourdeux nombres premiers entre euxpetq, onϕ(pq) =ϕ(p)ϕ(qpour). Donc Q ℓ k i m=pole`usp i sont des nombres premiers distincts, on a: i=1 i ℓ ℓ Y Y 1 1 k i ϕ(m) =p(1−) =m(1−). i p i p i i=1i=1 •Les entiersbpremiers avecminf´ur`aeriemconstituent un sousgroupe multiplicatif de Z/mZi’l(rdede´ezoBe).utsoCegsupuoropaerorunversibilit´ed´eocludelei’edtntiϕ(m) etd’apre`sleTh´eor`emedeLagrange,l’ordredetoute´l´ementdecegroupediviseϕ(m) d’o`uler´esultat. 2. Commedans le cours,mest l’ordre multiplicatif deqmodulonMontrer que les racines. (i) n m∗n deX−1 forment un sousgroupe cyclique deF(q) .Montrer que les racines deX−1 m constituent le groupe multiplicatif d’un corps ssin=q−1. m∗ •del’inessracueleiaqtlfeitdfetlpiilacougrmupenstusouitsnneuttinuoce´F(q) est ´evident.Soitαd’ordre maximal dans ce sousgroupe, disonsr. Commedans le cours, a′ onmontrequepourtoute´le´mentβd’ordeℓ, on aℓ|r. Pourπpremier, sir=π ret a′ b′′ ′π ℓb′ ℓ=π ℓavecπ∧r= 1 etπ∧ℓ= 1, alorsα βest d’ordreπ rdoncb≤aetℓ|ra. On r donctouteslesracinesdel’unit´equisatisfontX−xeueutdadx`1meom,c=0onssleel distinctes, on ar=n. m •Sin=q−e´tinu’ledsenicasrlesit,enemrsveenttituconsalri.enIitnosect’implica1,l m le groupe multiplicatif d’un corps.Ce corps est fini, contenu dansF(q) et contenu dans m m aucun coprs plus petit, c’est doncF(q) etn=q−1. 3.Montrerquepourlade´finitionplusg´en´eraledepolynˆomeminimalvueencours,lesproprie´te´s (M1)(M6) sont encore vraies. (s)s •SoitM(Ximindealnˆlyemom)elopα:rap´dinfie Y (s)i M(X) =(X−α). i∈C s

1