Cours-arith

Description

Universite Denis Diderot Paris 7, Semestre Fevrier-juin 2005Cours d’arithmetique (M1)(Marc Hindry : [e-mail] )PLANPremiere partie : structures nies page 3Rappels sur Z/mZ, (Z/mZ) et F . page 3qLa structure des groupes (Z/mZ) et F . page 5qSymboles de Legendre et Jacobi). page 7Sommes de Gauss. page 9Applications au nombre de solutions d’equations. page 12Applications I : algorithmes, primalite et factorisation. page 16Algorithmes de base. page 16Cryptographie, RSA. page 17Test de Primalite (I). page 19Test de Primalite (II). page 22Factorisation. page 25Applications II : Codes correcteurs. page 28Generalites sur les codes correcteurs. page 28Codes lineaires cycliques. page 31Deuxieme partie : Algebre et equations diophantiennes. page 36Sommes de carres. page 36Equation de Fermat (n = 3 et 4). page 412 2Equation de Pell-Fermat x dy = 1. page 43Anneaux d’entiers algebriques. page 49Troisieme partie : theorie analytique des nombres page 55Enonces et estimations “elementaires”. page 55Fonctions holomorphes (resume/rappels). page 58Series de Dirichlet, fonction (s). page 61Caracteres et theoreme de Dirichlet. page 63Le theoreme des nombres premiers. page 681BIBLIOGRAPHIE (commentee subjectivement)D. Perrin, Cours d’algebre, Ellipses. (excellent livre particulierement recommande pour la preparation al’agregation)M.Demazure, Cours d’algebre,Cassini,Paris,1997. (surtout pour la partie ...

Informations

• Publié par: Zikes
• Nombre de lectures: 57
• Langue: Français

Extrait

Universit´eDenisDiderotParis7,SemestreF´evrier-juin2005 Coursd’arithm´etique(M1) (Marc Hindry : [e-mail] )

PLAN

Premie`repartie:structuresfinies Rappels surZ/mZ, (Z/mZ) ∗ etF q . La structure des groupes (Z/mZ) ∗ etF q . Symboles de Legendre et Jacobi). Sommes de Gauss. Applicationsaunombredesolutionsd’e´quations. ApplicationsI:algorithmes,primalit´eetfactorisation. Algorithmes de base. Cryptographie, RSA. TestdePrimalit´e(I). TestdePrimalite´(II). Factorisation. Applications II : Codes correcteurs. Ge´neralite´ssurlescodescorrecteurs. ´ Codeslin´eairescycliques. Deuxi`emepartie:Alge`breete´quationsdiophantiennes. Sommes de carres. ´ Equation de Fermat (n= 3 et 4). Equation de Pell-Fermatx 2 −dy 2 = 1. Anneauxd’entiersalge´briques. Troisi`emepartie:the´orieanalytiquedesnombres Enonc´esetestimations“´el´ementaires”. Fonctionsholomorphes(r´esume´/rappels). Se´riesdeDirichlet,fonctionζ(s). Caracte`resetthe´ore`medeDirichlet. Leth´eor`emedesnombrespremiers.

1

page 3 page 3 page 5 page 7 page 9 page 12 page 16 page 16 page 17 page 19 page 22 page 25 page 28 page 28 page 31 page 36 page 36 page 41 page 43 page 49 page 55 page 55 page 58 page 61 page 63 page 68

BIBLIOGRAPHIEenmmeet´bjsutiecoc(evemtn) D. Perrin,Coursd’alg`ebre, Ellipses. (reivtlenulicrtpallecxepournd´e´epalaprmene`iremoamrtceon`arati l’agregation) ´ M. Demazure,reebg`ald’rsouC, Cassini, Paris, 1997. (surtout pour la partie “structures finies” et algorithmes) K. Ireland, M. Rosen,A classical introduction to modern number theory 84,, Graduate texts in math. Springer, 1982. (comme le titre l’indique. . .) P. Samuel,´ethserbmonseedquriebg´alieor (, Hermann.`duakeniDedeuadxanneelesraitteunpivnnuuea pluse´leve´quececours–deuxie`mepartie–maissibiene´crit.Unclassique)

A. Baker,Transcendental Number Theory (, Cambridge University Press, 1975.esluttopresi`emreseapegs de´montrentlatranscendancedeeetπdeluvierseptulss,lerestecp´liiaes´) . . .semtrvilrpse´fe´s:er´ee G. H. Hardy and E. M.Wright,An introduction to the theory of numbers, Oxford University Press, 4th ed.,1960. (tdarsuesladeupplatnenoitpse´rnive`aunbressnomeiede´roedhtejstt-sa`etr,eriatneme´le´ua trayant!) J. P. Serre,urCoa’dshtirte´meuqi (, Presses Universitaires de France, 1970.Un classique insurpassable. - J’utiliserailed´ebutsurlescorpsfinis,laloid´ciocit´eetlapartiethe´orieanalytiquepourless´eries e re pr etthe´ore`medeDirichlet) Borevich, Shafarevich,T´hresnombedeseori(traduit du russe), Gauthier-Villars. (,iuqer`etrUnivilolsj mˆemes’ild´emarre`aunniveau´ele´mentaire,estd’unniveaupluse´leve´quececours)

2

Universite´DenisDiderotParis7,SemestreF´evrier-juin2004 Coursdemaıˆtrise:arithm´etique Premie`repartie:StructuresfiniesZ/nZ,(Z/nZ) ∗ , F q , F ∗ q . A. Rappels surZ/nZ, (Z/nZ) ∗ ,F q ,F q ∗ . B. La structure des groupes (Z/nZ) ∗ etF q ∗ . C. Symboles de Legendre et Jacobi. D. Sommes de Gauss. E.Applicationsaunombredesolutionsd’´equations. A. Rappels sur Z/nZ,(Z/nZ) ∗ , F q , F q ∗ . Lath´eoriedescongruencesame`ne,pourchaqueentiersn≥2nn’arlreueaa`,e´disnocZ/nZainsi que le groupedesese´le´mentsinversibles(pourlamultiplication)(Z/nZ) ∗ . Pour chaque puissance d’un nombre premierq=p f , il existe un corps fini de cardinalqnu,ueiqis`aoromisphemrpe`,son´teF q . Nous rappelons laconstructiondecesobjetsetpr´ecisonsleursprincipalespropri´ete´s. Le groupeZfinin.emtne)itrun´el´eendr´epagne(euqilcyctseiqus)`eprmeisphorsimo(ea`orpuuqge’uniestl Tous ses sous-groupes sont du typemZpourm≥0. L’ensembleZniolumenu’dtacilpitgalest´emunimente quienfaitunanneaucommutatif.Danscetanneauonalanotiondedivisibilit´eetdePGCDetPPCM. Dans le cas deZla notion d’ae´dil´dirdunp.Oteeultneecafemelieccedeavıncico¨uoep-srgseuollde n e the´or`emesuivant The´ore`me.(´Bze)utoSoitm n∈Zet soitdleur PGCD, alors il existeu v∈Ztels que d=um+vn. Preuve. L’ensembleH:=mZ+nZ={um+vn|u v∈Z}est clairement un sous-groupe; il est donc de la formed 0 Zet il existeu vtels qued 0 =um+vn. Commeddivisemetn, on voit queddiviseum+vn=d 0 maism neitrappaa`tnennHdoncd 0 divisemetndoncd 0 vise´egadielemtndet on conclut quedZ=d 0 Z (onauramˆemed=d 0 si l’on a pris soin de les prendre tous les deux positifs). Le groupeZ/nZqinu’ltse`argeuepuolcyceuqins)i.e.engendr´epsimorohpsiemrpe`´´eelntme`as(nura e´l´ementd’ordrenateun´errsutida`e´gse´reesOn.ejd´utpe Proposition.Soitm∈Zetm¯sa classe dansZ/nZvinaetsse´´tseusispropri,lestroesntlevauieqt´on (i)L’e´le´mentm¯dreateun´erng´eestuZ/nZ. (ii)Les´ele´mentsmetnsont premiers entre eux. (iii)L’e´le´ment¯mest inversible modulonc,e’ts`-a-direqu’ilexistem 0 ∈Ztel quemm 0 ≡1 modnou encore mm 0 = 1∈Z/nZ. ¯ ¯ Preuve. Supposons quem¯ engendreZ/nZalors il existem 0 ∈Ztel quem 0 ¯m= 1∈Z/nZ; ainsimm 0 ≡ 1 modnce qui signifie quemest inversible modulon. Simm 0 ≡1 modnalorsmm 0  += 1anet doncm est premier avecn. Simest premier avecnh´etr`eoedem´eeBolad,srrpa’lse`oztui,elixtsea btels que am+bn= 1 doncam¯ = 1∈Z/nZet doncm¯ engendreZ/nZ. Exercice. Montrer que si, dans un groupe commutatif, l’ordre dex 1 estd 1 , l’ordre dex 2 estd 2 avecd 1 et d 2 premiers entre eux, alors l’ordre dex 1 x 2 estd 1 d 2 ´rerlage.tnoM,dsisuanenemuetquq,ecyilpucegnor l’ordre dex 1 estd 1 , l’ordre dex 2 estd 2 durerd’osloral,sous-groupeengenrde´aprx 1 etx 2 ga´eulaets PPCM ded 1 etd 2 . Legroupedese´l´ementsinversiblesdel’anneauZ/nZegt´es`aal (Z/nZ) ∗ ={m¯∈Z/nZ|mest premier avecn}={urteesdeng´ra´eZ/nZ}. De´finition.On noteφ(n) := card(Z/nZ) ∗ l’indicatrice d’Euler. 3

Onende´duitfacilementque,sipest premier,φ(p r ) =p r −p r−1 = (p−1)p r−1 dleeL.enullccara´eeng´φ(n) sefaitgrˆaceaulemmeclassiquesuivant. Proposition.(Lemme chinois)Soitm n∈Z, supposonsmetnpremiers entre eux, alors les groupes Z/mnZetZ/mZ×Z/nZsont naturellement isomorphes. plus cet isomorphisme est aussi un isomorphisme De d’anneauxet,parconse´quentinduitunisomorphismeentre(Z/mnZ) ∗ et(Z/mZ) ∗ ×(Z/nZ) ∗ . En particulier φ(mn) =φ(m)φ(n). Preuve.Conside´ronsl’applicationf:Z→Z/mZ×Z/nZaprdonn´eex7→(xmodm xmodn un). C’est homomorphisme de groupe de noyau ppcm(m n)Z`ouu,’dejtcenninio ˆ f:Z/ppcm(m n)Z,→Z/mZ×Z/nZ. Commemetnppmc(eexuo,anstnooppusrsietreness´emprm n) =mnourdesraet,pilanidracedsnosie,t´ ˆ l’homomorphismefernuˆttedio.Demismeorphisomi`anegern´´ealeris,eAetBsont des anneaux, on a (A×B) ∗ =A ∗ ×B ∗ `in.iortse’d`oludaue x eme as Rappelonsque,d’apr`esleth´eor`emedeLagrangel’ordred’unsous-groupedivisetoujoursl’ordredugroupe. La description des sous-groupes deZ/nZest assez simple. Proposition.Pour chaque entierd≥1divisantn, il existe un unique sous-groupe deZ/nZd’ordred, c’est lesous-groupecycliqueengendre´parlaclasseden/ddansZ/nZ. ¯ Preuve. Supposonsn=dd 0 ´le´’lsrolantmex=d 0 ∈Z/nZest d’ordredcar clairementdx= 0 et, si e cx= 0 alorsndivisecd 0 doncddivisec. Soit maintenantHun sous-groupe deZ/nZd’ordred. Notons s:Z→Z/nZ Onla surjection canonique. sait ques −1 (H) =mZteesenng´edrrpamdoncHetseegne´rdn par ¯m∈Z/nZ. On adm 0 donc¯ =ndivisedmdoncd 0 divisemdonc le sous-groupeHest contenu dans le ¯ sous-groupe engendre pard 0 ncdoetca`lage´rg-suose.oupe ´ Comme application, on peut en tirer la formule (que nous utiliserons plus bas) n= X φ(d). d|n Eneffeton´ecritZ/nZd(noinuemmocseenes)dteinjoisemtnlee´ds´’bmelrdresd’odpourddivisantn. Le nombredeces´ele´mentsestlenombredege´ne´rateursdel’uniquesous-groupedecardinald, et comme ce dernier est isomorphe aZ/dZeurseste´´nretamorbdegenel,φ(d). ` Un corps finike`aegalin´euqfiesiit´treectdacarirsaenem´ntsseceepun nombre premier et contient donc Z/pZ=F p ’phh(olromommeisZ→ka pour noyaunZavecn >0 et commeZ/nZ,→kon doit avoir n dimension depremier). LaksurF p , commeF p -espacevectorielsefitin,ee´agelida`snosfet donc card(k) =p f . On observe que card(k ∗ ) =p f −nemeedst´el´slesctou1donk ∗ ´fiiretenx p f −1 = 1 et donc v touslese´le´mentsdekifientv´erx p f =xa`sprocnrustonec’undioctne´deptuernudeiunver.Intonseme p f me´le´ondie`ernueetxneisentsainsi:onconsKdeF p =Z/pZuqalelleopelˆnylmnosdeaP=X p f −X estscind´eetonposek:={x∈K|P(x) = 0}. CommeP 0 (X) =−1, les racines dePsont simples et card(k) = deg(P) =p f ; de pluskest un sous-corps deKt´aciscer,eararncuqitep, l’application “Frobenius” de´finieparφ:x7→x p isphoromomnhtuesemeˆmedsprocedemqueφ f `a-dest-.C’no:aeu’lriqe (xy) p =x p y p et (x+y) p =x p +y p .

D’apr`eslesthe´ore`mesge´n´erauxdeth´eoriedescorpslecorpskde cardinalp f dosteqieucnnumoroa`simephis pr`es,onlenoteF pf us´nnenocsledanaR´esumon.e.c´ Th´eor`eme.Soitppremier etf≥1, notonsq=p f . Il existe un corps fini de cardinalqueiqun,a` isomorphismepre`s.Les´ele´mentsdeF q sontlesracidsenlopuoˆnyemX q −X∈Z/pZ[X]. 4