Criteri d'Euler

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{\pmod {p}}$

Demostració

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

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

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

$X^{(p-1)/2}$	$\equiv (b^{i})^{(p-1)/2}{\pmod {p}}$
	$\equiv b^{i(p-1)/2}{\pmod {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}$.