Critère d'Euler

$\forall x \not = 0, (x^{(p-1)/2})^2=x^{p-1} \equiv 1 [n]$donc x^(p-1)/2 est dans $\textrm{Ker}f={\pm 1}$.Im(f) est un sous-groupe de F_p^* de cardinal $\frac{p-1}{2}$.Si x est un carré non nul, on a $x \in$ Im (f) et donc $x^{(p-1)/2}=(y^2)^{(p-1)/2}=y^{p-1}\equiv 1 [p]$.D'autre part, remarquons que l'ensemble des racines du polynômes X^(p-1)/2-1 contient les $\frac{p-1}{2}$ carrés non nuls. Or ce polynôme a au plus $\frac{p-1}{2}$ racines. Donc les racines de X^(p-1)/2-1 et les carrés non nuls coïncident.

On en déduit le critère d'Euler : x est carré non nul si et seulement si

x^(p-1)/2=1.

En résumé, avec le symbole de Legendre : $\left(\frac{x}{p}\right) \equiv x^{(p-1)/2}\ [p]$.

Il est intéressant de citer le critère d'Euler généralisé aux résidus n-ièmes : en posant q=pgcd(n, p-1), $x^n \equiv a \ [p]$ est résoluble si et seulement si $a^\frac{p-1}{q} \equiv 1 \ [p]$ et il y a alors q racines modulo p. On a donc, au total, 1+(p-1)/q résidus n-ièmes et (q-1)(p-1)/q non résidus dans ${\mathbb Z}/p{\mathbb Z}$.

Vinogradov a par ailleurs montré que le nombre R de résidus quadratiques compris entre 1 et $n\leq p-1$ est $R=\frac{1}{2} n+ \theta \sqrt{p} \ln p$ où $\vert\theta \vert \leq 1$ et a formulé l'hypothèse que la distance entre deux non résidus est $O(p^\varepsilon)$, Linnik a d'ailleurs montré que c'était ``presque toujours'' le cas. En outre, le plus petit non résidu quadratique est $\leq p^{1/(2 \sqrt e)} (\ln p)^2$.