Théorie > Théorie des nombres > Résidus quadratiques


Général

Introduction Chapitre entier

Points théoriques

Racines primitives Résidus quadratiques Symbole de Legendre Loi de réciprocité quadratique

Exercices

Exercice 1 Exercice 2 Exercice 3 Exercice 4 Exercice 5

Racines primitives

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)$ ? Un nombre $a$ vérifiant cette propriété est appelé racine primitive modulo $n$, et la question revient donc à demander si, $n$ étant fixé, il existe une racine primitive modulo $n$.

Dans le cas où $n$ est premier, la réponse est affirmative et on connaît même le nombre exact de racines primitives modulo $n$ (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.

Soit $p$ un nombre premier. Il existe exactement $\varphi(p-1)$ racines primitives modulo $p$, où $\varphi$ désigne l'indicatrice d'Euler.

Exemple :
Considérons $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 le chapitre précédent.

Remarque :
Lorsque $n$ n'est pas premier, il n'est pas toujours vrai qu'il existe une racine primitive modulo $n$. On connaît en fait exactement les nombres $n$ tels qu'il existe une racine primitive modulo $n$ : il faut que $n$ soit égal à $2$ ou $4$ ou une puissance d'un nombre premier impair ou le double d'une puissance d'un nombre premier impair. Ce résultat dépasse cependant largement le cadre du cours.