Criterio de Euler

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.

Enunciado

Sea p > 2 un número primo y a un número entero coprimo con p. Entonces a es un residuo cuadrático módulo p si y solo si

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

Como corolario de este teorema se obtiene que si a no es un residuo cuadrático módulo p entonces

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

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

$a^{(p-1)/2}\equiv \left(\frac{a}{p}\right)(\mathrm{mod}p).$

Demostración

Supóngase que $a\equiv x^2(\mathrm{mod}p)$. Se sabe por el pequeño teorema de Fermat que si p es primo y es coprimo con a, es decir, p no divide al número a, entonces $a^{p-1}\equiv 1(\mathrm{mod}p)$. Luego se tiene que

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

A la inversa, se supone que $a^{(p-1)/2}\equiv 1(\mathrm{mod}p)$. Sea b un elemento primitivo módulo p. Entonces $a\equiv b^i(\mathrm{mod}p)$ para algún i. Luego se tiene que

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

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

Referencias

Bibliografía

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

Enlaces externos

• Plantilla:MathWorld
• Plantilla:Enlace roto