Mines Maths 2 MP 2002

Thème de l'épreuve Autour des nombres premiers et de leur répartition
Principaux outils utilisés arithmétique, Z/nZ, séries numériques
Mots clefs répartition des nombres premiers, anneau, inégalité de Tchebychev

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                    

Rapport du jury

(télécharger le PDF)
        

Énoncé obtenu par reconnaissance optique des caractères


J. 2066
A 2002 Math MP 2

ÉCOLE NATIONALE DES PONTS ET CHAUSSÉES.
ÉCOLES NATIONALES SUPÉROEURES DE L'AERONAUTIQUE ET DE L'ESPACE,
DE TECHNIQUES AVANCÉES, DES TELECOMMUNTCADONS,
DES MINES DE PARIS, DES MINES DE SAINT--ETIENNE, DES MINES DE NANCY,
DES TÉLÉCOMMUNÏCATIÛNS DE BRETAGNE.
ÉCOLE POLYTECHNIQUE ( Filière TSI)

CONCOURS D'ADMISSION 2002

ÉPREUVE DE MATHÉMATIQUES
DEUXIEME EPREUVE
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--ENR

Les candidats sont priés de mentionner de façon apparente sur la première page 
de la copie :
MATHEMATIQUES 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 premiers p ,, i = 
1, 2, :

p1=2,p2=3,p3=

Dans tout le problème la lettre p est réservée aux nombres premiers. Étant 
donné un réel x, sa
partie entière [x] est l'entier n qui vérifie la double inégalité suivante :

[x]=nSx_ 2), s un réel 
donné strictement
positif (s > O)

I-2. Ensemble Mn :
a. Justifier la relation suivante :

b. Soient a et b deux entiers, différents l'un de l'autre, tous les deux 
supérieurs ou égaux à 2
(a # b, a z 2, b 2 2) ; démontrer que la série double de terme général u, i = 
0,1,2,...,

] = 0, 1,2, défini par la relation suivante

]"

u...= .1 , i=0,1,2,..., j=0,1,2,....

est sommable. Déterminer sa somme S.

Soient pl , pl ..., p,, les n premiers nombres premiers, M ,, l'ensemble des 
réels obtenus en

considérant tous les produits des réels (pl )", (p;)', ..., (p,,)' élevés à des 
exposants et,,
1 S i S n, entiers positifs ou nuls.

M" = {m | m : (p0°'"".(p;)""2 ..... (p,,)"", a,-- e N}.

c. Démontrer que l'application (al, a2,...,an) +----> (p1)s"".(pg)""2 ..... 
(p,,)"'", de N" dans
M ,,, est injective. En déduire qu'il est possible d'indexer les réels m dans 
l'ordre croissant :

l'application i i----> m ,- est strictement croissante de N* sur M...
Exemples : écrire la suite des 12 premiers termes de la suite (m,--),ËW lorsque 
le réels est égal

à 1 et l'entier n égal à 2 puis à 3.

Il est admis que la série de terme général v,-- : l/m,--, i EUR N'", est 
convergente ; sa somme est
désignée par le symbole : 2 m"'. Comme le laisse présager l'alinéa b, le 
résultat plus général
mêM,,
ci-dessous est vrai et est admis :

--2/7--

Soit f,, la fonction définie sur la demi-droite ouverte ]0, oo[ par la relation 
suivante :

fn(s) : ñ(l .. (p1)s)"l.

i=l

Soit N le rang du plus grand nombre premier inférieur à n (N = sup{i | pi 5 n} 
).

d. Démontrer l'inégalité suivante :

n N ..
ëîlfîgll" (pi-ÿ) l'

Retrouver, en donnant une valeur particulière au réel 5, le résultat : la suite 
des entiers premiers
est illimitée.

Déterminer, en supposant le réels inférieur ou égal à 1 (0 < s 5 1), la limite, 
lorsque l'entier n
tend vers l'infini, de l'expression f,, (s) introduite ci-dessus.

Il est admis, puisque la suite des nombres premiers est illimitée, qu'à tout 
réel x supérieur ou
égal à 2 (x _>_ 2), peut être associé un entier N tel que le réel x soit 
encadré par les nombres

premiers pN et pN+1 :

PN E x < pN+l-
e. Établir, lorsque le réel s est strictement supérieur à 1 (s > 1), 
l'encadrement ci-dessous :
n 1 N 1 _1 co 1
--,.- _<_ (1 -- s ) S ---;,--.
ëk [J  1, la limite de l'expression f,, (s) introduite ci-dessus 
lorsque l'entier n
tend vers l'infini.

1--3. Série de terme général l/p,-, i = 1,2,... :
Déduire des résultats ci-dessus la nature de la série de terme général v,--, i 
= 1, 2, défini par
la relation suivante.

_ _ .l.
V,' --- lfl(l pi ).
En déduire la nature de la série de terme général :

W," : l=1,2,.....

__1_
Pi '
Quelle conclusion qualitative est-il possible d'en tirer sur la répartition des 
nombres premiers ?

1--4. Fonction Ç :
Soit Ç la fonction limite de la suite f,,. Démontrer que cette fonction, 
définie d'après la question
I--2.e sur la demi-droite ouverte ]1, col: par la relation ci-dessous, est 
continûment dérivable.

__.- N _ 1 "= _l_
Ç(s) IrmH 1 (p--)' Ek--°'
1--1 '

N--bOE) -_ k: 1

T
_ 3 /7 _ ournez la page S.V.P.

Deuxième partie

Le but de cette partie est d'établir une majoration du produit des nombres 
entiers premiers
inférieurs ou égaux à un entier donné n et d'encadrer le plus petit commun 
multiple de tous les
entiers inférieurs ou égaux à cet entier n.

Soit toujours n un entier supérieur ou égal à 2 (n 2 2), N le rang du plus 
grand nombre
premier inférieur ou égal à n ; soit P,, le produit des nombres premiers 
inférieurs ou égaux à n :

N
pN 5 n _ 2), 7r(x) est égal au nombre des 
nombres premiers
inférieurs ou égaux au réel x.

N
PNSX_ 2, àla somme des 
termes de la suiteA

dont les rangs sont inférieurs ou égaux au rang N du plus grand nombre entier 
premier inférieur ou
égal à x :

0,sile<2,

HA(X) : N

Zak, si2 S xetpN 5 x  1/lnx, 
l'inégalité suivante :

7r(x) S ln4(-È +]: (£:)2 )

c. Démontrer la convergence vers 0, lorsque le réel x croît vers l'infini, de 
la fonction R(x)
suivante :

R(x) : Ln%.Jî (Æ),

Indication : introduire, pour x 2 4 , les intégrales de 2 à J)? et de J)? à x.

d. En déduire l'existence d'un réel x0 tel que, pour tout réel x supérieur ou 
égal à x0, la
fonction 7: vérifie la majoration suivante :

J£...
rr(x) _<_ 4 ln2 lnx'

III--3. Une minoration de la fonction 7r :
En utilisant par exemple la minoration du p. p. c. rn. d2 ... obtenue àla 
question II-3,

démontrer qu'il existe un réel xl tel que, pour tout réel x supérieur ou égal à 
x1 , la fonction %
vérifie la minoration suivante :

_h_1â_x_
7r_(x)Z 2 lnx'

Ces deux résultats sont cohérents avec le "théorème des nombres premiers" 
établi par
Hadamard et de La Vallée Poussin en 1896, qui affirme que la fonction n est 
équivalente à l'infini

à la fonction x r----> x/ lnx.

--6/7-

Quatrième partie

Soit, dans toute cette partie, un entier n donné (n 2 2). L'anneau Z/nZ est 
l'ensemble quotient
de l'anneau Z par la relation d'équivalence : "deux entiers relatifs sont 
équivalents si leur
différence est divisible par l'entier n". Classiquement un élément de Z/nZ, une 
classe

d'équivalence, est notée à, a étant un représentant de cette classe.
Soit (p la fonction qui, à l'entier n, associe le nombre d'éléments inversibles 
de Z/nZ.

IV-l. Théorème d'Euler :
a. Démontrer que, pour que l'élément à" de Z/nZ soit inversible, il faut et il 
suffit que l'entier a
soit premier avec n. Donner les valeurs de rp(n) lorsque l'entier n prend toute 
valeur de 2 à 7.

b. Démontrer que l'ensemble (Z/nZ)* des éléments de Z/nZ inversibles est un 
groupe

multiplicatif. Quel est son cardinal ?
Soit a un entier compris entre 0 et n -- 1 (O 5 a 5 n -- 1 ), premier avec n. 
Soit rp(n) le nombre
d'éléments de Z/nZ inversibles. Démontrer la relation :

Î, (n).

Indication : considérer l'application y : 5 »----> 5.ä de (Z/nZ)* dans 
lui--même puis l'expression c
définie par la relation suivante :
c = n 5.'ä.

bG(Z/nZ)'

Ill

â'P(")

c. Application : déterminer le reste de la division de 251311 par 6.

IV-2. Principe de cryptographie :
Soit n un entier (n 2 2) égal au produit de deux nombres premiers p et q ; n : 
p.q .
a. Démontrer la relation :

(PO?) = (P--1)(CI--1)-

Soit e un nombre entier premier avec (p -- 1) (q -- 1 ).

b. Établir l'existence d'un entier d tel que :

aâæ 1... (
			

Extrait du corrigé obtenu par reconnaissance optique des caractères



Mines Maths 2 MP 2002 -- Corrigé
Ce corrigé est proposé par Éric Ricard (Agrégé de mathématiques) ; il a été relu
par Vincent Puyhaubert (ENS Cachan) et Walter Appel (Professeur en CPGE).

Cette épreuve des Mines est composée de quatre parties et a pour thème général
les nombres premiers. Malgré la longueur apparente de l'énoncé, le devoir n'est 
pas
très long et ne présente que peu de difficultés techniques.
· La première partie, indépendante des autres, propose d'établir la divergence
de la série des nombres premiers. En dehors de trois questions de cours qui
n'en ont pas l'air (I-1, I-2.b et I-4), seule la connaissance des techniques de
manipulation des séries est nécessaire.
· La deuxième partie établit quelques inégalités utiles dans la suite. Elle ne
demande presque aucune connaissance du programme de Spéciales et ne repose que 
sur des raisonnements élémentaires sur les nombres entiers. C'est là
toute son originalité, puisqu'il faut absolument comprendre les mécanismes mis
en jeu. En contrepartie, les questions sont très détaillées et donc abordables.
· Les inégalités de Tchebychev sur le nombre d'entiers premiers plus petits que
n consituent la troisième partie. Elle exploite les résultats de la précédente,
toujours dans le même esprit : très peu de calculs et des raisonnements assez
bien décortiqués par un énoncé donnant beaucoup d'indications.
· La dernière partie, indépendante des précédentes, contraste avec le reste du
sujet. Il s'agit de présenter le principe de base du cryptage RSA ; on a donc
affaire à de l'arithmétique dans Z/nZ et à des notions plus abstraites que dans
les parties précédentes. Les résultats qui y sont démontrés (surtout dans la
première question) sont pour la plupart des rappels de cours ou d'exercices
classiques. Elle ne requiert qu'une bonne compréhension de Z/nZ et reste à la
portée de nombreux candidats.
Dans l'ensemble, cette épreuve est originale et plaisante ; on y démontre 
quelques
résultats intéressants. La difficulté reste très raisonnable et se situe 
essentiellement
au niveau des raisonnements, ce qui est assez rare pour être souligné.

Indications
Première partie
1
pour se ramener à des entiers.
s
I-2.d Comparer MN et {k s ; 1 6 k 6 n}.
n 1
P
Prendre s = 1 et majorer
.
k=1 k
n
P
I-3 Calculer
vi .
I-2.c Élever à la puissance

i=1

I-4 Penser à utiliser le théorème de dérivation des séries de fonctions pour .

Deuxième partie
II-1.b Montrer que Pn = Pn+1 .
p
P
II-1-c Utiliser 2p =
Ckp et Ckp = Cp-k
.
p
k=0

Remarquer que Pn+1 divise Pm+1 Cm
2m+1 .

II-2 Montrer que i = max{  N | p
i 6 n} en procédant par double inégalité.
II-3.b Montrer puis utiliser le fait que In > 0 pour obtenir d2n+1 In > 1.
Troisième partie
III-1 Découper l'intégrale et inverser les sommes.
III-2.a Utiliser la question II-1.d.
III-3 Montrer d'abord le résultat pour x = 2n + 1 en utilisant la question II-2
(en passant à ln) puis la question II-3.

Quatrième partie
IV-1.b Montrer que c = ca

(n)

en utilisant le fait que (Z/nZ ) = Z/nZ.

IV-2.a Décrire les entiers entre 1 et n non premiers avec n et utiliser la 
question
IV-1.a.
IV-2.c Utiliser l'identité de Bézout.

Première partie
Dans ce corrigé, comme suggéré par l'énoncé, n est un nombre entier
supérieur à 2 et N désigne le rang du plus grand nombre premier inférieur à n.
Il est bon d'avoir en tête les inégalités
et

pn > n

N 6 pN 6 n

(1)

La première dit que le ne nombre premier est plus grand que n et la
seconde résulte de la première et de la définition de N.

I-1 Supposons qu'il n'existe qu'un nombre fini d'entiers premiers que l'on note
p1 , . . . , pn .
n

Posons

Q=

 pi + 1
i=1

On sait que tout nombre entier se décompose en un produit de facteurs premiers ;
Q admet donc un diviseur premier. Selon notre hypothèse, il existe un entier
k  [[ 1 ; n ]] tel que pk divise Q. Comme pk divise également p1 × · · · × pn , 
on en
déduit que pk divise 1, donc que pk = 1, ce qui est contradictoire car 1 n'est 
pas
premier.
I-2.a La suite
0<

1
nks

est géométrique ; comme n > 2 et s > 0, sa raison vérifie

kN

1
< 1. La série associée converge donc et
ns

-1

P
1
1
1
=
= 1- s
ks
1
n
k=0 n
1- s
n

I-2.b D'après le théorème d'inversion des séries doubles à termes positifs, la 
série
P
(uij )(i,j)N2 est sommable si et seulement si pour tout entier i,
uij converge et si
j

P P
P
la série
uij converge ; la valeur de cette série est alors
uij .
i

j=0

(i,j)N2

Dans la situation proposée,

P

j=0

uij =

1
ais

1-

1
bs

-1

D'après la question précédente, en appliquant ce résultat une fois de plus pour 
la
somme en i, on déduit que la famille (uij ) est sommable et

-1 
-1
1
1
S= 1- s
1- s
a
b

I-2.c Notons  l'application de l'énoncé. Soient (i )16i6n et (i )16i6n dans Nn ,
il faut montrer que

 (i )i[[ 1 ; n ]] =  (i )i[[ 1 ; n ]] =  i  [[ 1 ; n ]]
i = i
1
, il vient
s

En élévant l'égalité de gauche à la puissance
n

n

 pi 
i=1

i

=

 pi 
i=1

i

L'unicité de la décomposition d'un entier en facteurs premiers donne alors i = i
pour tout i inférieur à n. La fonction  est donc injective.
Par définition de Mn , elle est également surjective et réalise donc une 
bijection
1
entre Mn et Nn . Il s'ensuit que Mn est infini. L'application m 7 m s est une 
injection
de Mn dans N. D'après ce qui précède, son image est infinie et donc peut être 
énumérée
par ordre croissant comme toute partie infinie de N. Autrement dit, il existe
1

: N - Mn s
1

i 7- mi s

croissante et bijective. En composant  avec x 7 xs qui est strictement monotone,
on obtient l'indexation souhaitée.
Pour l'exemple, on range par ordre croissant les nombres de la forme 21 32 ,
puis de la forme 21 32 53 :
n=2
n=3

1
1

2 3
2 3

4 6
4 5

8
6

9 12 16 18 24 27
8 9 10 12 15 16

I-2.d D'après le résultat admis,
-1
N 
P 1
1
 1- p s
=
i=1
i
mMN m
Le résultat admis n'est que la généralisation du résultat de la question I-2.b
à n > 2.
Soit k  [[ 1 ; n ]]. Alors k s est élément de Mn . En effet la décomposition en 
facteurs
q

premiers de k est de la forme

 p
i=1 i

i

où pq est le plus grand facteur premier de k.

Ainsi k  [[ pq ; n ]] ; comme N est le rang du plus grand nombre premier plus 
petit
que n, on a q 6 N. Ainsi k s = ((1 , . . . , q , 0, . . . , 0))  MN . Puisque 
les éléments
de MN sont positifs :
-1
N 
n 1
P
P 1
1
6
=  1- s
s
i=1
pi
mMN m
k=1 k
Prenons s = 1 et supposons qu'il n'existe que q nombres premiers ; alors N 6 q
1
1
pour tout n et, comme pour tout i, pi > 2 donne 1 -
> , on a
pi
2
n 1
P
6
k=1 k

2N
|{z}

dépend de n

6

2q
|{z}

ne dépend pas de n