¿Cuál es el resto cuando 128 ^ 1000 se divide por 153?

Este es complejo y no se puede hacer por vía oral. Trataré de dar lógica para resolver tales preguntas.
Para todas las preguntas de este tipo (x a la potencia de y, se divide por z. Encuentre el resto), hay un patrón cíclico en los restos que tenemos que identificar y aprovechar.

Tomemos el caso anterior ahora:
128 ^ 1000 = 2 ^ 7 ^ 1000 = 2 ^ 7000

ahora, tenemos que encontrar el patrón cíclico cuando las potencias de 2 se dividen por 153.

(Ahora esto es algo, usé Excel para generar)

Entonces, según lo anterior, el ciclo se repite después de cada 24 iteraciones.
2 ^ 24 dividido por 153 tiene el resto de 1
2 ^ 48 dividido por 153 tiene el resto de 1

2 ^ 6984 dividido por 153 tiene el resto de 1. (6984 es 24 * 291 y el más cercano a 7000)

Por lo tanto, nos queda 2 ^ 16 (7000-6984).
El resto cuando 2 ^ 16 se divide por 153 es 52.
Por lo tanto, la respuesta es 52

52

Tenemos que averiguar Rem [128 ^ 1000/153]

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.

153 = 9 * 17
128 ^ 1000 = 2 ^ 7000

Veamos Rem [2 ^ 7000/9] y Rem [2 ^ 7000/17]
Los combinaremos más tarde.

Rem [2 ^ 7000/9]
= Rem [2 ^ 6999 x 2/9]
= Rem [8 ^ 2333 x 2/9]
= Rem [(-1) ^ 2333 x 2/9]
= Rem [(-1) x 2/9]
= – 2 de 9
= 7

Rem [2 ^ 7000/17]
= Rem [16 ^ 1750/17]
= Rem [(-1) ^ 1750/17]
= 1

Entonces, nuestra respuesta es un número que deja un resto de 7 cuando se divide entre 9 y debe dejar un resto de 1 cuando se divide entre 17 .

Comencemos considerando todos los números que dejan un resto de 1 cuando se divide por 17
=> 18 (deja un resto de 0 de 9. Inválido)
=> 35 (deja un resto de 8 de 9. Inválido)
=> 52 (deja un resto de 7 de 9. 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

La respuesta de Keval Chaudhari es excelente. Solo agregaré que está usando el teorema del resto chino como base para la solución. Además, una forma de justificar que [math] \ frac {(17-1) ^ {1750}} {17} [/ math] tiene el resto es usar el teorema de Binomial para expandir el numerador. Reconozca que cada término en la expansión es un múltiplo de alguna potencia de 17, excepto el término [matemáticas] (- 1) ^ {1750} [/ matemáticas]. Este término es obviamente uno. Entonces, cuando se agregan todos esos términos, el resultado es uno más que un múltiplo de 17. (¡Ese no es el argumento más directo para justificar ese paso, pero me gusta usar el teorema binomial siempre que sea posible!)

En general,
x ^ e = x ^ (e mod phi (n)) (mod n)

donde phi (n) es la función totient de Euler.

Phi (153) = 3 * 2 * 16 = 96.

128 ^ 1000 = 2 ^ 7000 = 2 ^ (7000 mod 96) = 2 ^ 88 (mod 153).

2 ^ 88 = (2 ^ 11) ^ 8 = 2048 ^ 8 = 59 ^ 8 = 115 ^ 4 = 67 ^ 2 = 52 (mod 153).

153 = 32 * 17 = 9 * 17
y 128 ^ 1000 = 2 ^ 1000mod9 = 2 ^ (3 * 333 + 1) mod9 = -1 * 2mod9 = 7mod9.
también 128 ^ 1000 = (-8) 1000mod17 = 2 ^ 3000mod17 = 24 * 750mod17 = 1mod17.
También 9 * 2 – 17 * 1 = 1
Uso del teorema del resto chino
128 ^ 1000 = (9 * 2 * 1 – 17 * 1 * 7) mod153 = -101mod153 = 52mod153.

Perdón por cualquier error gramatical.
(El autor de esta respuesta no se logra al escribir: P)

127 es la respuesta.

Muchos se preguntarán cómo obtuve la respuesta. Bueno, no soy una calculadora humana. Acababa de escribir un programa simple de Java para esto.

Pero la belleza de la pregunta es

resto de
((128 ^ k) / 153) = 127 por cada k> 4.

Lamento no tener ninguna explicación para la respuesta.

¿Cuál es el resto cuando 128 ^ 1000 se divide por 153?
= 128 ^ 1000
= (- 25) ^ 1000
= (13) ^ 500
= (16) ^ 250
= (103) ^ 125
= (52) ^ 62 * (103)
= (103) ^ 31 * (103); el patrón comienza, vea la segunda última línea, podemos usarlo directamente, solo estoy escribiendo los poderes por el momento, también esto es ahora
= (103) ^ 32

Solo los poderes ahora:

32
dieciséis
8
4 4
2
1

Ahora escribiendo los resultados:
32-103
16-52
8-103
4-52
2-103
1- 52

Usaremos python para esto.

Nota: ** se usa para exponentes y% se usa para encontrar el resto.

Muy bien, ¿verdad?

PD: uso Python 3.4 en mi bunsenlabs Linux

¡¡¡Que te diviertas!!!

153 = 17 * 9
dividir 128 ^ 1000 por ambos individualmente

128 ^ 1000/9 = (2 + 126) ^ 1000/9 = 2 ^ 1000/9
el resto para esto es 7

128 ^ 1000/17
Nota: Para cualquier número primo, k ^ p-1 / p deja el resto 1, aquí 128 ^ 16/17 dejaría el resto como 1.
por lo tanto 128 ^ 1000 = 128 ^ 8/17 = 9 ^ 8/17 = 13 ^ 4/17 = 1

9x + 7 = 17y + 1
x = 5 satisface
de ahí 52

153 = 9 * 17
128 ^ 1000 = 2 ^ 7000

Descubramos rem [2 ^ 7000/9] y rem [2 ^ 7000/17]
Los combinaremos más tarde.

rrem [2 ^ 7000/9 ]
= Rem [2 ^ 6999 x 2/9]
= Rem [8 ^ 2333 x 2/9]
= Rem [(-1) ^ 2333 x 2/9]
= Rem [(-1) x 2/9]
= – 2 de 9
= 7

rem [2 ^ 7000/17]
= Rem [16 ^ 1750/17]
= Rem [(-1) ^ 1750/17]
= 1

recordatorio =

17 + 1,34 + 1, 51 + 1 , 68 + 1 ……

9 + 7,18 + 7,27 + 7,36 + 7, 45 + 7 , 54 + 7 ……

Finalmente tu recordatorio = 52

En general, puede calcular a ^ b mod c rápidamente. El punto clave es que no tiene que calcular a ^ b. Solo tiene que hacer un seguimiento del mod de respuesta c.

Calcular
a ^ 1 mod c
a ^ 2 mod c
a ^ 4 mod c
a ^ 8 mod c
a ^ 16 mod c

Cada uno de ellos es un cálculo rápido, solo cuadrando mod c.

Luego, multiplique todos los a ^ (2 ^ n) para obtener a ^ b, utilizando la representación binaria de b.

52