criterio de euler

En teoría de números sobre números 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 primo . Precisamente,

Sea p un primo impar y a un coprimo entero de 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 manera 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 1748 de Leonhard Euler . ^{[5] [6]}

Prueba

La prueba utiliza el hecho de que las clases de residuos módulo de 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 sólo puede tener como máximo k raíces. 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 menospag -1/2distintos residuos cuadráticos 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 los distintos residuos cuadráticos 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 se puede escribir como

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

Dado que los números enteros mod p forman un campo, 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}}.}$

Entonces, 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 quepag -1/2valores de a que hacen que el primer factor sea cero. Pero como señalamos al principio, existen al menospag -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 otropag -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. Éste es el criterio de Euler.

Prueba alternativa

Esta prueba solo utiliza el hecho de que cualquier congruencia tiene una solución única (módulo) siempre que no divida . (Esto es cierto porque como recorre todos los restos 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 restos distintos de cero módulo cuyo cuadrado es No 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 módulo (ya que por este hecho para cada uno podemos encontrar tal , unívocamente, y viceversa, y diferirán entre sí si no es congruente con ). Si no es un no residuo cuadrático, se trata simplemente de una reagrupación de todos los residuos distintos de cero en pares, por lo que concluimos que . Si es un residuo cuadrático, exactamente dos residuos no estaban entre los emparejados, y tal que . Si juntamos esos dos restos ausentes, su producto será en lugar de , de donde en este caso . En resumen, considerando estos dos casos hemos demostrado que 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 (al elevar 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 p primos 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, tenga en cuenta que 17 ≡ 4 (mod 13) y 2 ² = 4.

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

Si seguimos calculando los valores, encontramos:

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

(17/ p ) = −1 para p = {3, 5, 7, 11, 23, ...} (17 no es un módulo de residuo cuadrático de 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 ² = 1

2 ² = 4

3 ² = 9

4 ² = 16

5 ² = 25 ≡ 8 (mod 17)

6 ² = 36 ≡ 2 (mod 17)

7 ² = 49 ≡ 15 (mod 17)

8 ² = 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 necesitábamos calcular cuadrados para los valores del 9 al 16, ya que todos son negativos de los valores previamente elevados al cuadrado (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 la 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 módulo de residuo cuadrático . ${\displaystyle \left({\frac {a}{n}}\right)}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle n}$

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

Notas

1. Gauss , DA, art. 106
2. Denso, Joseph B.; Dence, Thomas P. (1999). "Teorema 6.4, Capítulo 6. Residuos". Elementos de la Teoría de Números . Prensa académica de Harcourt. pag. 197.ISBN​ 9780122091308.
3. Leonard Eugene Dickson, "Historia de la teoría de los números", vol 1, p 205, Chelsea Publishing 1952
4. Hardy y Wright, ellos. 83
5. Lemmermeyer, pag. 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 la 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 (1986), Disquisitiones Arithmeticae (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