Criterio de Euler

En teoría de números , el criterio de Euler es una fórmula para determinar si un 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 ]}

a^{\tfrac {p-1}{2}}\equiv {\begin{cases}\;\;\,1{\pmod {p}}&{\text{ si existe un entero }}x{\text{ tal que }}x^{2}\equiv a{\pmod {p}},\\-1{\pmod {p}}&{\text{ si no existe tal entero.}}\end{cases}}

El criterio de Euler puede reformularse concisamente utilizando el símbolo de Legendre : ^{[ 4 ]}

\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 demostración utiliza el hecho de que las clases de residuos módulo un número primo forman un cuerpo . Consulte el artículo «Cuerpo primo» 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² \equiv a (mod p)$ tiene como máximo 2 soluciones para cada $a . Esto implica inmediatamente que$ $, además de 0, hay al menos p$ $-$ 1 $/ 2 residuos 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, $(px)^{2}\equiv x^{2}{\pmod {p}}.$ Esto se debe a que $(px)^{2}\equiv p^{2}-{2}{x}{p}+x^{2}\equiv x^{2}{\pmod {p}}.$ Entonces, el ${\tfrac {p-1}{2}}$ Los residuos cuadráticos distintos son: $1^{2},2^{2},...,({\tfrac {p-1}{2}})^{2}{\pmod {p}}.$

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

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

que se puede escribir como

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

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

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

o

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

Ahora bien, si $a$ es un residuo cuadrático, $a \equiv x 2$ ,

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

Así, todo 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$ $- 1/2$ $valores$ $de$ a $que hagan cero$ $el$ primer factor. Pero como señalamos al principio, hay al menos $p$ $-$ $1/2$ $residuos cuadráticos$ distintos (mod $p$ ) (además de 0). Por lo tanto, son precisamente las clases de residuos que hacen cero el primer factor. Las otras $p$ $-$ $1/2$ $clases$ $de residuos , los no residuos, deben hacer cero el segundo factor, o no cumplirían$ $el$ pequeño teorema de Fermat. Este es el criterio de Euler $.$

Prueba alternativa

Esta prueba solo utiliza el hecho de que cualquier congruencia $kx\equiv l\!\!\!{\pmod {p}}$ tiene un único (módulo) $p$ ) solución $x$ proporcionó $p$ no divide $k$ . (Esto es cierto porque como $x$ recorre todos los restos distintos de cero módulo $p$ sin repeticiones, así también $kx$ : si tenemos $kx_{1}\equiv kx_{2}{\pmod {p}}$ , entonces $p\mid k(x_{1}-x_{2})$ , por eso $p\mid (x_{1}-x_{2})$ , pero $x_{1}$ y $x_{2}$ no son congruentes módulo $p$ .) De este hecho se deduce que todos los restos no nulos módulo $p$ el cuadrado del cual no es congruente con $a$ pueden agruparse en pares no ordenados $(x,y)$ según la regla de que el producto de los miembros de cada par es congruente con $a$ módulo $p$ (ya que por este hecho para cada $y$ podemos encontrar tal $x$ , de forma única, y viceversa, y diferirán entre sí si $y^{2}$ no es congruente con $a$ ). Si $a$ no es un residuo cuadrático, esto es simplemente una reagrupación de todos $p-1$ residuos distintos de cero en $(p-1)/2$ pares, por lo tanto concluimos que $1\cdot 2\cdot ...\cdot (p-1)\equiv a^{\frac {p-1}{2}}\!\!\!{\pmod {p}}$ . Si $a$ es un residuo cuadrático, exactamente dos restos no estaban entre los emparejados, $r$ y $-r$ de tal manera que $r^{2}\equiv a\!\!\!{\pmod {p}}$ Si emparejamos esos dos restos ausentes, su producto será $-a$ en vez de $a$ , de donde en este caso $1\cdot 2\cdot ...\cdot (p-1)\equiv -a^{\frac {p-1}{2}}\!\!\!{\pmod {p}}$ En resumen, considerando estos dos casos hemos demostrado que para $a\not \equiv 0\!\!\!{\pmod {p}}$ tenemos $1\cdot 2\cdot ...\cdot (p-1)\equiv -\left({\frac {a}{p}}\right)a^{\frac {p-1}{2}}\!\!\!{\pmod {p}}$ Queda por sustituir $a=1$ (que obviamente es un cuadrado) en esta fórmula para obtener de inmediato 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 .

Ejemplos

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

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

Podemos probar manualmente los números primos p 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, observe que 17 ≡ 4 (mod 13), y 2 ² = 4.

Podemos realizar estos cálculos más rápidamente utilizando diversas propiedades de la aritmética modular y de los símbolos de Legendre.

Si continuamos 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 de la siguiente manera:

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).

Así pues, el conjunto de los residuos cuadráticos módulo 17 es {1,2,4,8,9,13,15,16}. Nótese que no fue necesario calcular los cuadrados de los valores del 9 al 16, ya que todos son negativos de los valores elevados al cuadrado previamente (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 comprobar 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 comprobar 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. $\left({\frac {a}{n}}\right)$ . Si $n$ es un primo impar, esto es igual al símbolo de Legendre y decide si $a$ es un residuo cuadrático módulo $n$ .

Por otro lado, dado que la equivalencia de $a^{\frac {n-1}{2}}$ El símbolo de Jacobi se cumple para todos los primos impares, pero no necesariamente para los números compuestos; calcular ambos y compararlos puede usarse como una prueba de primalidad, específicamente la prueba de primalidad de Solovay-Strassen . Números compuestos para los cuales la congruencia se cumple para un dado $a$ se denominan pseudoprimos de Euler-Jacobi en base $a$ .

Notas

↑ Gauss , DA, Art. 106
↑ 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.
↑ Leonard Eugene Dickson, "Historia de la teoría de los números", vol. 1, pág. 205, Chelsea Publishing, 1952
↑ Hardy y Wright, teorema 83
↑ Lemmermeyer, pág. 4 cita dos artículos, E134 y E262, del Archivo Euler.
^ 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 trabajos sobre teoría de números: todas las demostraciones 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 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 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 de Euler

[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, teorema 83

[5] Lemmermeyer, pág. 4 cita dos artículos, E134 y E262, del 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

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]