\documentclass[a4paper]{article}
\usepackage{entete}
\author{Référence~: Oraux X-ENS, Algèbre 1. \\ Serge \textsc{Francinou}, Hervé \textsc{Gianella}, Serge \textsc{Nicolas}}
\title{Probabilité pour que deux entiers soient premiers entre eux.}
\date{2011-2012}

\begin{document}
\maketitle

Prérequis~: 
\begin{itemize}
    \item fonction de Möbius
    \item formule du crible
\end{itemize}
\bigskip

On rappelle la définition de la fonction de Möbius~:
\begin{defi}
    La fonction de Möbius est la fonction $\mu~:~\N^* \to \Z$ définie par~:
    \begin{itemize}
        \item $\mu(1)=1$
        \item $\mu(p_1\cdots p_r) = (-1)^r$ si les $p_i$ sont des nombres premiers distincts
        \item $\mu(n)=0$ sinon (si $n$ est divisible par le carré d'un nombre premier).
    \end{itemize}
\end{defi}
On rappelle de plus la formule du crible~:
\begin{prop}[Formule du crible]
    Soient $E_1,\ldots,E_k$ des ensembles finis. Alors~:
    $$\card \left( \bigcup_{i=1}^k E_i \right) = \sum_{\emptyset\not = I \subseteq \Lbrack 1,k \Rbrack} (-1)^{1+\card I} \card \left( \bigcap_{i\in I} E_i \right).$$
\end{prop}
On note aussi $r_n$ la probabilité que deux entiers choisis au hasard dans $\Lbrack 1,n \Rbrack$ soient premiers entre eux.

On a alors~:
\begin{thm}
    On a $\displaystyle{\lim_{n\to\infty} r_n = \frac{6}{\pi^2}}.$
\end{thm}
\begin{proof}
    Appellons, pour tout $n\geqslant 1$, 
    $$A_n = \{ (a,b) \in \Lbrack 1,n \Rbrack^2~|~a \land b =1\}.$$

    On a donc $r_n = \frac{\card A_n}{n^2}.$

    On note $p_1,\ldots,p_k$ la liste des nombres premiers inférieurs à $n$, et $U_i = \{(a,b) \in \Lbrack 1,n \Rbrack^2~|~p_i|a\text{ et } p_i|b\}$.

    On a alors l'identité~:
    $$A_n = \left( \bigcup_{i=1}^k U_i \right)^c.$$ 
    \begin{lem}
        On a 
        $$\card A_n = \sum_{d=1}^n \mu(d) E \left( \frac n d \right)^2.$$
    \end{lem}
    \begin{prooflem}
        Soit $I \subseteq \Lbrack 1,k \Rbrack$ non vide. Alors le cardinal de l'intersection $\bigcap_{i\in I} U_i$ est exactement égal au nombre de couples de multiples strictement positifs de $\prod_{i\in I} p_i$ inférieurs à $n$~:
        $$\card \left( \bigcap_{i\in I} U_i \right) = E \left( \frac{n}{\prod_{i\in I}p_i} \right)^2.$$

        On peut donc utiliser la formule du crible~:
        \begin{align*}
            \card \left( \bigcup_{i=1}^k U_i \right) 
            &= \sum_{\emptyset\not = I \subseteq \Lbrack 1,k \Rbrack} (-1)^{1+\card I} \card \left( \bigcap_{i\in I} U_i \right) \\
            &= \sum_{\emptyset\not = I \subseteq \Lbrack 1,k \Rbrack} (-1)^{1+\card I} E \left( \frac{n}{\prod_{i\in I}p_i} \right)^2 \\
        \end{align*}

        Donc on a~:
        \begin{align*}
            \card A_n &= n^2 - \sum_{\emptyset\not = I \subseteq \Lbrack 1,k \Rbrack} (-1)^{1+\card I} E \left( \frac{n}{\prod_{i\in I}p_i} \right)^2 \\
            &= \sum_{d=1}^n \mu(d) E \left( \frac{n}{d} \right)^2 
        \end{align*}

        En effet~: on veut ne garder dans la somme que les produits de nombres premiers distincts, d'où le $\mu(d)$ pour "enlever" les autres, et $n^2$ correspond à $d=1$.

        D'où le résultat.
    \end{prooflem}
    On peut en déduire immédiatement que 
    $$r_n = \frac{1}{n^2} \sum_{d=1}^n \mu(d) E \left( \frac n d  \right)^2.$$

    L'intuition nous indique ici de remplacer le terme $\frac 1{n^2} E \left( \frac n d \right)^2$ par son équivalent $\frac{1}{d^2}$ (on commence à voir apparaître $\zeta(2)$\dots).

    On estime la différence entre les deux sommes~:
    $$\left| r_n - \sum_{d=1}^n \frac{\mu(d)}{d^2} \right| 
     = \left| \sum_{d=1}^n \mu(d) \left( \frac{1}{n^2} E \left( \frac nd \right)^2 - \frac 1{d^2}  \right)  \right| .$$

     On remarque que $E(n/d) > n/d -1$, et donc on a~:
     $$\frac1{n^2} - \frac{2}{dn} < \frac{1}{n^2} E \left( \frac nd \right) ^2 - \frac{1}{d^2} \leqslant 0.$$

    Donc, par inégalité triangulaire~:
    \begin{align*}
        \left| r_n - \sum_{d=1}^n \frac{\mu(d)}{d^2} \right| 
        &\leqslant \sum_{d=1}^n \left( \frac{2}{dn}+\frac{1}{n^2} \right) \\
        &\leqslant \frac 2n \sum_{d=1}^n \frac 1d + \frac 1n \\
        &= \mathcal O \left( \frac{\log n}{n} \right) 
    \end{align*}

    Ainsi, on a l'identité~:
    $$\lim_{n\to\infty} r_n = \sum_{d=1}^\infty \frac{\mu(d)}{d^2}.$$
    Calculons cette somme. Pour cela, calculons à tout hasard $$\sum_{d=1}^\infty \frac{\mu(d)}{d^2} \times \sum_{n=1}^\infty \frac{1}{n^2}.$$

    Les deux séries convergent absolument, et donc, par théorème de Fubini~:
    \begin{align*}
        \left( \sum_{d=1}^\infty \frac{\mu(d)}{d^2} \right) \left( \sum_{n=1}^\infty \frac{1}{n^2} \right) 
        &= \sum_{d,n\geqslant 1} \frac{\mu(d)}{(dn)^2} \\
        &= \sum_{d\geqslant 1,~d|k} \frac{\mu(d)}{k^2} \\
        &= \sum_{k\geqslant 1} \sum_{d|k} \frac{\mu(d)}{p^2} \\
        &= \sum_{k\geqslant 1} \frac{1}{k^2} \left( \sum_{d|k} \mu(d) \right) 
    \end{align*}

    Il ne nous manque ici plus qu'un petit lemme sur la fonction de Möbius~:
    \begin{lem}
        On a 
        $$\sum_{d|n} \mu(d) = \left\{ \begin{array}{c} 1 \text{ si } n=1 \\ 0 \text{ si } n\geqslant 2. \end{array} \right.$$
    \end{lem}
    \begin{prooflem}
        Notons $S(n)$ la somme considérée. Il est clair que $S(1) =1$. Soit donc $n\geqslant 2$, et considérons sa décomposition en facteurs premiers~:
        $$n =  \prod_{i=1}^k p_i^{\alpha_i},$$
        où les $p_i$ sont des nombres premiers distincts, et $\alpha_i$ des entiers strictements positifs.

        Les seuls termes non nuls dans $S(n)$ sont des produits de $p_i$, sans multiplicités. Pour chaque $j$, $n$ a exactement $C_k^j$ diviseurs de cette forme, produits de $i$ $p_j$. D'où
        \begin{align*}
            S(n) &= \sum_{j=0}^k C_k^j (-1)^j \\
            &= (1-1)^k \\
            &= 0
        \end{align*}
    \end{prooflem}
    On conclut avec le lemme, et la bien connue valeur de $\zeta(2)$.
\end{proof}


\end{document}
