Criterio de Euler

En la teoría de números relativa a los primos

En teoría de números , el criterio de Euler es una fórmula para determinar si un número entero es un residuo cuadrático módulo un primo . Precisamente,

Sea p un primo impar y a un entero coprimo con p . Entonces ^{[1] [2] [3]}

${\displaystyle a^{\tfrac {p-1}{2}}\equiv {\begin{cases}\;\;\,1{\pmod {p}}&{\text{ if there is an integer }}x{\text{ such that }}x^{2}\equiv a{\pmod {p}},\\-1{\pmod {p}}&{\text{ if there is no such integer.}}\end{cases}}}$

El criterio de Euler se puede reformular de forma concisa utilizando el símbolo de Legendre : ^[4]

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

El criterio data de un artículo de Leonhard Euler de 1748. ^{[5] [6]}

Prueba

La prueba se basa en el hecho de que las clases de residuos módulo un número primo son un cuerpo . Consulte el artículo sobre cuerpos primos para obtener más detalles.

Como el módulo es primo, se aplica el teorema de Lagrange : un polinomio de grado k solo puede tener k raíces como máximo. En particular, x ² ≡ a (mod p ) tiene como máximo 2 soluciones para cada a . Esto implica inmediatamente que además de 0 hay al menos ⁠pág - 1/2residuos cuadráticos distintos módulo p : cada uno de los p − 1 valores posibles de x solo puede ir acompañado de otro para dar el mismo residuo.

De hecho, esto se debe a que entonces los residuos cuadráticos distintos son: ${\displaystyle (p-x)^{2}\equiv x^{2}{\pmod {p}}.}$ ${\displaystyle (p-x)^{2}\equiv p^{2}-{2}{x}{p}+x^{2}\equiv x^{2}{\pmod {p}}.}$ ${\displaystyle {\tfrac {p-1}{2}}}$ ${\displaystyle 1^{2},2^{2},...,({\tfrac {p-1}{2}})^{2}{\pmod {p}}.}$

Como a es coprimo de p , el pequeño teorema de Fermat dice que

${\displaystyle a^{p-1}\equiv 1{\pmod {p}},}$

que puede escribirse como

${\displaystyle \left(a^{\tfrac {p-1}{2}}-1\right)\left(a^{\tfrac {p-1}{2}}+1\right)\equiv 0{\pmod {p}}.}$

Como los enteros módulo p forman un cuerpo, para cada a , uno u otro de estos factores debe ser cero. Por lo tanto,

${\displaystyle a^{\tfrac {p-1}{2}}\equiv 1{\pmod {p}}}$o

${\displaystyle a^{\tfrac {p-1}{2}}\equiv {-1}{\pmod {p}}.}$

Ahora bien, si a es un residuo cuadrático, a ≡ x ² ,

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

Por lo tanto, cada residuo cuadrático (mod p ) hace que el primer factor sea cero.

Aplicando nuevamente el teorema de Lagrange, observamos que no puede haber más de ⁠pág - 1/2⁠ valores de a que hacen que el primer factor sea cero. Pero como notamos al principio, hay al menos ⁠pág - 1/2⁠ residuos cuadráticos distintos (mod p ) (además de 0). Por lo tanto, son precisamente las clases de residuos las que hacen que el primer factor sea cero. Los otros ⁠pág - 1/2Las clases de residuos, los no residuos, deben hacer que el segundo factor sea cero, o no satisfarían el pequeño teorema de Fermat. Este es el criterio de Euler.

Prueba alternativa

Esta prueba solo usa el hecho de que cualquier congruencia tiene una solución única (módulo ) siempre que no divida a . (Esto es cierto porque como recorre todos los residuos distintos de cero módulo sin repeticiones, también lo hace —si tenemos , entonces , por lo tanto , pero y no son congruentes módulo .) De este hecho se deduce que todos los residuos distintos de cero módulo cuyo cuadrado no es congruente con se pueden agrupar en pares desordenados de acuerdo con la regla de que el producto de los miembros de cada par es congruente con módulo (ya que por este hecho para cada podemos encontrar tal , de manera única, y viceversa, y diferirán entre sí si no es congruente con ). Si no es un residuo cuadrático no cuadrático, esto es simplemente una reagrupación de todos los residuos distintos de cero en pares, por lo tanto concluimos que . Si es un residuo cuadrático, exactamente dos residuos no estaban entre los emparejados, y tales que . Si emparejamos esos dos residuos ausentes, su producto será en lugar de , de donde en este caso . En resumen, considerando estos dos casos hemos demostrado que para tenemos . Queda por sustituir (que obviamente es un cuadrado) en esta fórmula para obtener a la vez el teorema de Wilson , el criterio de Euler y (elevando al cuadrado ambos lados del criterio de Euler) el pequeño teorema de Fermat . ${\displaystyle kx\equiv l\!\!\!{\pmod {p}}}$ ${\displaystyle p}$ ${\displaystyle x}$ ${\displaystyle p}$ ${\displaystyle k}$ ${\displaystyle x}$ ${\displaystyle p}$ ${\displaystyle kx}$ ${\displaystyle kx_{1}\equiv kx_{2}{\pmod {p}}}$ ${\displaystyle p\mid k(x_{1}-x_{2})}$ ${\displaystyle p\mid (x_{1}-x_{2})}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle a}$ ${\displaystyle (x,y)}$ ${\displaystyle a}$ ${\displaystyle p}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y^{2}}$ ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle p-1}$ ${\displaystyle (p-1)/2}$ ${\displaystyle 1\cdot 2\cdot ...\cdot (p-1)\equiv a^{\frac {p-1}{2}}\!\!\!{\pmod {p}}}$ ${\displaystyle a}$ ${\displaystyle r}$ ${\displaystyle -r}$ ${\displaystyle r^{2}\equiv a\!\!\!{\pmod {p}}}$ ${\displaystyle -a}$ ${\displaystyle a}$ ${\displaystyle 1\cdot 2\cdot ...\cdot (p-1)\equiv -a^{\frac {p-1}{2}}\!\!\!{\pmod {p}}}$ ${\displaystyle a\not \equiv 0\!\!\!{\pmod {p}}}$ ${\displaystyle 1\cdot 2\cdot ...\cdot (p-1)\equiv -\left({\frac {a}{p}}\right)a^{\frac {p-1}{2}}\!\!\!{\pmod {p}}}$ ${\displaystyle a=1}$

Ejemplos

Ejemplo 1: Encontrar números primos para los cuales a es un residuo

Sea a = 17. ¿Para qué primos p es 17 un residuo cuadrático?

Podemos probar los números primos p manualmente dada la fórmula anterior.

En un caso, probando p = 3, tenemos 17 ^{(3 − 1)/2} = 17 ¹ ≡ 2 ≡ −1 (mod 3), por lo tanto, 17 no es un residuo cuadrático módulo 3.

En otro caso, probando p = 13, tenemos 17 ^{(13 − 1)/2} = 17 ⁶ ​​≡ 1 (mod 13), por lo tanto, 17 es un residuo cuadrático módulo 13. Como confirmación, note que 17 ≡ 4 (mod 13), y 2 ² = 4.

Podemos hacer estos cálculos más rápido utilizando varias propiedades de aritmética modular y símbolos de Legendre.

Si seguimos calculando los valores, encontramos:

(17/ p ) = +1 para p = {13, 19, ...} (17 es un residuo cuadrático módulo estos valores)

(17/ p ) = −1 para p = {3, 5, 7, 11, 23, ...} (17 no es un residuo cuadrático módulo estos valores).

Ejemplo 2: Hallar residuos dado un módulo primo p

¿Qué números son cuadrados módulo 17 (residuos cuadráticos módulo 17)?

Podemos calcularlo manualmente como:

1 ² = 1

2 ² = 4

3 ² = 9

4 ² = 16

5 ² = 25 ≡ 8 (mód 17)

6 ² = 36 ≡ 2 (mód 17)

7 ² = 49 ≡ 15 (mód 17)

8 ² = 64 ≡ 13 (mód 17).

Por lo tanto, el conjunto de los residuos cuadráticos módulo 17 es {1,2,4,8,9,13,15,16}. Nótese que no necesitamos calcular cuadrados para los valores del 9 al 16, ya que todos son negativos de los valores cuadrados previamente elevados (por ejemplo, 9 ≡ −8 (mod 17), por lo que 9 ² ≡ (−8) ² = 64 ≡ 13 (mod 17)).

Podemos encontrar residuos cuadráticos o verificarlos usando la fórmula anterior. Para probar si 2 es un residuo cuadrático módulo 17, calculamos 2 ^{(17 − 1)/2} = 2 ⁸ ≡ 1 (mod 17), por lo que es un residuo cuadrático. Para probar si 3 es un residuo cuadrático módulo 17, calculamos 3 ^{(17 − 1)/2} = 3 ⁸ ≡ 16 ≡ −1 (mod 17), por lo que no es un residuo cuadrático.

El criterio de Euler está relacionado con la ley de reciprocidad cuadrática .

Aplicaciones

En la práctica, es más eficiente utilizar una variante extendida del algoritmo de Euclides para calcular el símbolo de Jacobi . Si es un primo impar, es igual al símbolo de Legendre y decide si es un residuo cuadrático módulo . ${\displaystyle \left({\frac {a}{n}}\right)}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle n}$

Por otra parte, dado que la equivalencia de con el símbolo de Jacobi se cumple para todos los primos impares, pero no necesariamente para los números compuestos, calcular ambos y compararlos se puede utilizar como una prueba de primalidad, específicamente la prueba de primalidad de Solovay-Strassen . Los números compuestos para los que la congruencia se cumple para un dado se denominan pseudoprimos de Euler-Jacobi con base . ${\displaystyle a^{\frac {n-1}{2}}}$ ${\displaystyle a}$ ${\displaystyle a}$

Notas

1. Gauss , DA, Art. 106
2. Dense, Joseph B.; Dence, Thomas P. (1999). "Teorema 6.4, Cap. 6. Residuos". Elementos de la teoría de números . Harcourt Academic Press. pág. 197. ISBN 9780122091308.
3. Leonard Eugene Dickson, "Historia de la teoría de los números", vol. 1, pág. 205, Chelsea Publishing 1952
4. Hardy y Wright, tm. 83
5. Lemmermeyer, p. 4 cita dos artículos, E134 y E262 en el Archivo Euler
6. L Euler, Novi commentarii Academiae Scientiarum Imperialis Petropolitanae, 8, 1760-1, 74; Anal opúsculo. 1, 1772, 121; Com. Arit, 1, 274, 487

Referencias

Las Disquisitiones Arithmeticae han sido traducidas del latín ciceroniano de Gauss al inglés y al alemán . La edición alemana incluye todos sus artículos sobre teoría de números: todas las pruebas de reciprocidad cuadrática , la determinación del signo de la suma de Gauss , las investigaciones sobre reciprocidad bicuadrática y notas inéditas.

• Gauss, Carl Friedrich (1986), Disquisitiones Arithemeticae (Segunda edición corregida) , traducido por Clarke, Arthur A. (inglés), Nueva York: Springer , ISBN 0-387-96254-9

• Gauss, Carl Friedrich (1965), Untersuchungen über höhere Arithmetik (Disquisitiones Arithmeticae y otros artículos sobre teoría de números) (Segunda edición) , traducido por Maser, H. (alemán), Nueva York: Chelsea, ISBN 0-8284-0191-8

• Hardy, GH ; Wright, EM (1980), Introducción a la teoría de números (quinta edición) , Oxford: Oxford University Press , ISBN 978-0-19-853171-5

• Lemmermeyer, Franz (2000), Leyes de reciprocidad: de Euler a Eisenstein , Berlín: Springer , ISBN 3-540-66957-4

Enlaces externos

• El Archivo Euler