Criteri d'Euler

De Viquipèdia
Dreceres ràpides: navegació, cerca

En Matemàtiques, el criteri d'Euler és utilitzat per a calcular residus quadràtics

Definició[modifica | modifica el codi]

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ó[modifica | modifica el codi]

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}