Progresser-en-maths

Maths + Toi = 1

ENS
Exercices corrigés

Exercice corrigé : Oral de l’ENS 2022

Voici la correction détaillée d’un exercice de probabilité tombé à l’oral de l’ENS en 2022 mais qui est principalement un exercice de dénombrement mêlé avec des congruences.

Enoncé

Probabilités dans Z/nZ

Si vous voulez plus d’énoncés de sujets tombés en 2022, allez voir notre article à ce sujet.

Corrigé

Cas 1 : n est une puissance d’un nombre premier

Commençons par le cas

n = p^{\alpha}, \Z/p^{\alpha}\Z

Avec p premier. On a la relation suivante :

ab = 0 [p^\alpha] \iff v_p(ab) \geq \alpha

Où vp est la valuation p-adique

Calculons alors la probabilité suivante :

\mathbb{P}(v_p (X) = i ) 

Avec X variable aléatoire suivant une loi uniforme sur

\{ 0, \ldots, p^{\alpha} - 1 \}

On a

p^{\alpha -k}

Multiples de pk dans cet intervalle. On en a donc

\begin{array}{ll}
mult(p^{k})-mult(p^{k+1})& = p^{\alpha-k}-p^{\alpha-k-1}\\
& =p^{\alpha-k-1}(p-1)
\end{array}

Ainsi,

\mathbb{P}(v_p (X) = i ) = \dfrac{p^{\alpha-i-1}(p-1)}{p^{\alpha}}= \dfrac{p-1}{p^{i+1}}

De cette manière, on obtient pour la probabilité recherchée :

\begin{array}{ll}
\mathbb{P}(ab=0) &=\displaystyle \sum_{i=0}^{\alpha} \mathbb{P}(ab = 0 \cap v_p(a) = i)\\ 
&=\displaystyle \sum_{i=0}^{\alpha} \mathbb{P}_{v_p(a) =i}(v_p(ab) \geq \alpha )\mathbb{P}( v_p(a) = i)\\
&=\displaystyle \sum_{i=0}^{\alpha}\dfrac{p-1}{p^{i+1}}\mathbb{P}( v_p(b) \geq \alpha- i)\\
&=\displaystyle \sum_{i=0}^{\alpha}\dfrac{p-1}{p^{i+1}}\sum_{k= \alpha-i}^{\alpha} \dfrac{p-1}{p^{k+1}}\\
&=\displaystyle (p-1)^2 \sum_{i=0}^{\alpha}\sum_{k= \alpha-i}^{\alpha} \left(\dfrac{1}{p}\right)^{k+i+2}\\
&=\displaystyle (p-1)^2 \sum_{i=0}^{\alpha}\left( \dfrac{1}{p} \right)^{i+2}\left( \dfrac{1}{p} \right)^{\alpha-i}\dfrac{1-\left(\frac{1}{p}\right)^{i+1}}{1-\frac{1}{p}}\\
&=\displaystyle (p-1)^2 \sum_{i=0}^{\alpha}\left( \dfrac{1}{p} \right)^{\alpha+2}\dfrac{1-\left(\frac{1}{p}\right)^{i+1}}{\frac{p-1}{p}}\\
&=\displaystyle (p-1) \sum_{i=0}^{\alpha}\left( \dfrac{1}{p} \right)^{\alpha+1}\left(1-\left(\frac{1}{p}\right)^{i+1}\right)\\
&=\displaystyle \dfrac{(p-1)}{p^{\alpha+1}} \sum_{i=0}^{\alpha}\left(1-\left(\frac{1}{p}\right)^{i+1}\right)\\
&=\displaystyle \dfrac{(p-1)}{p^{\alpha+1}}(\alpha+1 -\dfrac{1}{p}\dfrac{1-\left(\frac{1}{p}\right)^{\alpha+1}}{1-\frac{1}{p}})\\
&=\displaystyle \dfrac{1}{p^{\alpha+1}}\left((p-1)(\alpha+1 )-1-\left(\frac{1}{p}\right)^{\alpha+1}\right)
\end{array}

Cas général

On décompose n à l’aide du théorème des nombres premiers :

n = p_1^{\alpha_1} \ldots p_r^{\alpha_r}

On va utiliser le fait que

\Z / n \Z \simeq \Z / p_1^{\alpha_1} \Z \times \ldots \times \Z /p_r^{\alpha_r}\Z

L’équivalence suivante est vraie :

ab = 0 [n]\iff \forall i \in \{1, \ldots,r\},ab = 0[p_i^{\alpha_i}]

On a ainsi, grâce à l’indépendance

\mathbb{P}(ab = 0 [n]) = \prod_{i=1}^n \mathbb{P}(ab= 0 [p_i^{\alpha_i}])

Ce qui nous permet de conclure la correction de cet exercice de l’ENS

Laisser un commentaire