Processing ...

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

Prérequis

Résumé

On dit d'un nombre a{1,,p1} 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 n2 et tout entier a premier avec n, l'ordre multiplicatif de a modulo n divise φ(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 à φ(n) ?

Définition
On dit que a est une racine primitive modulo n si son ordre multiplicatif modulo n vaut φ(n), c'est-à-dire si le plus petit nombre k1 tel que ak1(modn) est k=φ(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 φ(p1) racines primitives modulo p.

Par exemple, pour p=11, on a p1=10 et φ(p1)=φ(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,g2,,gp2 modulo p parcourent alors tous les nombres entre 1 et p1. 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 xZ tel que x2a(modp). 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 p1. 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 ap11(modp). On a donc
(ap121)(ap12+1)0(modp) ce qui signifie que ap12±1(modp) (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 p12 résidus quadratiques modulo p et p12 non-résidus quadratiques modulo p. Pour un entier a non divisible par p, on a par ailleurs
ap12{1(modp) si a est un résidu quadratique modulo p,1(modp) si a est un non-résidu quadratique modulo p.

Démonstration
Considérons g une racine primitive modulo p. Les puissances successives 1,g,g2,,gp2 prennent donc toutes les valeurs entre 1 et p1. Clairement, les nombres 1,g2,g4,,gp3 sont des résidus quadratiques modulo p (et sont au nombre de p12). Montrons à présent que les puissances impaires g,g3,g5,,gp2 sont des non-résidus quadratiques. Supposons par l'absurde que g2m+1x2(modp) pour certains m et x. Comme g est une racine primitive modulo p, on peut écrire x comme g. On a alors g2m+1x2g2(modp) d'où g2m+121(modp). Vu que op(g)=p1, cela implique que p1 divise 2m+12, ce qui est impossible comme p1 est pair alors que 2m+12 est impair.
D'autre part, si a est un résidu quadratique modulo p, alors ax2(modp) pour un certain x et donc ap12xp11(modp) par Fermat. Au contraire, si a est un non-résidu quadratique modulo p, on a montré que ag2m+1(modp) pour un certain m et on a donc
ap12g(2m+1)p12gm(p1)+p12gp12(modp). Puisque op(g)=p1, on a gp121(modp) et donc gp121(modp) 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 (ap) est défini par
(ap)={1si a est un résidu quadratique modulo p,1si a est un non-résidu quadratique modulo p.

Le symbole de Legendre (ap) 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 (1p)=1 pour tout p puisque 1=12. Au vu du résultat précédent, on sait aussi que
(ap)=(ap12modp). Cette formule n'est cependant pas efficace du tout puisqu'élever un nombre à la puissance p12 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
(abp)=(ap)(bp).

Démonstration
Cela découle directement de (ab)p12=ap12bp12.

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
(1p)={1si  p1(mod4)1si  p3(mod4)

Démonstration
Cela découle simplement du fait que si p1(mod4) alors (1)p12=1, et si p3(mod4) alors (1)p12=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
(2p)={1si  p±1(mod8)1si  p±3(mod8)

Par exemple :
  • 2 est un résidu quadratique modulo 7 puisque 3292(mod7). Le résultat précédent l'avait prédit puisque 71(mod8).
  • 2 est un non-résidu quadratique modulo 5 puisque les deux résidus quadratiques sont 11242(mod5) et 42232(mod5). Le résultat nous le disait également puisque 53(mod8).

Pour un a général, il n'existe pas de formule explicite pour calculer (ap) 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 pq, on a
(pq)(qp)=(1)p12q12.

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 (ap). En effet, elle permet de remplacer un symbole (pq) par (qp), tout en faisant attention à rajouter le signe (1)p12q12. 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=y2

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 (78103). 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 (abp)=(ap)(bp) précédemment mentionnée :
(78103)=(2103)(3103)(13103). On sait déjà que (2103)=1 car 1031(mod8) (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
(78103)=(1033)(10313)=(13)(1213), 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 (13)=1, et donc
(78103)=(1213)=(113). Puisque 131(mod4), on a (113)=1 et on a donc prouvé que
(78103)=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 (2p) suivant p de calculer tous les symboles de Legendre. En effet, à chaque fois que l'on est en présence d'un symbole (ap), 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.