ÉCOLE NATIONALE DES PONTS ET CHAUSSÉES. ÉCOLES NATIONALES SUPÉRIEURES DE L’AÉRONAUTIQUE ET DE L’ESPACE, DE TECHNIQUES AVANCÉES, DES TÉLÉCOMMUNICATIONS, DES MINES DE PARIS, DES MINES DE SAINT-ÉTIENNE, DES MINES DE NANCY, DES TÉLÉCOMMUNICATIONS DE BRETAGNE. ÉCOLE POLYTECHNIQUE (Filière TSI).
CONCOURS D’ADMISSION 2002
ÉPREUVE DE MATHÉMATIQUES DEUXIÈME ÉPREUVE Filière MP (Durée de l’épreuve:4 heures) (L’usage d’ordinateur ou de calculette est interdit).
Sujet mis à la disposition des concours : Cycle International, ENSTIM, ENSAE (Statistique), INT, TPE-EIVP.
Les candidats sont priés de mentionner de façon apparente sur la première page de la copie : MATHÉMATIQUES 2-Filière MP.
Cet énoncé comporte 7 pages de texte. Si, au cours de l’épreuve, un candidat repère ce qui lui semble être une erreur d’énoncé, il le signale sur sa copie et poursuit sa composition en expliquant les raisons des initiatives qu’il est amené à prendre.
Il est conseillé aux Candidats de lire le problème en entier. Les deuxième et quatrième parties peuvent être abordées indépendamment des parties précédentes.
Le crible d’Ératosthène donne un algorithme qui permet de savoir si un entier est premier ou non. Il est par suite possible d’indexer la suite des nombres premierspi,i1, 2,: p12,p23,p35, ... Dans tout le problème la lettrepest réservée aux nombres premiers. Étant donné un réelx, sa partie entièrexest l’entiernqui vérifie la double inégalité suivante : xnxn1. Étant donné un réelx, supérieur ou égal à 2,x2, il existe un entierNégal au rang du plus grand nombre premierpNinférieur ou égal àx pNsupppx
- 1 / 7 -
Première partie
Le but de cette partie est de dmontrer que la suite des nombres premiers est illimite et d' tudierla nature de la srie de terme gnral 1/pi,i1, 2,.
I-1.La suite des nombres premiers est illimite: Dmontrer que la suite des nombres premiers est illimite en considrant, par exemple, pour nnombres premiersp1,p,pndonns, l'entierQdfini partir de cesnnombres premiers 2, par la relation suivante : n Q p1.p2..pn1pi1. i1
Dans toute la suitenest un entier suprieur ou gal 2n2,sun rel donnstrictement positifs0
I-2.EnsembleMn: a. Justifier la relation suivante :
1 1 1 1s . n k s n k0
b. Soientaetbdeux entiers, diffrents l' un de l' autre, tous les deux suprieurs ou gaux 2 (ab,a2,b2) ; dmontrer que la srie double de terme gnralu,i0, 1, 2,, i j j0, 1, 2,, dfinipar la relation suivante 1 u,i0, 1, 2,,j0, 1, 2,. i j i sj s a.b est sommable. Dterminer sa sommeS. Soientp1,p,pnlesnpremiers nombres premiers,Mndes rels obtenus enl' ensemble 2, s ss considrant tous les produits des relsp1,p2,,pnlevs des exposantsi, 1inpositifs ou nuls., entiers s1s2sn Mnmmp1.p2..pn,iN.
s1s2snn c. Dmontrer que l'application1,2, ...,n p1.p2..pn, deNdans Mnindexer les relsil est possible d', estinjective. En dduire qu'mdans l' ordre croissant : l' applicationimiest strictement croissante deNsurMn. Exemples :de la suit crire la suite des 12 premiers termesemi iNlorsque le relsest gal 1 et l' entierngal 2 puis 3.
Il est admis que la srie de terme gnralvi1/mi,iN, estconvergente ; sa somme est 1 dsigne par le symbole :malina b, le rsultat plus gnral. Comme le laisse prsager l' mMn ci-dessous est vrai et est admis : n 1 1 11 1s . m mi pi i1mMni1
- 2 / 7 -
Soitfnla fonction dfinie sur la demi-droite ouverte0,par la relation suivante : n 1 1 fns1s. pi i1
SoitNle rang du plus grand nombre premier infrieur nNsupipin. d. Dmontrer l'ingalitsuivante : n N 1 1 1 s1s. kpi k1i1 Retrouver, en donnant une valeur particulire au rels, le rsultat : la suite des entiers premiers est illimite. Dterminer, en supposant le relsinfrieur ou gal 10s1entier, la limite, lorsque l' ntend vers l' infini, de l' expressionfnsintroduite ci-dessus. Il est admis, puisque la suite des nombres premiers est illimite, qu'tout relxsuprieur ou gal 2x2, peuttre associun entierNtel que le relxsoit encadrpar les nombres premierspNetpN1: pNxpN1.
e. tablir, lorsque le relsest strictement suprieur 1s1encadrement ci-dessous :, l' n N 1 1 11 s1s. s kpik k1i1k1 En dduire, poursexpression1, la limite de l'fnsentierintroduite ci-dessus lorsque l'n tend vers l' infini. I-3.Srie de terme gnral1/pi,i:1, 2, ... Dduire des rsultats ci-dessus la nature de la srie de terme gnralvi,idfini1, 2, ..., par la relation suivante. 1 viln 1. pi En dduire la nature de la srie de terme gnral : 1 wi,i1, 2, .... pi Quelle conclusion qualitative est-il possible d'en tirer sur la rpartition des nombres premiers ? I-4.Fonction: Soitla fonction limite de la suitefn. Dmontrer que cette fonction, dfinie d'aprs la question I-2.e sur la demi-droite ouverte1,par la relation ci-dessous,est continûment drivable. N 1 1 1 slimss 1. Npik i1k1
- 3 / 7 -
Deuxième partie Le but de cette partie est d'tablir une majoration du produit des nombres entiers premiers infrieurs ou gaux un entier donnnencadrer le plus petit commun multiple de tous leset d' entiers infrieurs ou gaux cet entiern. Soit toujoursnun entier suprieur ou gal 2n2,Nle rang du plus grand nombre premier infrieur ou gal n; soitPnle produit des nombres premiers infrieurs ou gaux n: N pNn pN1,Pnpi. i1
II-1.Majoration duproduitPndes nombres premiers majors par un entiern: a. Construire un tableau donnant pour les valeurs 2, 3, 4 et 5 de l'entiernles valeurs de n N,pN,Pn, 4 . n b. Vrifier que, si l'entiern1 n' est pas premier, l' ingalitPn4 impliquel' ingalit n1 Pn14 . c. L'entiern1 est premier dans cet alina ; justifier l' existence d' un entiermtel que : 2m1n1. Dmontrer que tout nombre premierpcompris entrem2 etn1m2pn1 m divise le coefficient du binômeC. tablir la majoration suivante : 2m1 m m C4 . 2m1 m1n1 En dduire que l' ingalitPm14 impliquel' ingalitPn14 . d. En dduire, pour tout entiernmajoration :2, la N n Pnpi4 . i1
Soitdnle plus petit commun multiple de tous les entiers 1,2, 3,...,n. II-2.Une expression du p.p.c.m.dn: Dmontrer que le p. p. c. m.dnest gal au produit des nombres premierspi, infrieurs ou gaux l' entiern, levs des puissancesigales aux parties entires du rapport lnnsur lnpi; c' est--dire: N lnn i pNnpN1,dnpi, avec:i. lnpi i1
- 4 / 7 -
II-3.Une minoration du p.p.c.m.d: 2n1 tant donnun entiernsuprieur ou gal 2n2, soitIndfinie par lal' intgrale relation suivante : 1 n n Inx1xdx. 0 a. Dmontrer la majoration : 1 In. n 4
b. Dmontrer que le p. p. c. m.dest divisible par tout entiernkl' entier1, lorsquek 2n1 varie de 0 n0e le produitd kn. En dduire qu2n.Inest un entier en considrant, par 1 n exemple, une expression deInobtenue par dveloppement de1x.
Dmontrer, l'aide de la majoration de l'intgraleInminoration du p. p. c. m., uned. 2n1
Troisième partie Le but de cette partie est d'tudier les deux fonctionsetdfinies ci-dessous pour en dduire un encadrement l'infini du relx. Pour tout relxsuprieur ou gal 2x2,xest gal au nombre des nombres premiers infrieurs ou gaux au relx. N pNxpN1,xN1. i1 Pour tout relxsuprieur ou gal 2x2,xest gal la somme des logarithmes des nombres premiers infrieurs ou gaux au relx. N xpN1,xlnpi. pN i1 Plus gnralement : tant donne une suite relleAak, soitHAla fonction dfinie sur k1 la demi-droite ferme1,, par la relation suivante : HAxest nul sur l'gal, pourintervalle 1,2 ,x2, la somme des termes de la suiteA dont les rangs sont infrieurs ou gaux au rangNdu plus grand nombre entier premier infrieur ou gal x: 0, si1x2, N HAx ak2, sixetpNxpN1. k1
III-1.Un rsultat auxiliaire: r une suiteAai Prciser, pouidonne, sur quels intervalles la fonctionHAest continue. 1 Quels sont ses points de discontinuit? Prciser en ces pointsxla valeur deHAxHAx0.
- 5 / 7 -
Soitf2,une fonction relle, dfinie et continûment drivable sur la demi-droite ferme, et une suite relleAai; dmontrer la relation suivante : pour tout relxcompris entrepN i1 etpN1,pNxpN1il vient : N x aifpiHAxfxHAtf´tdt. 2 i1
III-2.Une majoration de la fonction: a. Dmontrer la majoration suivante de la fonction: xxln 4.
b. tablir en choisissant, dans la relation tablie la question prcdente, comme suiteA, la suite lnpk,ket comme fonction1, 2, ...,f, lafonctionx1/ lnxingalitsuivante :, l' x x dt xln 4. 2 lnx2 lnt
c. Dmontrer la convergence vers 0, lorsque le relxinfini, de la fonctioncroît vers l'Rx suivante : x lnx dt Rx.. x2 lnt 2 Indication : introduire, pourx4 , les intgrales de 2 xet dexx.
d. En dduire l'existence d'un relx0tel que, pour tout relxsuprieur ou gal x0, la fonctionvrifie la majoration suivante : x x4 ln2 . lnx
III-3.Une minoration de la fonction: En utilisant par exemple la minoration du p. p. c. m.dobtenue la question II-3, 2n1 dmontrer qu'il existe un relx1tel que, pour tout relxsuprieur ou gal x1, la fonction vrifie la minoration suivante : ln 2x x. 2 lnx
Ces deux rsultats sont cohrents avec le flthorme des nombres premiersfltabli par Hadamard et de La Valle Poussin en 1896, qui affirme que la fonctionest quivalente l' infinila fonctionxx/ lnx.
- 6 / 7 -
Quatrième partie
Soit, dans toute cette partie, un entierndonnn2. L'anneauZ/nZest l'ensemble quotient de l'anneauZdeux entiers relatifs sont quivalents siquivalence : ºpar la relation d' leur diffrence est divisible par l'entiernº .Classiquement un lment deZ/nZ, uneclasse d' quivalence,est notea,atant un reprsentant de cette classe. Soitla fonction qui, l'entiern, associe le nombre d'lments inversibles deZ/nZ.
IV-1.Thorème d'Euler: a. Dmontrer que, pour que l'lmentadeZ/nZsoit inversible, il faut et il suffit que l'entier asoit premier avecn. Donner les valeurs denentierlorsque l'nprend toute valeur de 2 7. b. Dmontrer que l'ensembleZ/nZdes lments deZ/nZinversibles est un groupe multiplicatif. Quel est son cardinal ? Soitaun entier compris entre 0 etn10an1, premier avecn. Soitnle nombre d'lments deZ/nZinversibles. Dmontrer la relation : n a1,n. Indication : considrer l' application:bb.adeZ/nZdans lui-mme puis l' expressioncdfinie par la relation suivante : cb.a. bZ/nZ
311 c. Application : dterminer le reste de la division de 251par 6. IV-2.Principe de cryptographie: Soitnun entiern2gal au produit de deux nombres premierspetq;np.q. a. Dmontrer la relation : np1 q1.
Soiteun nombre entier premier avecp1 q1. b. tablir l'existence d'un entierdtel que : e.d1,p1 q1. e.d Exemple simple :n6,e5 ; calculer, pour tout lmentadeZ/6Z,a. c. Dmontrer pour tout lmentadeZ/nZ, la relation : e.d aa,n.
En fait l' entiereentierexpditeur, l'est connu de l'ddu destinataire. L' entierdest trs difficile calculer si la factorisation de l'entiernn' estpas connue (les entierspetqsont grands). e Chiffrement du messageapar l'expditeur :aa; dchiffrement par le destinataire : e ed a a. Le message est retrouv.