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.^[1][2][3]

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

${\displaystyle 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

${\displaystyle 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:

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

Demostración

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

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

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

${\displaystyle a^{(p-1)/2}}$	${\displaystyle \equiv (b^{i})^{(p-1)/2}{\pmod {p}}}$
	${\displaystyle \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 ${\displaystyle \pm b^{i/2}}$.

Referencias

1. Gauss, DA, Art. 106
2. Dense, Joseph B.; Dence, Thomas P. (1999). «Theorem 6.4, Chap 6. Residues». Elements of the Theory of Numbers. Harcourt Academic Press. p. 197. ISBN 9780122091308.
3. Leonard Eugene Dickson, "History Of The Theory Of Numbers", vol 1, p 205, Chelsea Publishing 1952

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