Exercice corrigé : Oral de l’ENS 2022

Voici la correction d’un exercice d’oral de l’ENS tombé en 2022
ENS

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,

\forall i < \alpha, \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\neq 0)  &=\displaystyle \sum_{i=0}^{\alpha-1} \mathbb{P}(ab \neq 0 \cap v_p(a) = i)\\ 
&=\displaystyle \sum_{i=0}^{\alpha-1} \mathbb{P}_{v_p(a) =i}(v_p(ab) < \alpha )\mathbb{P}( v_p(a) = i)\\
&=\displaystyle \sum_{i=0}^{\alpha-1}\dfrac{p-1}{p^{i+1}}\mathbb{P}( v_p(b) <\alpha- i)\\
&=\displaystyle \sum_{i=0}^{\alpha-1}\dfrac{p-1}{p^{i+1}}\sum_{k= 0}^{\alpha-i-1} \dfrac{p-1}{p^{k+1}}\\
&=\displaystyle \dfrac{(p-1)^2}{p^2} \sum_{i=0}^{\alpha-1}\left(\dfrac{1}{p}\right)^{i}\sum_{k= 0}^{\alpha-i-1} \left(\dfrac{1}{p}\right)^{k}\\
&=\displaystyle  \dfrac{(p-1)^2}{p^2} \sum_{i=0}^{\alpha-1}\left( \dfrac{1}{p} \right)^{i}\dfrac{1-\left(\frac{1}{p}\right)^{\alpha-i}}{1-\frac{1}{p}}\\
&=\displaystyle  \dfrac{(p-1)^2}{p^2} \sum_{i=0}^{\alpha-1}\left( \dfrac{1}{p} \right)^{i}\dfrac{1-\left(\frac{1}{p}\right)^{\alpha-i}}{\frac{p-1}{p}}\\
&=\displaystyle  \dfrac{(p-1)}{p} \sum_{i=0}^{\alpha-1}\left( \dfrac{1}{p} \right)^{i+1}\left(1-\left(\frac{1}{p}\right)^{\alpha-i}\right)\\
&=\displaystyle  \dfrac{(p-1)}{p} \sum_{i=0}^{\alpha-1}\left( \dfrac{1}{p} \right)^{i}-\left( \dfrac{1}{p} \right)^{\alpha}\\
&=\displaystyle \dfrac{(p-1)}{p}\left( \dfrac{1-\left(\dfrac{1}{p}\right)^{\alpha}}{1-\dfrac{1}{p}}-\dfrac{\alpha}{p^{\alpha}}\right)\\
&=1-\left(\dfrac{1}{p}\right)^{\alpha}-\dfrac{\alpha(p-1)}{p^{\alpha+1}}\\

\end{array}

D’où

\mathbb{P}(ab=0) =\left(\dfrac{1}{p}\right)^{\alpha}+\dfrac{\alpha(p-1)}{p^{\alpha+1}}

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

Total
0
Shares

Laisser un commentaire

Articles similaires
Des idées de cadeaux pour Noël ? Vous voulez profiter du Black Friday ? Voici nos propositions de livres et objets mathématiques !
Découvrez nos idées