Comprobar si $10^{499} \equiv 1$ modulo $1997$

Question

Necesito encontrar el número más pequeño $x$ tal que $10^x\equiv 1 \pmod{1997}$ ,

Por la función de Euler sabemos $\phi(1997)=1996=4\times499$ Así que $x$ debe ser un divisor de $1996$ , por lo que tengo que comprobar si $10^{499}\equiv 1 \pmod{1997}$ pero no encuentro una forma agradable de calcularlo.

Answer 1

Quiere encontrar el orden de $10\bmod 1997$ con lápiz y papel.

Se empieza por factorizar $1997$ y comprobar que es un primo verificando que no es divisible por ningún primo bajo $\sqrt{1997} < 50$ ( por lo que sólo se comprueba $2,3,5,7,11,13,17,19,23,29,31,37,39,41,43,47$ ), lo que supone un poco de trabajo, pero no demasiado.

Ahora conocemos el grupo multiplicativo $\bmod 1997$ es isomorfo a $\mathbb Z_{1996}$ .

Factorizamos $1996$ y obtener $1996 = 2^2 \cdot 499$ con el fin de encontrar que $499$ es primo sólo tenemos que comprobar que no es divisible por $2,3,5,7,11,13,17,19,23$ .

Para saber cuál es el orden de $10\bmod 1997$ es que podemos encontrar $v_2$ y $v_{499}$ de la orden.

Para encontrar $v_{499}$ de la orden debemos comprobar si $10^{1996/499} \equiv 1 \bmod 1997$ . Esta parte es fácil porque $10^4 = 10000$ no es $1\bmod 1997$ . A continuación $v_{499}$ de la orden es $1$ .

Para encontrar $v_2$ de la orden debemos comprobar si $10^{1996/4}\equiv 1$ y si $10^{1996/2}\equiv 1 \bmod 1997$ . Primero comprobamos si $10^{499} \equiv 1 \bmod 1997$ .

Utilizamos la exponenciación al cuadrado. Primero escribimos $499$ en binario, es $111110011$ . A continuación obtenemos la primera $9$ residuos para $10^{2^k}$ empezando por $k=0$ .

$10,100,15,225,700,735,1035,833,930$ .

De ello se desprende $2^{449} \equiv 930 \cdot 833 \cdot 1035 \cdot 735 \cdot 700 \cdot 100 \cdot 10 \bmod 1997$ .

Este número resulta ser $1996\bmod 1997$ .

Ahora, para comprobar $10^{1996/2}$ sólo tenemos que elevar al cuadrado el número anterior, que resulta ser $1$ . A continuación $v_2$ de la orden es $1$ .

Por lo tanto, el orden es $998$ .

Answer 2

Sólo un conjunto de cálculos reutilizables y sencillos $$10^3\equiv -997\pmod{1997}$$ $$10^4\equiv -9970\equiv 15\pmod{1997}$$ $$10^7\equiv -997\cdot15\equiv 1021\pmod{1997}$$ $$10^{14}\equiv 1021^2 \equiv 7\pmod{1997}$$ $$10^{42}\equiv 7^3 \equiv 343\pmod{1997}$$ $$10^{46}\equiv 343\cdot 15\equiv 1151\pmod{1997}$$ $$10^{49}\equiv 1151 \cdot (-997) \equiv 728\pmod{1997}$$ $$10^{490}\equiv 728^{10}\equiv 779^{5} \equiv 1750\cdot 1750\cdot779 \equiv 1099\cdot 779 \equiv 1405 \pmod{1997}$$ $$10^{498}\equiv 1405\cdot (15)^2 \equiv 599\pmod{1997}$$ $$10^{499}\equiv 5990 \equiv -1\pmod{1997}\tag{1}$$

---

Es Cabe destacar que $$ord_n(a) \mid \varphi(n)$$ Así que $$ord_{1997}(10) \mid \varphi(1997)=2^2\cdot 449$$ considerando $(1)$ y comprobando varias combinaciones de $2,2,449$ concluimos que $x=ord_{1997}(10)=2\cdot 499$ $$10^{2\cdot499} \equiv (-1)^2\equiv 1\pmod{1997}$$