Générateurs dans Z/nZ

Bonjour,

Le groupe multiplicatif \((\Z/n\Z)^*\) n'est pas nécessairement cyclique, auquel cas on ne peut pas parler de « générateur » du groupe.

Tout groupe admet des générateurs, le vocabulaire est malheureusement ambigu. Ce qui est vrai, c'est qu'un groupe fini est cyclique si et seulement si il admet au moins une partie génératrice de cardinal $1$.

franckfranck a écrit:

* pour le groupe multiplicatif (Z/nZ)* de cardinal n-1

Attention ! Le groupe des inversibles de $\mathbb Z/n\mathbb Z$ n'est de cardinal $n-1$ que si $n$ est premier.

Pour trouver un générateur d'un groupe $G$ de cardinal $n$, on parcourt les éléments de ce groupe. Pour chaque élément, on calcule ses puissances $g^k$ pour $k$ entre $1$ et $n$. Si aucun de ces calculs ne donne le neutre sauf le dernier, c'est que $g$ est un générateur de $G$ (en fait, $g^n$ vaut automatiquement 1 par le théorème de Lagrange).

Évidemment, c'est rudimentaire et impraticable si $n$ est grand. Dans le cas des $(Z/pZ)^*$, il existe sûrement mieux mais ce sera probablement assez lent aussi.
Je lis que le groupe cyclique $(Z/pZ)^*$ a $\varphi(p - 1)$ générateurs, avec $\varphi$ la fonction indicatrice d'Euler. Donc, pour estimer la proportion des éléments de $(Z/pZ)^*$ qui en sont générateurs, il faut calculer $\frac{1}{\pi(x)} \sum_{p \leq x} \frac{\varphi(p - 1)}{p - 1}$ où la somme se fait sur les nombres premiers et $\pi$ est la fonction qui compte le nombre de premiers inférieurs à $x$. Je ne sais pas faire ça, mais en prenant tous les p < 1000 premiers, j'arrive à une proportion d'un peu plus d'un tiers. Ça ne préjuge pas de ce qui va arriver pour les premiers plus grands et du coup, j'aimerais bien voir ce calcul :-D