                          %+------------------------+
                          %|  MINES 2002. Maths 2.  |
                          %+------------------------+
                        %+-----------------------------+
                        %|  Corrig\'e pour serveur UPS.  |
                        %+-----------------------------+
%%*******************************************************************************
\input jll.mac
\hautpageun={\hfill}
\hautpage={\hfill}
\def\cc{\quad{\smc cqfd.}}
\def\Num#1{\leavevmode\hbox to 8 true mm{\bf #1\hfill}}
\def\dsim{\mathop{\sim}\limits}
\catcode64=11 \def\email{jean-louis.lamard@prepas.org} \catcode64=12
%%*******************************************************************************
\centerline{\bf MINES-PONTS 2002. Fili\`ere MP. MATH\'EMATIQUES 2.}\par
\centerline{\it Corrig\'e de JL. Lamard (\email)}\vs
%%*******************************************************************************
\ind{
%%*******************************************************************************
\Num{I.1.}{\bf La suite des nombres premiers est illimit\'ee.}\vs
\v Raisonnement classique par l'absurde bas\'e sur la d\'ecomposition en produit de
nombres premiers de tout entier sup\'erieur ou \'egal \`a 2.\cc\vs
%%*******************************************************************************
\Num{I2.}{\bf Ensemble $M_n$.}\vs
%%-------------------------------------------------------------------------------
\num{a.}$0<\lfrac1{n^s}<1$ d'o\`u la relation propos\'ee.\cc\par
%%-------------------------------------------------------------------------------
\num{b.}Ainsi les familles de r\'eels positifs $\Big(\lfrac1{a^{is}}\Big)_{i\in\N}$ et
$\Big(\lfrac1{a^{js}}\Big)_{j\in\N}$ sont sommables 
(puisque positives et que les s\'eries cor\-respondantes convergent) 
donc la famille produit est sommable de somme le produit des sommes.\cc\vs
%%-------------------------------------------------------------------------------
\num{c.}Notons $\varphi$ l'application propos\'ee et soient 
$\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_n)$ et 
$\beta=(\beta_1,\beta_2,\ldots,\beta_n)$ deux \'el\'ements de $\N^n$ tels que 
$\varphi(\alpha)=\varphi(\beta)$. En \'elevant ce r\'eel positif \`a la puissance $\lfrac1s$,
il vient que $p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_n^{\alpha_n}=
p_1^{\beta_1}p_2^{\beta_2}\ldots p_n^{\beta_n}$ donc $\alpha=\beta$ par unicit\'e
de la d\'ecomposition en facteurs premiers. Ainsi l'application $\varphi$ est
injective.\cc\vs
\b Ainsi $M_n$ est un ensemble de r\'eels en bijection avec $\N^n$ lui m\^eme en
bijection avec $\N$. Il en d\'ecoule classiquement qu'il existe une bijection
strictement croissante de $\N^*$ sur $M_n$.\cc\vs
\b $M_2=\big\{1,2,3,4,6,8,9,12,16,18,24,27,\ldots\big\}$ \par
\v $M_3=\big\{1,2,3,4,5,6,8,9,10,12,15,16,\ldots\big\}$.\vs
\b Les $n$ familles de r\'eels positifs 
$\Big(\lfrac1{p_i^{s\alpha_i}}\Big)_{\alpha_i\in\N}$ sont sommables de somme 
$\Big(1-\lfrac1{p_i^s}\Big)^{-1}$ donc la famille produit est sommable de somme le
produit des sommes. \par
\v Ainsi $\dsum_{m\in M_n}\lfrac1m=\dsum_{j=1}^\++\lfrac1{m_j}=
\dprod_{i=1}^n\Big(1-\lfrac1{p_i^s}\Big)^{-1}$.\cc\vs
%%-------------------------------------------------------------------------------
\num{d.} Notons $N=N(n)$. \par
\v Il vient $\dsum_{k=1}^n\lfrac1{k^s}=\dsum_{m\in M_{N(n)}; m\le n^s}\lfrac1m
\le f_{N(n)}(s)$ et cela pour tout entier $n\ge2$ et tout r\'eel $s>0$.\cc\vs
\b En particulier $\dsum_{k=1}^n\lfrac1k\le f_{N(n)}(1)$. Supposons qu'il n'existe
que $N_0$ entiers premiers. \par
\v Il en r\'esulte que 
$\dsum_{k=1}^n\lfrac1k\le f_{N_0}(1)$ pour tout entier
$n\ge N_0$. Ainsi la s\'erie harmonique serait convergente. \cc\vs
\b Pour tout r\'eel $s>0$, la suite $\big(f_k(s)\big)_{k\in\N}$ est clairement croissante donc
admet une limite $\ell(s)\in\overline\R$.\par
\v Lorsque $n$ tend vers $\++$, il en va de m\^eme de $N(n)$ donc $f_{N(n)}(s)$
tend vers $\ell(s)$.\par
\v Supposons d\'esormais que $s\in]0,1]$. De 
$\dsum_{k=1}^n\lfrac1{k^s}\le f_{N(n)}(s)$ on tire par passage \`a la limite que 
$\ell(s)=\++$. \par
\v Ainsi $\dlim_{n\to\++}f_n(s)=\++$ pour $s\in]0,1]$.\cc\vs
%%-------------------------------------------------------------------------------
\num{e.}On a \'evidemment $\Big\{\lfrac1m\Big\}_{m\in M_{N(n)}}\subset
\Big\{\lfrac1{k^s}\Big\}_{k\in\N^*}$ donc si $s>1$ il vient 
$\dsum_{k=1}^n\lfrac1{k^s}\le f_{N(n)}(s)\le\zeta(s)$.\par
\v Par passage \`a la limite, il en r\'esulte que $\ell(s)=\zeta(s)$.\par
\v Ainsi $\dlim_{n\to\++}f_n(s)=\zeta(s)$ pour $s>1$.\cc\vs
%%*******************************************************************************
\Num{I.3.}{\bf S\'erie de terme g\'en\'eral $\lfrac1{p_i}$.}\vs
\v Il vient $\dsum_{i=1}^nv_i=\ln\Big(\dprod_{i=1}^n(1-\lfrac1{p_1})\Big)=
-\ln f_n(1)$ tend vers $-\infty$ d'apr\`es I.2.d. Donc la s\'erie de terme g\'en\'eral
$v_i$ diverge donc \'egalement la s\'erie de terme g\'en\'eral $\lfrac1{p_i}$ puisque 
$-v_i\sim\lfrac1{p_i}>0$.\par
\v Ainsi la s\'erie $\dsum\lfrac1{p_i}$ diverge ce qui prouve qu'il a ``beaucoup''
de nombres premiers.\cc\vs
%%*******************************************************************************
\goodbreak
\Num{I.4.}{\bf Fonction $\zeta$.}\vs
\v Notons $u_k(s)=\lfrac1{k^s}$. Les fonctions $u_k$ sont de classe ${\cal C}^1$
sur $]1,\++[$, la s\'erie $\dsum_{k=1}^\++u_k(s)$ y converge simplement et la
s\'erie d\'eriv\'ee $\dsum u'_k(s)$ y converge localement normalement car, pour $s\ge
a$ avec $1<a$, on a $|u'_k(s)|=\lfrac{\ln k}{k^s}\le\lfrac{\ln k}{k^a}$ et 
$\lfrac{\ln k}{k^a}=o\big(\lfrac1{k^\alpha}\big)$ avec $1<\alpha<a$. Ainsi la
fonction $\zeta$ est de classe ${\cal C}^1$ sur $]1,\++[$.\cc\vs
%%*******************************************************************************
\Num{II.1.}{\bf Majoration du produit $P_n$.}\vs
%%-------------------------------------------------------------------------------
\num{a.}\par
\vskip-3mm
\v $\left[\matrix{
n&N&p_N&P_n&4^n\cr
2&1&2&2&16\cr
3&2&3&6&64\cr
4&2&3&6&256\cr
5&3&5&30&1024\cr
}\right]$\vs
%%-------------------------------------------------------------------------------
\num{b.}Si $n+1$ n'est pas premier alors $N(n+1)=N(n)$ donc
$P_{n+1}=P_n$. \cc\vs
%%-------------------------------------------------------------------------------
\num{c.}Si $n+1$ est premier il est impair car $n\ge2$ d'o\`u l'existence de
l'entier $m$.\par
\v On a $m!\binom_{2m+1}^m=(2m+1)(2m)\ldots(m+2)$. Donc si $p$ est un nombre
entier compris entre $m+2$ et $2m+1$ il divise $m!\binom_{2m+1}^m$. Si en outre $p$ est
premier, il ne divise pas $m!$ d'apr\`es le th\'eor\`eme de Gauss (sinon il diviserait
$k\le m$ ce qui est impossible car $p>m$) donc, toujours par le th\'eor\`eme de
Gauss, il divise $\binom_{2m+1}^m$.\cc\vs
\b On a $\binom_{2m+1}^m+\binom_{2m+1}^{m+1}\le
\dsum_{k=0}^{2m+1}\binom_{2m+1}^k=2^{2m+1}=2\ 4^m$. Or 
$\binom_{2m+1}^m=\binom_{2m+1}^{m+1}$.
Donc $\binom_{2m+1}^m\le4^m$.\cc\vs
\b Supposons $P_{m+1}\le4^{m+1}$. Il vient $P_{n+1}=P_{m+1}q$ o\`u $q$ est le
produit des nombres premiers compris entre $m+2$ et $n+1=2m+1$. D'apr\`es
ci-dessus chacun de ces facteurs divise $\binom_{2m+1}^m$ donc leur produit $q$
\'egalement d'apr\`es le th\'eor\`eme de Gauss. Il en r\'esulte que 
$q\le\binom_{2m+1}^m\le4^m$. Ainsi  $P_{n+1}\le4^{m+1}4^m=4^{n+1}$.\cc\vs
%%-------------------------------------------------------------------------------
\num{d.}Pour $n\ge2$ soit le pr\'edicat 
${\cal P}(n)=\og \ P_k\le4^k\ \text{pour}\ 2\le k\le n\ \fg$. 
${\cal P}(2)$ est vrai et il r\'esulte de ce
qui pr\'ec\`ede que ${\cal P}(n)$ est vrai pour tout $n\ge2$ par r\'ecurrence.\cc\vs
%%*******************************************************************************
\Num{II.2}{\bf Une expression du ppcm $d_n$.}\vs
\v On a $d_n=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_N^{\alpha_N}$ avec
$p_i^{\alpha_i}$ divise un entier $k\le n$ mais $p_i^{\alpha_i+1}$ n'en divise aucun. \par
\v Ainsi $p_i^{\alpha_i}\le n$ et $p_i^{\alpha_i+1}>n$ sinon
$p_i^{\alpha_i+1}=k\le n$ donc divise $k\le n$.\par
\v Donc $\alpha_1=\left[\ln n/\ln p_i\right]$.\cc\vs
%%*******************************************************************************
\Num{II.3.}{\bf Une minoration du ppcm $d_{2n+1}$.}\vs
\num{a.}Pour tout $x\in[0,1]$ il vient $x(1-x)\le\lfrac14$ d'o\`u
$I_n\le\lfrac1{4^n}$. \cc\vs
%%-------------------------------------------------------------------------------
\num{b.}$d_{2n+1}$ est \'evidemment divisible par tout entier inf\'erieur ou \'egal \`a
$2n+1$ donc en particulier par $n+k+1$ pour $k$ variant de 0 \`a $n$.\par
\v Or $I_n=\dsum_{k=0}^n(-1)^k\lfrac{\binom_n^k}{n+k+1}$ donc
$d_{2n+1}I_n\in\Z$. Par ailleurs $d_{2n+1}I_n>0$ donc c'est un entier naturel
non nul.\par
\v Ainsi $d_{2n+1}I_n\ge1$ donc $d_{2n+1}\ge\lfrac1{I_n}\ge4^n$ d'apr\`es
II.3.a. \cc\vs
%%*******************************************************************************
\Num{III.1.}\ {\bf Un r\'esultat auxiliaire.}\vs
\b Notons que $\pi(x)=N([x])$, $\theta(x)=\ln P_{[x]}$ et $H_A(x)=A_{\pi(x)}$ en
notant $A_n=\dsum_{k=1}^na_k$.\par
\b $H_A$ est constante donc continue sur $[1,2[$ et sur tout intervalle
$[p_n,p_{n+1}[$ o\`u elle vaut $A_n$.\par
\v On a donc $H_A(p_n)-H_A(p_n-0)=a_n$ et donc $H_A$ est discontinue en $p_n$ si
et seulement si $a_n\not=0$.\vs
\b $\dint_2^xH_A(t)f'(t)\d t=
\dsum_{k=1}^{N-1}\dint_{p_k}^{p_{k+1}}H_A(t)f'(t)\d t+
\dint_{p_N}^xH_A(t)f'(t)\d t$\par
\v \phantom{$\dint_2^xH_A(t)f'(t)\d t$}
$=\dsum_{k=1}^{N-1}A_k\big(f(p_{k+1})-f(p_k)\big)+A_N\big(f(x)-f(p_N)\big)$
\quad car $f$ est de classe ${\cal C}^1$.\par
\v \phantom{$\dint_2^xH_A(t)f'(t)\d t$}
$=A_Nf(x)+\dsum_{k=2}^NA_{k-1}f(p_k)-\dsum_{k=1}^NA_kf(p_k)$\par
\v \phantom{$\dint_2^xH_A(t)f'(t)\d t$}
$=H_A(x)f(x)-\dsum_{k=1}^Na_kf(p_k)$\cc\vs
%%*******************************************************************************
\goodbreak
\Num{III.2.}\ {\bf Une majoration de la fonction $\pi$.}\vs
%%-------------------------------------------------------------------------------
\num{a.}On a $\theta(x)=\ln\big(P_{[x]}\big)\le\ln\big(4^{[x]}\big)$
d'apr\`es II.1.d. Donc $\theta(x)\le [x]\ln4\le x\ln 4$.\cc\vs
%%-------------------------------------------------------------------------------
\num{b.}En choisissant la suite $(a_k)$ et la fonction $f$ (qui est bien de
classe ${\cal C}^1$ sur $[2,\++[$) indiqu\'ees dans l'\'enonc\'e, il vient 
$H_A(x)=\theta(x)$ et la relation \'etablie en III.1. s'\'ecrit, puisqu'alors 
$\dsum_{k=1}^Na_kf(p_k)=N=N(x)=\pi(x)$ :\par
\v $\pi(x)=\lfrac{\theta(x)}{\ln x}+\dint_2^x\lfrac{\theta(t)}{t\ln^2t}\d t$.\par
\v D'o\`u la majoration propos\'ee compte tenu de l'in\'egalit\'e $\theta(x)\le x\ln 4$
\'etablie ci-dessus.\cc\vs
%%-------------------------------------------------------------------------------
\num{c.}Il vient $\dint_2^x\lfrac{\d t}{\ln^2t}=
\dint_2^{\sqrt x}\lfrac{\d t}{\ln^2t}+\dint_{\sqrt x}^x\lfrac{\d t}{\ln^2t}\le
\lfrac{\sqrt x-2}{\ln^22}+\lfrac{4(x-\sqrt x)}{\ln^2x}\dsim_{x\to\++}
\lfrac{4x}{\ln^2x}$.\par
\v Donc $\dlim_{x\to\++}R(x)=0$.\cc\vs
%%-------------------------------------------------------------------------------
\num{d.}En particulier pour $x$ assez grand on a $R(x)\le1$ donc 
$\dint_2^x\lfrac{\d t}{\ln^2t}\le\lfrac x{\ln x}$ d'o\`u, en vertu de l'in\'egalit\'e 
III.2.b., $\pi(x)\le4\ln 2\lfrac x{\ln x}$.\cc\vs
%%*******************************************************************************
\Num{III.3.}\ {\bf Une minoration de la fonction $\pi$.}\vs
\v Soit $x$ un r\'eel positif et soit $n$ tel que $2n+1\le x\le 2n+2$.\par
\v Il vient $d_{2n+1}=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_N^{\alpha_N}$ 
avec $N=N(2n+1)=\pi(x)$.\par
\v Or $d_{2n+1}\ge4^n$ d'apr\`es II.3.b. donc 
$\alpha_1\ln p_1+\alpha_2\ln p_2+\cdots+\alpha_N\ln p_N\ge n\ln 4$.\par
\v Or $\alpha_i=[\ln(2n+1)/\ln p_i]$ donc a fortiori 
$\dsum_{i=1}^N\ln(2n+1)\ge n\ln 4$ d'o\`u $N=\pi(x)\ge\ln 4\lfrac
n{\ln(2n+1)}\ge\ln 4\lfrac{(x-2)/2}{\ln x}$.\par
\v Or $\ln4\lfrac{(x-2)/2}{\ln x}
\dsim_{n\to\++}\ln 2\lfrac x{\ln x}$ donc, pour $x$ assez grand, 
$\pi(x)\ge\lfrac{\ln 2}2\ \lfrac x{\ln x}$.\cc\vs
%%*******************************************************************************
\Num{IV.1.}\ {\bf Th\'eor\`eme d'Euler.}\vs
%%-------------------------------------------------------------------------------
\num{a.} $\Big(\ \overline a \text{ est inversible dans \Z/n\Z}\ \Big)
\<=>\Big(
\ \exists \overline u\in\Z/n\Z \text{ tel que } \overline u\ \overline a=\overline1\ 
\Big)\<=>\Big(
\ \exists u\in\Z\  \exists v\in\Z \text{ tel que } ua=1+vn
\Big)$\par
\v Ainsi, d'apr\`es le th\'eor\`eme de Bezout (ici Bachet de M\'eziriac en r\'ealit\'e),
$\overline a$ est inversible si et seulement si $a$ est premier avec $n$.\cc\vs
%%-------------------------------------------------------------------------------
\num{b.}D'une mani\`ere g\'en\'erale si ${\cal A}$ est un anneau, il est imm\'ediat de
v\'erifier que l'ensemble ${\cal A}^*$ des \'el\'ements inversibles est
un groupe multiplicatif. En particulier $\Big(\Z/n\Z\big)^*$ est un groupe
multiplicatif de cardinal $\varphi(n)$ compte-tenu de la question
pr\'ec\'edente.\par
\b Soit $a$ premier avec $n$. Alors $\overline a\in \Big(\Z/n\Z\big)^*$ et son
ordre $r$ divise $\varphi(n)$ d'apr\`es le th\'eor\`eme de Lagrange. \par
\v Donc $\overline a^{\varphi(n)}=\overline a^{rq}=\overline 1^q=\overline 1$.
\cc\par
\v {\it Autre d\'emonstration} : l'application propos\'ee est, puisque $\overline a$
est inversible, bien une application de $\Big(\Z/n\Z\big)^*$ dans lui-m\^eme et
elle est injective. Donc elle est surjective puisque $\Big(\Z/n\Z\big)^*$ est
fini. Ainsi $c$ est le produit de tous les \'el\'ements de $\Big(\Z/n\Z\big)^*$. 
Or, puisque le groupe est commutatif, $c=\overline a^{\varphi(n)}c$ avec $c$
inversible. \cc\vs
%%-------------------------------------------------------------------------------
\num{c.}$251=41\times6+5$ donc, modulo 6, $251^{311}\equiv5^{311}\equiv(-1)^{311}
\equiv-1$. Le reste cherch\'e est donc 5. Le th\'eor\`eme d'Euler est totalement
inutile pour traiter cet exemple !\vs
%%*******************************************************************************
\Num{IV.2.}\ {\bf Principe de criptographie.}\vs
%%-------------------------------------------------------------------------------
\num{a.}Soit $m$ non premier avec $pq$, avec $1\le m\le pq-1$. Alors $m$ est divisible par $p$
ou $q$ donc de la forme $pr$ avec $r<q$ ou de la forme $qs$ avec $s<p$. Or ces
deux ensemble sont disjoints. Donc le nombre des entiers $m$ est $(p-1)+(q-1)$.
Il en d\'ecoule que $\varphi(pq)=pq-1-(p+q-2)=(p-1)(q-1)$.\cc\vs
%%-------------------------------------------------------------------------------
\num{b.}Ce n'est rien d'autre qu'un cas particulier de IV.1.a.\vs
%%-------------------------------------------------------------------------------
\num{c.}Soit $a$ un entier quelconque. \par
\v Nous avons $a^{1+k(p-1)(q-1)}\equiv a$\quad (mod $p$). En effet c'est
clairement vrai si $a$ est divisible par $p$ et sinon, comme $p$ est premier,
$a$ est premier avec $p$ et le th\'eor\`eme d'Euler fournit $a^{p-1}\equiv 1$ \quad
(mod $p$).\par
\v De m\^eme puisque $q$ est premier, $a^{1+k(p-1)(q-1)}\equiv a$\quad (mod
$q$).\par
\v $p$ et $q$ \'etant \'evidemment premiers entre eux, le th\'eor\`eme de Gauss
prouve que $a^{1+k(p-1)(q-1)}\equiv a$\quad (mod $pq$).\par
\v Comme $ed=1+k\varphi(n)=1+k(p-1)(q-1)$, il vient donc $a^{ed}\equiv a$ \quad
(mod $pq$).\cc\vs
%%*******************************************************************************
}\indd\VS\Fin
%%*******************************************************************************
\bye

