Tengo que resolver esta ecuación $2^{133} \equiv x \mod 133 $ Utilizando el teorema de Euler lo reduje a $2^{25} \equiv x \mod 133$ pero no se me ocurrió ninguna forma rápida de proceder después de esto.
¿Alguna idea?
Respuestas
¿Demasiados anuncios?
HINT $\ $ para los primos $\rm\: p\ne q,\ \ p\!-\!1\ |\ q\!-\!1\ \Rightarrow\ c^{q}\equiv\: c\pmod{p\:q}\ $ por el pequeño Teorema de Fermat.
Así que para $\rm\:p,q = 7,19,\ c = 2^7\:$ deducimos que $\rm\: 2^{\:7\:\cdot\: 19}\equiv 2^7\equiv 128 \equiv {-}5 \pmod{7\cdot 19}\ \ $ QED
Prueba $\ $ Supongamos que $\rm\ p \ne q\ $ son primos y $\rm\: q = 1 + k\:(p-1)\:,\ k\in \mathbb N\:.\: $ Por el pequeño Teorema de Fermat $\rm\:mod\ q\!:\ c^q = c\:;\ \ \ mod\ p\!:\ c^q =\: c^{\:1+k\:(p-1)} =\: c\ (c^{\:p-1})^{k}\equiv\: c\ $ si $\rm\:c\not\equiv\: 0\:,\:$ y $\rm\:c^q\equiv c\:$ si $\rm\:c\equiv 0\:.\:$
Por lo tanto, $\rm\:p,q\ |\ c^q-c\:$ $\:\Rightarrow\:$ $\rm\:lcm(p,q) =\: p\:q\ |\ c^q-c\:.\ \ $ QED
NOTA $\ $ La proposición anterior es un caso especial de una proposición general Teorema de Fermat-Euler-Carmichael.
Tenga en cuenta que este es otro ejemplo de optimización de casos constantes de restos chinos (CRT).
Robert Christie
Puntos
7323
Utilice $133 = 7 \times 19$ . Utilice $2^p = 2 \mod p$ para $p \in \mathbb{P}$ .
Ahora $2^{133} = (2^7)^{19} \mod 7 = 2^{19} \mod 7 = (2^7)^2 \times 2^5 = 2^2 \times 2^5 = 2^7 = 2 \mod 7$ . Del mismo modo, $2^{133} = (2^{19})^7 = 2^7 = 14 \mod 19$ . Así,
Dejemos que $x = 2^{133} \mod 133$ , entonces de $x = 14 \mod 19$ se deduce que $x = 14 + 19 \times k$ . Desde $x = 2 \mod 7$ se deduce que $(14 + 19 \times k) = 5 \times k = 2 \mod 7$ y $k = 6 \mod 7$ . De esto obtengo $2^{133} = 128 \mod 133$ .
