¿Pregunta sobre cálculo de $2^{32101}\bmod 143$?

Question

Estoy tratando de calcular $2^{32101}\bmod 143$ con el uso de papel y una calculadora. Lo que me molesta es que $32101 = 47 \times 683$$143=11 \times 13$, por lo que no son números primos. Esto significa que no puede usar de Fermat poco teorema. He intentado también para resolver cuadrado y multiplicar algoritmo, pero estoy atascado allí también, así que tal vez no funciona demasiado. He estado pensando en usar el Chino recordatorio teorema, pero no sé cómo aplicarlo aquí, porque de la prima facorization de $32101$...

¿Alguien tiene una idea de cómo calcular el suche grandes números que no son primos? Yo estaría encantado si alguien me puede ayudar. Gracias de antemano!

Answer 1

Bueno, ya pensaste acerca del uso de pequeño Teorema de Fermat y Teorema chino del resto, que combinados pueden hacen esto.

La idea básica es que usted puede calcular

$2^{32101} \pmod{11}$ $2^{32101} \pmod{13}$ utilizando el pequeño Teorema de Fermat, y luego usar los resultados para calcular $2^{32101} \pmod{143}$ usando el Teorema chino del resto.

Answer 2

Cuadrado y multiplicar debería funcionar. El cálculo es lo suficientemente largo que es fácil que haya cometido un error, sin embargo, si usted no es cuidadoso. Yo suelo terminar de hacer cálculos largos dos veces (espero que con las variaciones en los dos trata-por ejemplo, un cálculo puede utilizar la parte inferior variación y el otro el de arriba-abajo de variación) para obtener algo más de confianza que no tenía un error.

Usted podría romper mod 143 en mod 11 y mod 13, y hacer esas individualmente, luego se recombinan para obtener una respuesta.

La base y el módulo son relativamente primos, así que usted podría utilizar la generalización de Fermat poco teorema:

Si $\gcd(b,m) = 1$, $b^{\varphi(m)} \equiv 1 \bmod m$ donde $\varphi$ es de Euler totient función.

Answer 3

Podemos utilizar la función de Carmichael para encontrar $$\lambda(143)=60$ $

$$\implies 2^{60}\equiv1\pmod{143}\implies 2^{60a}\equiv1^a\pmod{143}\equiv1\text{ for any integer }a$$

Ahora, $32101\equiv1\pmod{100}$ y $32101\equiv1\pmod3$

$\implies 32101\equiv1\pmod{\text{lcm}(100,3)}\implies 32101\equiv1\pmod{300}$

$\implies32101\equiv1\pmod{60}$

Answer 4

Los factores de la $32101$ no importan. Lo que debe hacerse es señalar por ejemplo, que $2^{12} = 1 \pmod{13}$ y $2^{10} = 1 \pmod{11}$, que $2^{60}= 1 \pmod{143}$, donde $60 = \operatorname{lcm}(12, 10)$,

Por lo tanto, puede poner $2^{60}x = x \pmod{143}$ y así libremente restar múltiplos de $60$ $32101$. Esto equivale a $2^{32101} = 2^1 \mod{143}$, porque restando múltiplos de 60 de 32101 equivale a $32101 = 1 \pmod{60}$.

Entonces es la tarea simple de evaluar $2^1 = 2$, que es la respuesta deseada.