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
ap−1≡1(modp). On a donc
(ap−12−1)(ap−12+1)≡0(modp) ce qui signifie que
ap−12≡±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 p−12 résidus quadratiques modulo p et p−12 non-résidus quadratiques modulo p. Pour un entier a non divisible par p, on a par ailleurs
ap−12≡{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,…,gp−2 prennent donc toutes les valeurs entre 1 et p−1. Clairement, les nombres 1,g2,g4,…,gp−3 sont des résidus quadratiques modulo p (et sont au nombre de p−12). Montrons à présent que les puissances impaires g,g3,g5,…,gp−2 sont des non-résidus quadratiques. Supposons par l'absurde que g2m+1≡x2(modp) pour certains m et x. Comme g est une racine primitive modulo p, on peut écrire x comme gℓ. On a alors g2m+1≡x2≡g2ℓ(modp) d'où g2m+1−2ℓ≡1(modp). Vu que op(g)=p−1, cela implique que p−1 divise 2m+1−2ℓ, ce qui est impossible comme p−1 est pair alors que 2m+1−2ℓ est impair.
D'autre part, si a est un résidu quadratique modulo p, alors a≡x2(modp) pour un certain x et donc ap−12≡xp−1≡1(modp) par Fermat. Au contraire, si a est un non-résidu quadratique modulo p, on a montré que a≡g2m+1(modp) pour un certain m et on a donc
ap−12≡g(2m+1)p−12≡gm(p−1)+p−12≡gp−12(modp). Puisque op(g)=p−1, on a gp−12≢1(modp) et donc gp−12≡−1(modp) puisqu'on peut seulement obtenir −1 ou 1 comme expliqué plus haut.