Nous avons vu grâce au théorème d'Euler-Fermat que pour tout naturel $n \geq 2$ et tout entier $a$ premier avec $n$, l'ordre multiplicatif de $a$ modulo $n$ divise $\varphi(n)$. Une question que l'on peut se poser est la suivante : étant donné un nombre $n$ fixé, existe-t-il un entier $a$ premier avec $n$ dont l'ordre multiplicatif modulo $n$ soit
égal à $\varphi(n)$ ?
Dans le cas où $n$ est premier, il existe bel et bien des racines primitives modulo $n$, et on connaît même leur nombre exact (où on ne distingue pas deux racines primitives égales modulo $n$). Il s'agit de la proposition suivante. Sa démonstration est abordable mais dépasse légèrement le cadre de ce cours ; nous ne la donnons donc pas.
Proposition
Soit $p$ un nombre premier. Il existe exactement $\varphi(p-1)$ racines primitives modulo $p$.
Par exemple, pour $p = 11$, on a $p-1 = 10$ et $\varphi(p-1) = \varphi(10) = 4$. Le résultat nous apprend donc qu'il doit y avoir exactement $4$ racines primitives modulo $11$. En effectuant le calcul on remarque facilement qu'il s'agit des nombres $2$, $6$, $7$ et $8$.
L'intérêt d'avoir une racine primitive $g$ modulo $p$ est que les puissances successives $1, g, g^2, \ldots, g^{p-2}$ modulo $p$ parcourent alors tous les nombres entre $1$ et $p-1$. Cela découle des propriétés de l'ordre multiplicatif données dans un précédent chapitre.