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 coprimo entero de p . Entonces [1] [2] [3]
El criterio de Euler se puede reformular de forma concisa utilizando el símbolo de Legendre : [4]
El criterio apareció por primera vez en un artículo de 1748 de Leonhard Euler . [5] [6]
Prueba
La demostración utiliza el hecho de que las clases de residuos módulo un número primo son un campo . Consulte el campo principal del artículo para obtener más detalles.
Debido a que el módulo es primo, se aplica el teorema de Lagrange : un polinomio de grado k solo puede tener como máximo k raíces. En particular, x 2 ≡ a (mod p ) tiene como máximo 2 soluciones para cada a . Esto implica inmediatamente que además de 0 hay al menosp - 1/2residuos cuadráticos distintos módulo p : cada uno de los p - 1 valores posibles de x solo puede ir acompañado de uno de otro para dar el mismo residuo.
De echo, Esto es porque Entonces el distintos residuos cuadráticos son:
Como una es primos entre sí a P , el pequeño teorema de Fermat dice que
que se puede escribir como
Dado que los números enteros mod p forman un campo, para cada a , uno u otro de estos factores debe ser cero.
Ahora, si a es un residuo cuadrático, a ≡ x 2 ,
Entonces, cada residuo cuadrático (mod p ) hace que el primer factor sea cero.
Aplicando el teorema de Lagrange nuevamente, notamos que no puede haber más de p - 1/2valores de a que hacen que el primer factor sea cero. Pero como señalamos al principio, hay al menosp - 1/2residuos 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. El otrop - 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 un (modulo ) solución previsto no divide . (Esto es cierto porque como se ejecuta a través de todos los módulos restantes distintos de cero sin repeticiones, también lo hace - si tenemos , luego , por eso , pero y no son módulo congruente .) De este hecho se deduce que todos los residuos distintos de cero módulo cuyo cuadrado no es congruente con se puede agrupar en pares desordenados de acuerdo con la regla de que el producto de los miembros de cada par es congruente con modulo (ya que por este hecho para cada podemos encontrar tal , de forma única, y viceversa, y se diferenciarán entre sí si no es congruente con ). Si es un no residuo cuadrático, esto es simplemente una reagrupación de todos 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 tal que . Si emparejamos esos dos residuos ausentes juntos, su producto será en vez de , de donde en este caso . En resumen, considerando estos dos casos hemos demostrado que para tenemos , Queda por sustituir (que es obviamente un cuadrado) en esta fórmula para obtener a la vez el teorema de Wilson , el criterio de Euler y (elevando ambos lados del criterio de Euler) el pequeño teorema de Fermat .
Ejemplos de
Ejemplo 1: encontrar números primos para los que a es un residuo
Sea a = 17. ¿Para qué primos p es 17 un residuo cuadrático?
Podemos probar primos p ' s manualmente dada la fórmula anterior.
En un caso, probando p = 3, tenemos 17 (3 - 1) / 2 = 17 1 ≡ 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 6 ≡ 1 (mod 13), por lo tanto 17 es un residuo cuadrático módulo 13. Como confirmación, tenga en cuenta que 17 ≡ 4 (mod 13) y 2 2 = 4.
Podemos hacer estos cálculos más rápidamente usando varias propiedades aritméticas modulares 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: Encontrar 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 2 = 1
- 2 2 = 4
- 3 2 = 9
- 4 2 = 16
- 5 2 = 25 ≡ 8 (mod 17)
- 6 2 = 36 ≡ 2 (mod 17)
- 7 2 = 49 ≡ 15 (mod 17)
- 8 2 = 64 ≡ 13 (mod 17).
Entonces, el conjunto de residuos cuadráticos módulo 17 es {1,2,4,8,9,13,15,16}. Tenga en cuenta que no necesitamos calcular cuadrados para los valores del 9 al 16, ya que todos son negativos de los valores previamente al cuadrado (por ejemplo, 9 ≡ −8 (mod 17), por lo que 9 2 ≡ (−8) 2 = 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 8 ≡ 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 8 ≡ 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, esto es igual al símbolo de Legendre, y decide si es un módulo de residuo cuadrático .
Por otro lado, dado que la equivalencia de Para el símbolo de Jacobi se aplica a todos los números primos impares, pero no necesariamente a 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 . Números compuestos para los que se cumple la congruencia para un determinadose denominan pseudoprimas de Euler-Jacobi a la base.
Notas
- ^ Gauss , DA, art. 106
- ^ Denso, Joseph B .; Dence, Thomas P. (1999). "Teorema 6.4, Capítulo 6. Residuos" . Elementos de la teoría de los números . Prensa académica de Harcourt. pag. 197. ISBN 9780122091308.
- ^ Leonard Eugene Dickson, "Historia de la teoría de los números", vol 1, p 205, Chelsea Publishing 1952
- ^ Hardy y Wright, thm. 83
- ^ Lemmermeyer, pág. 4 cita dos artículos, E134 y E262 en el Archivo Euler
- ↑ L Euler, Novi commentarii Academiae Scientiarum Imperialis Petropolitanae, 8, 1760-1, 74; Opusc Anal. 1, 1772, 121; Comm. Arith, 1, 274, 487
Referencias
The Disquisitiones Arithmeticae se ha traducido 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 la reciprocidad bicuadrática y notas inéditas.
- Gauss, Carl Friedrich; Clarke, Arthur A. (traductor al inglés) (1986), Disquisitiones Arithemeticae (Segunda edición corregida) , Nueva York: Springer , ISBN 0-387-96254-9
- Gauss, Carl Friedrich; Maser, H. (traductor al alemán) (1965), Untersuchungen über höhere Arithmetik (Disquisitiones Arithemeticae y otros artículos sobre teoría de números) (Segunda edición) , Nueva York: Chelsea, ISBN 0-8284-0191-8
- Hardy, GH ; Wright, EM (1980), Introducción a la teoría de los 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