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

Demostración

Supóngase que $a\equiv x^{2}{\pmod {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{\pmod {p}}$. Luego se tiene que

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

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

$a^{(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 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

• Weisstein, Eric W. «Euler's Criterion». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Elvidge, Sean. «The History of the Law of Quadratic Reciprocity» (PDF) (en inglés). The University of Birmingham. Consultado el 9 de abril de 2011.  (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última).

• Datos: Q2346904