Capesext deuxieme composition de mathematiques 2003 capes maths capes de mathematiques

Publié par

Capes externe 2003, deuxi`eme ´epreuve page 1Notations, rappels et pr´esentation du probl`eme⁄L’ensemble des entiers naturels sera not´e N, celui des entiers relatifs Z. On notera (Z=nZ) l’ensembledes ´el´ements deZ=nZ inversibles pour la multiplication.´Etant donn´es deux entiers relatifs a et b, le plus grand diviseur commun de a et b sera not´e PGCD(a;b)ou a^b. On rappelle que a^0=a.a est dit premier avec b si a^b=1.a·bmodn signifie que a est congru `a b modulo n, c’est-`a-dire que n divise (b¡a).Un groupe (G;£) est dit cyclique s’il existe un ´el´ement a de G et un entier naturel p tel que G =' “2 3 p k1;a;a ;a ;:::;a , ou` a =a£a£:::£a (k termes); a est alors un g´en´erateur de (G;£).Pour un entier naturel n sup´erieur ou ´egal `a 2, on notera respectivement :S l’ensemble des entiers strictement positifs, inf´erieurs ou ´egaux `a n, et premiers avec n.nDble des diviseurs de n, entiers positifs (en particulier, 1 appartient `a D ).n nPLa notation d´esignera une somme ´etendue `a tous les ´el´ements d de D .nd2DnEnfin, on notera `(n) le cardinal de S .nLa premi`ere partie du probl`eme a pour but d’´etablir une identit´e due `a Euler concernant la fonction `,`a l’aide d’un raisonnement probabiliste.Dans la deuxi`eme partie, on ´etudie le groupe des ´el´ements inversibles pour la multiplication dansZ=nZ,et on montre que, si n n’a qu’un seul diviseur premier, alors ce groupe est cyclique.La troisi`eme partie introduit la notion de nombres ...
Publié le : jeudi 21 juillet 2011
Lecture(s) : 275
Nombre de pages : 6
Voir plus Voir moins
Capesexterne2003,deuxiemeepreuve
Notations,rappelsetpresentationduprobleme
page 1
LensembledesentiersnaturelsseranoteN, celui des entiers relatifsZ. On notera (Z/nZ) l’ensemble deselementsdeZ/nZinversibles pour la multiplication. Etantdonnesdeuxentiersrelatifsaetb, le plus grand diviseur commun deaetb(seranotePGCDa, b) ouab. On rappelle quea0 =a. aest dit premier avecbsiab= 1. abmodnsignie queautrsgoncaebmodulonrediequstea--c,ndivise (ba). Un groupe (G,×ntmeeelneutsixeliseuqilcy)estditcadeGet un entier naturelptel queG= © ª 2 3p k 1, a, a, a, . . ., a,oua=a×a×. . .×a(ktermes) ;aesuoralstrenegn(edruetaG,×). Pour un entier naturelnroeueguaalon2,etonerarcepsevit:emtnspueir Sni,sfitisoptnemetgaeourseurienfmelbesnltricerssentiedesxuan, et premiers avecn. Dnl’ensemble des diviseurs denosspifiten,ertiitrappa1atnertpaens(r,ieulicDn). P LanotationdesigneraunesommeetendueatousleselementsddeDn. dDn Enn, on noteraφ(n) le cardinal deSn.
LapremierepartieduproblemeapourbutdetabliruneidentitedueaEulerconcernantlafonctionφ, alaidedunraisonnementprobabiliste. Dansladeuxiemepartie,onetudielegroupedeselementsinversiblespourlamultiplicationdansZ/nZ, et on montre que, sinn’a qu’un seul diviseur premier, alors ce groupe est cyclique. Latroisiemepartieintroduitlanotiondenombrespseudo-premiersfortsetseproposedendonnerune caracterisationalgorithmiquesurunecalculatriceprogrammable. Enn,laquatriemepartieapourobjetletudedenombresappelesnombresdeCarmichael,presentant dessimilaritesaveclesnombrespremiers,etsetermineparlapresentationduntestprobabilistepourla detectiondenombrespremiers.
Capesexterne2003,deuxiemeepreuve
Partie I
page 2
1.Onconsideredanscettequestionununivesprobabilise(, B, PuednirrantcontmeneeveL.) evenementErestonaeE. (a) SoientA1etA2tsanndpenitucedenom;sreveuqrertdeuxveeenemtnisdneA1etA2sont independants. (b)Generalisation:soitkun entier naturel non nul etA1,A2, .. .,Akktnemelleutumenementsevindependantsde. (I) MontrerqueA1,A2. .,, .Akndtse.pnetndianso (II)MontrerparrecurrencequeA1,A2, .. .,Akdnitnostnadnepes. Dans toute la suite de cette partie,ntanrlerupuseireedgnsineeuientneteuXl2aeagruuo variablealeatoiresur,prenantsesvaleursdanslensemble{1, . . ., n}ereequidemani,borpelba 1 cest-a-diretellequepourtouti= 1, . . ., n, on aP(X=i) =. n 2.OnconsiderelevenementA1eXts:ltmuleip2deletvemenetneA2: “X est multiple de 5”. (a) Onsuppose quen= 100. CalculerlesprobabilitesdesevenementsA1etA2.A1etA2nadn?stdnisepet-ilson (b) Onsuppose maintenant quen= 101. Reprendre les questions du (a) dans ce cas. k Q αi 3.Onsupposequeladecompositionenfacteurspremiersdentecrisn=pelso,uαisont des i i=1 entierssuperieursouegauxa1. Enn, pourientier naturel, 1ik,AiislbidivperaveementenstXedgiselenpi”. (a)SoitAlevenement:Xestpremieravecn” ;exprimerP(Aidaeedal)netφ(n). 1 (b) MontrerqueP(Aipour tout entier) =i, 1ik. pi (c) Montrerque les (Ai)1ikindmentellemututnos.sadtnpene (d)ExprimerAalaidedesAi. µ ¶ k Q1 (e)Endeduirequeφ(n) =n1(E). p i=1i 4.Onseproposederetrouverlegaliteprecedente(E)paruneautremethode;soientpetqdeux entiers naturels premiers entre eux. ½ Spq→ {0, . . ., p1} × {0, . . ., q1} Onconsiderelapplicationh:uoa(resp.b) est le reste de r7→(a, b) la division euclidienne derparp(resp. parq). (a) Montrerqueh(Spq) est inclus dansSp×Sq. (b) Montrerquehest injective. (c) Justierl’existence de deux entiersαetβdeZtels que :αp+βq= 1. Soit (a, b) un couple deSp×Sq. On notex=αpb+βqa; montrer quexamodpet xbmodq. EndeduirequelimagedehestSp×Sq, puis queφ(pq) =φ(p)φ(q). (d)Alaidedunerecurrencesurlenombredediviseurspremiersdenteorvurelarolsegalite,r (E). 5.IdentitedEuler: (a) Soitdun diviseur deneta(; montrer que PGCDun entier naturel non nula, n) =dsi, et n seulement si, il existe un entierktel quepremier aveca=kd.Endsonbmereddeiuerel d entiersatels que 1anet PGCD(a, n) =d.
Capesexterne2003,deuxiemeepreuve
page 3
(b) Pourtout entierddiviseur den, on noteCdtnemene(DCGPvelX, n) =d”. ExprimerP(Cdlia)aededn,det de la fonctionφ. ³ ´ P1n (c)Endeduirequeφ= 1 (rappel :Dnnote l’ensemble des diviseurs dendansN). n d dDn n (d) Montrerque l’applicationuesruiqduivai,uttoddenassocieu(d) =est une bijection de d P Dnˆe-muisltron.Mmeenraqdueφ(d) =neduEeli(edtnti.r) dDn
Partie II
nnusritneottnuojutaeetonepuorgudedutelsteetiarepttceteedojb2al,agloueieurperersu ((Z/nZ),×ed)elsmeesdnteZ/nZinversibles pour la multiplication. Onrappellequecetensembleestcomposedesclassesmodulondes nombres premiers avecn. On pourra donc remarquer queφ(n) =card((Z/nZ) ). La classe d’un entieraanerseetoa˙ .
A)Desresultatsgenerauxsurlesgroupesetlesanneaux.
1. Soientaetbdeleeuxtitamuomf(udstnemcuaennanA,+,×) etnun entier naturel non nul. n n Montrer quebaest divisible parba. n n Donner le quotient debaparbasous forme de somme. 2. Montrerque (Z/nZ,+,×) est un corps si, et seulement si,nest premier. 3.Factorisationdepolynoˆmes. (a) SoitPylopnuededomnˆeregksnasueirupreagluoeacoea1,ntsdcieZ/nZ,uonest un entier premier. Montrer quePadmet au pluskrpneonisraraurporusecnerrucerraracines(onk). 2 (b)Determiner,dansZ/6Zynolmeˆoneciupsdsearl,P(X) =XX. Que peut-on en conclure? 2 ˙ (c) Trouver,dansZ/6Z[X], deux factorisations distinctes deXXsous la forme (X˙a)(Xb). 4. Onrappelle que sixntdemetelesinepuorgnuG, l’ordre dexest le plus petit entier naturelk k non nul tel quexelmelntnertue1,=u1oesdneigedeG. (a) SoitxemtnleeunedG, groupe ni de cardinaln; montrer que, sikest l’ordre dex, alors © ª k1 l’ensemble 1, x, . . ., xest un sous-groupe deG. n Endeduirequelordredexdivise le cardinal deG, et quex= 1. (b) Sipest un entier naturel premier etxun entier naturel non divisible parp, montrer que p1 x1 est divisible parp.
B) Etude du groupe((Z/nZ),×)quandnest premier.
On suppose dans cette sous-partie quen.3iSugelaaroeurieuprsieemrpreitnenutsedest un entier naturelnonnuletstrictementinferieuran, on noteζ(dsleeredtndseem(e(nomb)leZ/nZ),×) d’ordre d. P 1. Montrerqueζ(d) =n1. dDn1 2. Soitdun diviseur den1 et soitalenemeedtn((u˙Z/nZ),×) d’ordred, s’il existe. ˙ d a˙iiasnireev˙a= 1. © ª ˙ ˙ d2 3d1 (a)MontrerquelensembledesracinesdupolynˆomeX1 est, dans (Z/nZ1) ,,˙a,˙a ,˙. . .,a ,˙a.
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.