7 jours d'essai offerts
Cet ouvrage et des milliers d'autres sont disponibles en abonnement pour 8,99€/mois
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.