$2^{1008} \mod 2017$

Question

Encontrar $2^{1008} \mod 2017$

A partir de Fermat podemos encontrar que $2^{2016} \equiv 1 \mod 2017$.
Pero ahora no podemos decir que $2^{1008} \equiv 1 \mod 2017$. Puede ser$-1$. Pero, ¿cómo demostrar que es igual a $1$?

Answer 1

Una forma sería la de encontrar $2^{1008} \pmod{2017}$ usando el binario de expansión de $1008 = 1111110000_{(2)}$.

Otro método utiliza cuadrática de los residuos: Desde 2017 es un primer $\equiv 1\pmod{8}$, 2 es un residuo cuadrático mod de 2017. (ver https://en.wikipedia.org/wiki/Quadratic_residue )

Luego existen valores de $r$ (más precisamente, 986 y 1031) tal que $r^2 \equiv 2 \pmod{2017}$, lo que implica que $2^{1008} \equiv r^{2016} \equiv 1\pmod{2017}$.

Answer 2

Si usted tiene la Reciprocidad Cuadrática a su disposición, a continuación, Catalin Zara de la respuesta es el camino a seguir. Si no, un poco de experimentación (y un poco de suerte), conduce a la siguiente:

$$\left(2\over2017\right)=\left(-2\over2017\right)=\left(2015\over2017\right)=\left(5\over2017\right)\left(403\over2017\right)=\left(5\over2017\right)\left(2420\over2017\right)\\=\left(5\over2017\right)\left(5\over2017\right)\left(4\over2017\right)\left(121\over2017\right)=1$$

El primer paso se basa en el teorema de que $\left(-1\over p\right)=1$ $p\equiv1$ mod $4$. Como en Zara de la respuesta, la conclusión final de $2^{1008}$ sigue del teorema que $r^{(p-1)/2}\equiv1$ mod $p$ al $\left(r\over p\right)=1$.

Añadido posterior: Un poco más de experimentación da de una forma más simple de la evaluación, utilizando la factorizations $8=2\cdot4$$2025=45\cdot45$:

$$\left(2\over2017\right)=\left(8\over2017\right)=\left(2025\over2017\right)=\left(45\over2017\right)^2=1$$

Answer 3

$986^2-2=2017\cdot482$.

Por lo tanto, $$2^{1008}-1\equiv986^{2016}-1\equiv0$$