Buscar

Question

Encontrar $\sqrt 7 \pmod {2579}$.

Creo que entiendo cómo resuelvo una ecuación muy básica como esta:

$x^2 = 1 \pmod 5$

hacer una tabla de las posibles soluciones como esta

$x = 0 \implies x ^ 2 = 0 \ x = 1 \implies x ^ 2 = 1 \ x = 2 \implies x ^ 2 = 4 \ x = \implies 3 x ^ 2 = 4 \ x = \implies 4 x ^ 2 = 1 \ x = \implies 5 x ^ 2 = 0$

luego tomar los que trabajan. En este caso $\pm 1$ y $\pm 4$ son las raíces, pero ¿cómo hacer esto con un primer enorme que no puedo en la lista a todas las posibilidades?

Answer 1

En primer lugar, compruebe que no hay soluciones para$x^2 \equiv 7 \bmod 2579$, usando el criterio de Euler:

Si $p$ es un primo que no divide a $a$, entonces
$\qquad x^2 \equiv a \bmod p$ tiene una solución $\iff a^{\tfrac{p-1}{2}} \equiv 1 \bmod p$.

Hemos de calcular y ver que $7^{\frac{2579-1}{2}} \equiv 1 \bmod 2579$.

A continuación, encontramos las soluciones utilizando un teorema de Lagrange, que es fácil de comprobar:

Si $p \equiv 3 \bmod 4$ $a$ es una ecuación cuadrática de residuos de mod $p$, luego
$\qquad$ las soluciones de $x^2 \equiv a \bmod p$$x \equiv \pm a^{\frac{p+1}{4}} \bmod p$.

Este teorema se aplica debido a que $2579 \equiv 3 \bmod 4$ $7$ es una ecuación cuadrática de residuos de mod $2579$, como en el anterior.

Así, calculamos el $7^{645} \equiv 88 \bmod 2579$, por lo que las soluciones son $\pm 88 \bmod 2579$.