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


Général

Résumé 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)$ ?

Définition
On dit que $a$ est une racine primitive modulo $n$ si son ordre multiplicatif modulo $n$ vaut $\varphi(n)$, c'est-à-dire si le plus petit nombre $k \geq 1$ tel que $a^k \equiv 1 \pmod n$ est $k = \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$, où $\varphi$ désigne l'indicatrice d'Euler.

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.
:
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.