Criteri d'Euler

Plantilla:Falten referències En matemàtiques, el criteri d'Euler és utilitzat per a calcular residus quadràtics.

Definició

Sigui p > 2 un nombre primer. Llavors x és un residu quadràtic mòdul p si i només si

$X^{(p-1)/2}\equiv 1(\mathrm{mod}p)$

Demostració

Suposem que $x\equiv y^2(\mathrm{mod}p)$. Se sap pel petit teorema de Fermat que si p és primer, aleshores $x^{p-1}\equiv 1(\mathrm{mod}p)$. Després tenim

$X^{(p-1)/2}$	$\equiv (y^2{)}^{(p-1)/2}(\mathrm{mod}p)$
	$\equiv y^{p-1}(\mathrm{mod}p)$
	$\equiv 1(\mathrm{mod}p)$

A la inversa, suposem que $x^{(p-1)/2}\equiv 1(\mathrm{mod}p)$. Sigui b un element primitiu mòdul p. Llavors $x\equiv b^i(\mathrm{mod}p)$ per algun i. Aleshores tenim

$X^{(p-1)/2}$	$\equiv (b^i{)}^{(p-1)/2}(\mathrm{mod}p)$
	$\equiv b^{i(p-1)/2}(\mathrm{mod}p)$

Com que b és d'ordre p-1, s'ha de donar el cas que p-1 divideix i (p-1)/2. Per tant, i és parell, i les arrels quadrades de x són $\pm b^{i/2}$.