Indicatrice d’Euler

Dans cet exercice de Proba, nous avons un entier N strictement supérieur à 1 et nous choisissons de manière équiprobable un entier X parmi les entiers entre 1 et N. Nous définissons les événements AM, où M est inférieur ou égal à N, comme étant l'événement où M divise X. L'événement B correspond à X étant premier avec N. Nous notons P1 jusqu'à PR tous les diviseurs premiers de N. Pour exprimer B en fonction des APK, nous devons noter que si X est premier avec N, cela signifie qu'aucun PK ne divise X. Ainsi, B peut être exprimé comme l'intersection des complémentaires de AP1, AP2, jusqu'à APR. Pour calculer la probabilité de AM pour tout entier M qui divise N, nous considérons que N est égal à Kfois M et examinons les multiples de N plus petits que N, tous étant dans AM. Il y a K tels multiples car N est égal à K fois M. Ainsi, la probabilité de AM est égale à K/N. Ensuite, pour montrer que les événements AP1, AP2, jusqu'à APR sont mutuellement indépendants, nous utilisons la définition. Nous prenons des entiers I1 jusqu'à IK choisis parmi les nombres premiers. Étant donné que les PIJ sont premiers entre eux, le produit des probabilités est égal à la probabilité de l'intersection. Ainsi, les événements AP1, AP2, jusqu'à APR sont mutuellement indépendants. Nous en déduisons que la probabilité de B est égale au produit des probabilités des complémentaires de AP1, AP2, jusqu'à APR. En utilisant le fait que la probabilité de APJ bar est égale à 1-PJ, nous pouvons exprimer la probabilité de B comme le produit de 1 moins PJ pour J allant de 1 à R. Enfin, nous notons Phi de N comme l'indicatrice de l'ensemble des entiers plus petits que N qui sont premiers avec N. Nous montrons que Phi de N est égal à N fois le produit de 1 moins PK pour K allant de 1 à R. Cela ressemble à la probabilité de B, et en utilisant l'équiprobabilité, nous pouvons exprimer Phi de N comme N fois ce produit.