Criterio de euler

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 entero coprimo de p. Entonces

${displaystyle a^{tfrac {p-1}{2}equiv {begin{cases};;,1{pmod {p} {text{ if there is an integer }x{text{ such that }aequiv} Si no hay tal entero.$

El criterio de Euler se puede reformular de manera concisa utilizando el símbolo de Legendre:

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

El criterio apareció por primera vez en un artículo de 1748 de Leonhard Euler.

Prueba

La prueba utiliza el hecho de que las clases de residuos módulo un número primo son un campo. Consulte el artículo campo principal 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² ≡ a (modificación 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ñada de otra para dar el mismo residuo.

De hecho, ${displaystyle (p-x)^{2}equiv x^{2}{pmod {p}}$Esto es porque ${displaystyle (p-x)^{2}equiv ¿Qué? ¿Qué?$Así que... ${fnMicroc} {p-1}{2}}$ distintos residuos cuadráticos son: ${displaystyle 1^{2},2^{2},({tfrac {p-1}{2}} {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}-1right)left(a^{tfrac {p-1}{2}+1right)equiv ¿Qué?$

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²,

${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, notamos que no puede haber más que p − 1/2 valores de a que hacen que el primer factor sea cero. Pero como notamos 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 las que hacen que el primer factor sea cero. El otro p − 1/2 las 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 sólo utiliza el hecho de que cualquier congruencia ${displaystyle kxequiv l!! {pmodp}}$ tiene un único (modulo ${displaystyle p}$) solución ${displaystyle x}$ proporcionadas ${displaystyle p}$ no divide ${displaystyle k}$. (Esto es verdad porque como ${displaystyle x}$ se ejecuta a través de todos los módulos no ceros ${displaystyle p}$ sin repeticiones, también lo hace ${displaystyle kx}$ - si tenemos ${displaystyle kx_{1}equiv kx_{2}{pmod {p}}$, entonces ${displaystyle pmid k(x_{1}-x_{2}}$, por lo tanto ${displaystyle pmid (x_{1}-x_{2}}$, pero ${displaystyle x_{1}}$ y ${displaystyle x_{2}$ no son modulos congruentes ${displaystyle p}$.) Se deriva de este hecho de que todos los no cero restantes modulo ${displaystyle p}$ el cuadrado de que no es congruente con ${displaystyle a}$ se pueden agrupar en pares sin orden ${displaystyle (x,y)}$ según la regla de que el producto de los miembros de cada par es congruente con ${displaystyle a}$ modulo ${displaystyle p}$ (ya por este hecho para todos ${displaystyle y}$ podemos encontrar tal ${displaystyle x}$, singularmente, y viceversa, y ellos difieren entre sí si ${displaystyle y^{2}$ no es congruente con ${displaystyle a}$). Si ${displaystyle a}$ es un no residual cuadrático, esto es simplemente una reagrupación de todo ${displaystyle p-1}$ residuos no cero en ${displaystyle (p-1)/2}$ pares, por lo tanto concluimos que ${displaystyle 1cdot 2cdot...cdot (p-1)equiv a^{frac ¡Oh! {p}}$. Si ${displaystyle a}$ es un residuo cuadrático, exactamente dos restos no estaban entre los pares, ${displaystyle r}$ y ${displaystyle -r}$ tales que ${displaystyle ¡Oh!$. Si emparejamos esos dos restos ausentes juntos, su producto será ${displaystyle -a}$ en lugar de ${displaystyle a}$, cuando en este caso ${displaystyle 1cdot 2cdot...cdot (p-1)equiv -a^{frac ¡Oh! {p}}$. En resumen, considerando estos dos casos hemos demostrado que ${displaystyle anot equiv ¡Oh!$ tenemos ${displaystyle 1cdot 2cdot...cdot (p-1)equiv -left({frac {}{p}right)a^{frac ¡Oh! {p}}$. Queda por sustituir ${displaystyle a=1}$ (que es obviamente un cuadrado) en esta fórmula para obtener a la vez el teorema de Wilson, el criterio de Euler, y (cuando ambos lados del criterio de Euler) el pequeño teorema de Fermat.

Ejemplos

Ejemplo 1: encontrar números primos para los que a es un residuo

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

Podemos probar los p's 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 usando varias aritméticas modulares y propiedades de símbolos de Legendre.

Si seguimos calculando los valores, encontramos:

(17/p) = +1 para p = {13, 19,...} (17 es un modulo de residuos cuadráticos estos valores)

(17/p) = 1 para p = {3, 5, 7, 11, 23,...} (17 no es un modulo de residuos cuadráticos 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² (mod 17)

7² (mod 17)

8² = 64 ≡ 13 (mod 17).

Entonces el conjunto de los residuos cuadráticos módulo 17 es {1,2,4,8,9,13,15,16}. Tenga en cuenta que no necesitábamos calcular los cuadrados para los valores del 9 al 16, ya que todos son negativos de los valores cuadrados anteriores (por ejemplo, 9 ≡ −8 (mod 17), por lo que 9² ≡ (− 8)² = 64 ≡ 13 (módulo 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 residuo. 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 Euclid para calcular el símbolo Jacobi ${displaystyle left({frac {n}right)}$. Si ${displaystyle n}$ es un principio extraño, esto es igual al símbolo Legendre, y decide si ${displaystyle a}$ es un modulo de residuos cuadráticos ${displaystyle n}$.

Por otra parte, desde la equivalencia ${displaystyle a^{frac {n-1}{2}}$ con el símbolo Jacobi sostiene para todos los primos impares, pero no necesariamente para los números compuestos, calcular ambos y compararlos puede ser utilizado como una prueba de primalidad, específicamente la prueba de primalidad Solovay-Strassen. Números compuestos para los cuales la congruencia sostiene para un dado ${displaystyle a}$ se llaman Euler-Jacobi pseudoprimes a base ${displaystyle a}$.