Racines primitives et 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

Prérequis

Théorème d'Euler-Fermat

Résumé

On dit d'un nombre

$a \in \{1, \ldots, p-1\}$ qu'il est résidu quadratique modulo

$p$ s'il existe un carré parfait congru à

$a$ modulo

$p$ . Dans ce chapitre, nous donnons une façon de déterminer si un nombre est résidu quadratique modulo

$p$ ou non à l'aide du symbole de Legendre. La notion de racine primitive modulo

$p$ est également introduite.

Ce chapitre a été écrit par N. Radu et mis en ligne le 4 janvier 2015.

1. 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$ .

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.

2. Résidus quadratiques

Définition

Étant donné un nombre premier impair

$p$ , on dit qu'un entier

$a$ non divisible par

$p$ est un résidu quadratique modulo

$p$ s'il existe

$x \in \mathbb{Z}$ tel que

$x^2 \equiv a \pmod p$ . Dans le cas contraire, on dit que

$a$ est un non-résidu quadratique modulo

$p$ .

Puisqu'on travaille modulo

$p$ et qu'on exclut les nombres divisibles par

$p$ , on étudie en fait essentiellement les nombres entre

$1$ et

$p-1$ . On ne distinguera plus dans la suite deux nombres égaux modulo

$p$ .

Le premier résultat suivant nous indique qu'il existe autant de résidus quadratiques que de non-résidus quadratiques modulo

$p$ fixé et donne une certaine caractérisation de ceux-ci. Rappelons que par le théorème de Fermat, si

$a$ n'est pas divisible par

$p$ alors

$a^{p-1} \equiv 1 \pmod p$ . On a donc

$(a^{\frac{p-1}{2}}-1) (a^{\frac{p-1}{2}}+1) \equiv 0 \pmod p$ ce qui signifie que

$a^{\frac{p-1}{2}} \equiv \pm 1 \pmod p$ (on utilise ici que

$p$ est premier, cette affirmation n'est pas vraie lorsque

$p$ est composé).

Proposition

Soit

$p$ un nombre premier impair. Il existe exactement

$\frac{p-1}{2}$ résidus quadratiques modulo

$p$ et

$\frac{p-1}{2}$ non-résidus quadratiques modulo

$p$ . Pour un entier

$a$ non divisible par

$p$ , on a par ailleurs

$a^\frac{p-1}{2} \equiv \begin{cases} 1 & \pmod p \quad\text{ si $a$ est un résidu quadratique modulo $p$,}\\ -1 & \pmod p \quad\text{ si $a$ est un non-résidu quadratique modulo $p$.} \end{cases}$

Démonstration

Considérons

$g$ une racine primitive modulo

$p$ . Les puissances successives

$1, g, g^2, \ldots, g^{p-2}$ prennent donc toutes les valeurs entre

$1$ et

$p-1$ . Clairement, les nombres

$1, g^2, g^4, \ldots, g^{p-3}$ sont des résidus quadratiques modulo

$p$ (et sont au nombre de

$\frac{p-1}{2}$ ). Montrons à présent que les puissances impaires

$g, g^3, g^5, \ldots, g^{p-2}$ sont des non-résidus quadratiques. Supposons par l'absurde que

$g^{2m+1} \equiv x^2 \pmod p$ pour certains

$m$ et

$x$ . Comme

$g$ est une racine primitive modulo

$p$ , on peut écrire

$x$ comme

$g^\ell$ . On a alors

$g^{2m+1} \equiv x^2 \equiv g^{2\ell} \pmod p$ d'où

$g^{2m+1-2\ell} \equiv 1 \pmod p$ . Vu que

$o_p(g) = p-1$ , cela implique que

$p-1$ divise

$2m+1-2\ell$ , ce qui est impossible comme

$p-1$ est pair alors que

$2m+1-2\ell$ est impair.
D'autre part, si

$a$ est un résidu quadratique modulo

$p$ , alors

$a \equiv x^2 \pmod p$ pour un certain

$x$ et donc

$a^\frac{p-1}{2} \equiv x^{p-1} \equiv 1 \pmod p$ par Fermat. Au contraire, si

$a$ est un non-résidu quadratique modulo

$p$ , on a montré que

$a \equiv g^{2m+1} \pmod p$ pour un certain

$m$ et on a donc

$a^\frac{p-1}{2} \equiv g^{(2m+1)\frac{p-1}{2}} \equiv g^{m(p-1)+\frac{p-1}{2}} \equiv g^\frac{p-1}{2} \pmod p.$ Puisque

$o_p(g) = p-1$ , on a

$g^\frac{p-1}{2} \not \equiv 1 \pmod p$ et donc

$g^\frac{p-1}{2} \equiv -1 \pmod p$ puisqu'on peut seulement obtenir

$-1$ ou

$1$ comme expliqué plus haut.

3. Symbole de Legendre

Le symbole de Legendre est défini comme suit.

Définition

Soit

$p$ un nombre premier impair et

$a$ un entier non divisible par

$p$ . Le symbole de Legendre

$\left(\frac{a}{p}\right)$ est défini par

$\left(\frac{a}{p}\right) = \begin{cases} 1 & \text{si $a$ est un résidu quadratique modulo $p$,}\\ -1 & \text{si $a$ est un non-résidu quadratique modulo $p$.} \end{cases}$

Le symbole de Legendre

$\left(\frac{a}{p}\right)$ indique donc si

$a$ est un résidu quadratique modulo

$p$ ou non, et nous consacrons la suite de ce chapitre à trouver comment calculer la valeur de ce symbole en un temps raisonnable. Premièrement, on a bien sûr

$\left(\frac{1}{p}\right) = 1$ pour tout

$p$ puisque

$1 = 1^2$ . Au vu du résultat précédent, on sait aussi que

$\left(\frac{a}{p}\right) = (a^\frac{p-1}{2} \bmod p).$ Cette formule n'est cependant pas efficace du tout puisqu'élever un nombre à la puissance

$\frac{p-1}{2}$ est presque aussi lent que tester toutes les racines carrées possibles pour

$a$ . On peut cependant en déduire le résultat suivant.

Lemme

Soit

$p$ un nombre premier impair et

$a$ ,

$b$ des entiers non divisibles par

$p$ . On a

$\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right) \left(\frac{b}{p}\right).$

Démonstration

Cela découle directement de

$(ab)^\frac{p-1}{2} = a^\frac{p-1}{2} \cdot b^\frac{p-1}{2}$ .

Il est aussi possible de savoir facilement en fonction de

$p$ si

$-1$ est un carré modulo

$p$ ou non.

Lemme

Soit

$p$ un nombre premier impair. On a

$\left(\frac{-1}{p}\right) = \begin{cases} 1 & \text{si }\ p \equiv 1 \pmod 4 \\ -1 &\text{si }\ p \equiv 3 \pmod 4 \end{cases}$

Démonstration

Cela découle simplement du fait que si

$p \equiv 1 \pmod 4$ alors

$(-1)^\frac{p-1}{2} = 1$ , et si

$p \equiv 3 \pmod 4$ alors

$(-1)^\frac{p-1}{2} = -1$ .

Il existe aussi une formule du même type pour savoir si

$2$ est un résidu quadratique modulo

$p$ ou non. Celle-ci est cependant plus complexe à prouver et nous n'en donnons dès lors que l'énoncé.

Proposition

Soit

$p$ un nombre premier impair. On a

$\left(\frac{2}{p}\right) = \begin{cases} 1 & \text{si }\ p \equiv \pm 1 \pmod 8 \\ -1 &\text{si }\ p \equiv \pm 3 \pmod 8 \end{cases}$

Par exemple :

$2$ est un résidu quadratique modulo $7$ puisque $3^2 \equiv 9 \equiv 2 \pmod 7$ . Le résultat précédent l'avait prédit puisque $7 \equiv -1 \pmod 8$ .
$2$ est un non-résidu quadratique modulo $5$ puisque les deux résidus quadratiques sont $1 \equiv 1^2 \equiv 4^2 \pmod 5$ et $4 \equiv 2^2 \equiv 3^2 \pmod 5$ . Le résultat nous le disait également puisque $5 \equiv -3 \pmod 8$ .

Pour un

$a$ général, il n'existe pas de formule explicite pour calculer

$\left(\frac{a}{p}\right)$ en fonction de

$p$ . C'est la loi de réciprocité quadratique qui va nous permettre de tout de même calculer ce symbole.

4. Loi de réciprocité quadratique

La loi de réciprocité quadratique s'énonce comme suit. Elle fut conjecturée par Euler et Legendre et prouvée par Gauss.

Loi de réciprocité quadratique

Pour tous nombres premiers impairs

$p$ et

$q$ avec

$p \neq q$ , on a

$\left(\frac{p}{q}\right) \cdot \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \frac{q-1}{2}}.$

Nous n'en donnons pas la démonstration.

L'intérêt de cette formule est qu'elle permet de calculer plus facilement tout symbole de Legendre

$\left(\frac{a}{p}\right)$ . En effet, elle permet de remplacer un symbole

$\left(\frac{p}{q}\right)$ par

$\left(\frac{q}{p}\right)$ , tout en faisant attention à rajouter le signe

$(-1)^{\frac{p-1}{2}\frac{q-1}{2}}$ . Autrement dit, il faut simplement rajouter un signe

$-$ si

$p$ et

$q$ sont tous les deux égaux à

$3$ modulo

$4$ .

À titre d'exemple, examinons le problème suivant :

Problème

Trouver tous les couples d'entiers

$(x,y)$ tels que

$103x+78 = y^2$

Solution

On remarque tout de suite que l'existence d'une solution est équivalente à dire que

$78$ est un résidu quadratique modulo

$103$ . Il s'agit donc dans un premier temps de voir si cela est vrai pour déterminer si une solution existe. On doit dès lors calculer le symbole

$\left(\frac{78}{103}\right)$ . Avant de pouvoir utiliser la loi de réciprocité quadratique, il faut que le numérateur soit premier. On commence donc par décomposer

$78$ en facteurs premiers en utilisant la formule

$\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right) \left(\frac{b}{p}\right)$ précédemment mentionnée :

$\left(\frac{78}{103}\right) = \left(\frac{2}{103}\right)\left(\frac{3}{103}\right) \left(\frac{13}{103}\right).$ On sait déjà que

$\left(\frac{2}{103}\right) = 1$ car

$103 \equiv -1 \pmod 8$ (voir formule dans le cas

$a = 2$ ). On peut à présent utiliser la loi de réciprocité quadratique pour chacun des deux termes. Vu que

$3$ et

$103$ sont tous les deux égaux à

$3$ modulo

$4$ , inverser ce symbole va faire apparaître un signe

$-$ . Par contre,

$13$ est égal à

$1$ modulo

$4$ donc ce symbole n'apportera pas de signe

$-$ . On a ainsi

$\left(\frac{78}{103}\right) = - \left(\frac{103}{3}\right) \left(\frac{103}{13}\right) = -\left(\frac{1}{3}\right) \left(\frac{12}{13}\right),$ où on peut remplacer

$103$ par sa valeur modulo

$3$ dans le premier symbole et par sa valeur modulo

$13$ dans le deuxième, comme la valeur d'un symbole ne dépend que de la valeur du numérateur modulo le dénominateur. On a clairement

$\left(\frac{1}{3}\right) = 1$ , et donc

$\left(\frac{78}{103}\right) = - \left(\frac{12}{13}\right) = - \left(\frac{-1}{13}\right).$ Puisque

$13 \equiv 1 \pmod 4$ , on a

$\left(\frac{-1}{13}\right) = 1$ et on a donc prouvé que

$\left(\frac{78}{103}\right) = -1,$ ce qui signifie que

$78$ est un non-résidu quadratique modulo

$103$ et qu'il n'y a aucun couple

$(x,y)$ satisfaisant l'énoncé.

Il est possible grâce à cette loi et à la valeur de

$\left(\frac{2}{p}\right)$ suivant

$p$ de calculer tous les symboles de Legendre. En effet, à chaque fois que l'on est en présence d'un symbole

$\left(\frac{a}{p}\right)$ , on peut décomposer

$a$ en ses facteurs premiers, trouver la valeur des symboles apparaissant avec un numérateur égal à

$2$ , et retourner les autres symboles en utilisant la loi de réciprocité quadratique. En remplaçant le numérateur obtenu par sa valeur modulo le dénominateur et en répétant l'opération, les nombres en jeu deviennent de plus en plus petits et on finit par pouvoir tout calculer.

Théorie > Théorie des nombres > Racines primitives et résidus quadratiques

Général

Points théoriques

Exercices

Prérequis

Résumé

1. Racines primitives

2. Résidus quadratiques

3. Symbole de Legendre

4. Loi de réciprocité quadratique