¿Cuál es el resto de (2 ^ (90)) / 91?

Answer 1

64

Tenemos que averiguar Rem [2 ^ 90/91]

Esto parece un poco difícil si no tiene ningún teorema para encontrar restos. Tomemos un enfoque más simple y dividamos el problema en partes más pequeñas.

Este tipo de preguntas se vuelven realmente simples si comprende el concepto de residuos negativos . Siempre trate de reducir el dividendo a 1 o -1.

91 = 7 * 13

Veamos Rem [2 ^ 90/7] y Rem [2 ^ 90/13]
Los combinaremos más tarde.

Rem [2 ^ 90/7]
= Rem [(2 ^ 3) ^ 30/7]
= Rem [8 ^ 30/7]
= Rem [1 ^ 30/7]
= 1

Rem [2 ^ 90/13]
= Rem [(2 ^ 6) ^ 15/13]
= Rem [64 ^ 15/13]
= Rem [(-1) ^ 15/13]
= -1 de 13
= 12

Entonces, nuestra respuesta es un número que deja un resto de 1 cuando se divide por 7 y debe dejar un resto de 12 cuando se divide por 13 .

Comencemos considerando todos los números que dejan un resto de 12 cuando se divide por 13
=> 12 (deja un resto de 5 de 7. Inválido)
=> 25 (deja un resto de 4 de 7. Inválido)
=> 38 (deja un resto de 3 de 7. Inválido)
=> 51 (deja un resto de 2 de 7. Inválido)
=> 64 (deja un resto de 1 de 7. Válido. Esta es nuestra respuesta)

He respondido un montón de preguntas muy similares sobre los residuos. Puede obtener la lista completa aquí: Teorema restante y conceptos relacionados para la preparación de CAT por Ravi Handa en Preparación de CAT

Answer 2

La respuesta es 64. ¿Cómo?

Sabemos que 91 = 7 * 13

Por el pequeño teorema de Fermat:

[matemáticas] 2 ^ {12} [/ matemáticas] mod 13 = 1

Así,

[matemáticas] 2 ^ {90} [/ matemáticas] mod 13
= [matemáticas] (2 ^ {12}) ^ 7 * 2 ^ 6 [/ matemáticas] mod 13
= [matemáticas] 2 ^ 6 [/ matemáticas] mod 13
= 64 mod 13
= 12

Además, desde el mismo teorum:

[matemáticas] 2 ^ 6 [/ matemáticas] mod 7 = 1

Aplicando el mismo módulo aritmático que el anterior:

[matemáticas] 2 ^ {90} [/ matemáticas] mod 7 = 1

Ahora, dado que 91 = 7 * 13, [math] 2 ^ {90} [/ math] mod 91 debe producir un resto que produce 12 cuando se divide por 13 y 1 cuando se divide por 7.

Entonces, el método de prueba y golpe simple al poner 0,1, 2 … en 13x + 12 y verificar si produce 1 cuando se divide por 7 nos da la respuesta como 64

Answer 3

2 ^ 90 = 1237940039285380274899124224
(2 ^ 90) Mod 91 = 64