Criterio de Euler

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En teoría de números, concretamente en aritmética modular, el criterio de Euler es utilizado para calcular si un número entero x es un residuo cuadrático módulo un número primo. Su nombre se debe al matemático suizo Leonhard Euler.

Definición[editar]

Sea p > 2 un número primo. Entonces x es un residuo cuadrático módulo p si y sólo si

x^{(p-1)/2} \equiv 1 \pmod p.

Como corolario de este teorema se obtiene que:

Si x no es un residuo cuadrático módulo p entonces

x^{(p - 1)/2} \equiv -1 \pmod p.

Así, el criterio de Euler puede ser reformulado de manera más compacta usando el símbolo de Legendre:


x^{(p-1)/2} \equiv \left(\frac{x}{p}\right) \pmod p.

Demostración[editar]

Supongamos que x \equiv y^2 \pmod p. Se sabe por el pequeño teorema de Fermat que si p es primo, entonces  x^{p-1} \equiv 1 
\pmod p . Luego tenemos

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, suponemos que x^{(p-1)/2} \equiv 1 \pmod p. Sea b un elemento primitivo modulo p. Entonces x \equiv b^i \pmod p para algún i. Entonces tenemos

 x^{(p-1)/2} \equiv (b^i)^{(p-1)/2} \pmod p
 \equiv b^{i(p-1)/2} \pmod p

Como b es de orden p-1, debe darse el caso que p-1 divide a i(p-1)/2. Por lo tanto, i es par, y las raíces cuadradas de x son \pm b^{i/2}.

Bibliografía[editar]

  • Tom M. Apostol (1976): Introduction to Analytic Number Theory, Springer-Verlag, New York. ISBN 0-387-90163-9, (Capítulo 9.2)

Enlaces externos[editar]