Résidus quadratiques, critère d'Euler

(i) L'application $s : x \mapsto x^2$ est un morphisme du groupe abélien $\mathbb F_p^\times$ dans lui-même, d'image $C$. Son noyau est formé des $x$ tels que $(x - 1)(x + 1) = 0$, c'est-à-dire de $1$ et $-1$, qui sont distincts puisque $p$ est impair ; il a deux éléments.

Le théorème d'isomorphisme (Théorème d'isomorphisme) identifie $C$ au quotient de $\mathbb F_p^\times$ par ce noyau, et le théorème de Lagrange (Lagrange) donne $|C| = \frac{p-1}2$. Enfin $x^2 = y^2$ équivaut à $(yx^{-1})^2 = 1$, c'est-à-dire à $yx^{-1} = \pm 1$.

(ii) Si $p$ divise $a$, les deux membres sont congrus à $0$. Sinon, soit $b$ la classe de $a^{\frac{p-1}2}$. Alors $b^2 = \bar a^{p-1} = 1$ par le théorème de Fermat (Fermat, Euler, (iii)), donc $b = \pm 1$ par (i).

Si $\bar a = x^2$ est un carré, $b = x^{p-1} = 1$. Les $\frac{p-1}2$ éléments de $C$ sont ainsi des racines dans $\mathbb F_p$ du polynôme $X^{\frac{p-1}2} - 1$. Ce polynôme non nul, de degré $\frac{p-1}2$, a au plus $\frac{p-1}2$ racines dans le corps $\mathbb F_p$ (Racines, (iii)) : ses racines sont exactement les éléments de $C$. Si $\bar a$ n'est pas un carré, il n'en est donc pas une racine, et $b = -1$.

(iii) La définition ne fait intervenir que la classe de $a$. Par (ii), $$\Big(\frac{ab}p\Big) \equiv a^{\frac{p-1}2}\,b^{\frac{p-1}2} \equiv \Big(\frac ap\Big)\Big(\frac bp\Big) \pmod p.$$ Les deux membres appartiennent à $\{-1, 0, 1\}$, et deux éléments de cet ensemble congrus modulo $p \geqslant 3$ sont égaux, leur différence étant de valeur absolue au plus $2$.

(iv) Par (ii), $\big(\frac{-1}p\big) \equiv (-1)^{\frac{p-1}2} \pmod p$, et ces deux nombres valent $\pm 1$, donc sont égaux comme en (iii). L'entier impair $p$ est congru à $1$ ou à $3$ modulo $4$, et $\frac{p-1}2$ est pair exactement dans le premier cas.