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 ≡ 1 ( mod p ) {\displaystyle X^{(p-1)/2}\equiv 1{\pmod {p}}}

Demostració

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

X ( p − 1 ) / 2 {\displaystyle X^{(p-1)/2}} ≡ ( y 2 ) ( p − 1 ) / 2 ( mod p ) {\displaystyle \equiv (y^{2})^{(p-1)/2}{\pmod {p}}}
≡ y p − 1 ( mod p ) {\displaystyle \equiv y^{p-1}{\pmod {p}}}
≡ 1 ( mod p ) {\displaystyle \equiv 1{\pmod {p}}}

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

X ( p − 1 ) / 2 {\displaystyle X^{(p-1)/2}} ≡ ( b i ) ( p − 1 ) / 2 ( mod p ) {\displaystyle \equiv (b^{i})^{(p-1)/2}{\pmod {p}}}
≡ b i ( p − 1 ) / 2 ( mod p ) {\displaystyle \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 ± b i / 2 {\displaystyle \pm b^{i/2}} .