¿Cuál es el resto de 2 ^ 100/1000?

Me gusta la respuesta de Sridhar Ramesh lo mejor, pero este problema es razonablemente sencillo de hacer de manera directa.

Primero, observemos que [matemáticas] \ frac {2 ^ {100}} {1000} = \ frac {2 ^ {97}} {125} [/ matemáticas].

Por supuesto, esta igualdad no significa que las dos fracciones tengan el mismo resto. Sin embargo, si escribimos:

[math] \ frac {2 ^ {97}} {125} = a + \ frac b {125} [/ math] con enteros [math] a, b [/ math], entonces se deduce que

[matemáticas] \ frac {2 ^ {100}} {1000} = a + \ frac b {125} = a + \ frac {8b} {1000} [/ matemáticas] para que tengamos (o podamos encontrar de inmediato) el resto buscar.

Ahora, [math] 128 \ mod 125 \ equiv 2 ^ 7 \ mod 125 \ equiv 3 \ mod 125 [/ math]. La proximidad de una potencia de dos a [matemática] 125 [/ matemática] simplifica el cálculo.

Entonces,

[matemáticas] 2 ^ {97} \ mod 125 \ equiv \ left (2 ^ {7} \ right) ^ {14} \ cdot 2 ^ {- 1} \ mod 125 \ equiv 2 ^ {- 1} \ cdot 3 ^ {14} \ mod 125 [/ matemáticas]

Próximo,

[matemáticas] 3 ^ {5} \ mod 125 \ equiv (250-7) \ mod 125 \ equiv -7 \ mod 125 [/ matemáticas].

Entonces,

[matemáticas] 2 ^ {- 1} \ cdot 3 ^ {14} \ mod 125 \ equiv 2 ^ {- 1} \ cdot 3 ^ {- 1} \ cdot (3 ^ 5) ^ 3 \ mod 125 \ equiv 2 ^ {- 1} \ cdot 3 ^ {- 1} \ cdot (-7) ^ 3 \ mod 125 [/ matemática]

Darse cuenta de

[matemáticas] (- 7) ^ 3 \ mod 125 \ equiv (-375 + 32) \ mod 125 \ equiv 32 \ mod 125 [/ matemáticas]

Entonces

[matemáticas] 2 ^ {- 1} \ cdot (-7) ^ 3 \ mod 125 \ equiv 2 ^ {- 1} \ cdot 32 \ mod 125 \ equiv 16 \ mod 125 [/ matemáticas]

Finalmente, vemos que

[matemáticas] 2 ^ {97} \ mod 125 \ equiv 2 ^ {- 1} \ cdot 3 ^ {- 1} \ cdot (-7) ^ 3 \ mod 125 \ equiv 3 ^ {- 1} \ cdot 16 \ mod 125 [/ matemáticas]

Como [math] 3 [/ math] no divide [math] 16 [/ math], no obtenemos directamente el resultado, pero notamos que [math] 3 [/ math] divide la suma de [math] 16 [/ math] y [math] 125 [/ math] así que en su lugar, vemos que:

[matemáticas] 2 ^ {97} \ mod 125 \ equiv 3 ^ {- 1} \ cdot 16 \ mod 125 \ equiv 3 ^ {- 1} \ cdot (125 + 16) \ mod 125 \ equiv 47 \ mod 125 [ /matemáticas]

Finalmente, sabemos que

[matemáticas] 2 ^ {97} \ mod 125 \ equiv 47 \ mod 125 \ \ implica \ 2 ^ {100} \ mod 1000 \ equiv 8 \ cdot 47 \ mod 1000 \ equiv 376 \ mod 1000 [/ matemáticas]

Espero que este enfoque (intencionalmente) poco elegante ayude a enfatizar el poder del teorema del resto chino, que es la herramienta en el corazón de la solución mucho más corta de Sridhar que uní anteriormente.

2 ^ 100

= (2 ^ 10) ^ 10

= {1024} ^ 10

2 ^ 10 = 1024≡24mod1000

2 ^ 100 = (2 ^ 10) ^ 10≡24 ^ 10mod1000 = 576 ^ 5mod1000

■■ Lanzando 1000’s

(i) 576 ^ 5 = (570 + 6) ^ 5 = 570 ^ 5 + 5 * 6 * 570 ^ 4 + 10 * 6² * 570³ + 10 * 6³ * 570² +

5 * 6 ^ 4 * 570 + 6 ^ 5 = 1000A + 57 * 800 * 81 * + 32 * 243 【5 * 2 ^ 4 * 3 ^ 4 * 57 * 10 = 5 * 2 * 10 * 8 * 81 * 57 】

(ii) (a) 57 * 81 = {40 + 6} (61) (7) = 4617 = 4k + 617

(b) 800 {4k + 617}

(c) 800 * 617 = 800 (600 + 17) = 480k + 13,600

(iii) 243 * 32 = {2 * 3} {12 + 2 * 2 = 16} {9 + 8 = 17} {6} = 7776 = 7,000 + 776

(iv) 600 + 776 = 1376 = 1000 + 376

376 es el resto

Quora está llena de preguntas como esta, y no sé por qué. Pero de todos modos, podemos ser inteligentes al respecto:

Para conocer un valor mod 1000 = 10 ^ 3, necesita conocerlo mod 2 ^ 3 y mod 5 ^ 3. Bueno, 2 ^ 100 es, por supuesto, 0 mod 2 ^ 3.

¿Qué tal 2 ^ 100 mod 5 ^ 3? Bueno, 2 ^ 100 = (2 ^ 4) ^ (5 ^ 2) y 2 ^ 4 = 1 mod 5. Entonces (2 ^ 4) ^ (5 ^ 2) = (1 + 5k) ^ (5 ^ 2) , y expandiendo esto por el teorema binomial, todos los términos son divisibles por 5 ^ 3 excepto el inicial 1. Entonces 2 ^ 100 = 1 mod 5 ^ 3.

Entonces, el resto de 2 ^ 100/1000 es el valor que es 0 mod 2 ^ 3 y 1 mod 5 ^ 3. Es decir, es el valor de ambos lados de la ecuación 2 ^ 3 a = 1 + 5 ^ 3 b.

Reorganizando esto, obtenemos 2 ^ 3 a – 5 ^ 3 b = 1, y una forma de interpretar esto es que b es el recíproco de -5 ^ 3 mod 2 ^ 3.

También resulta que en la aritmética mod 2 ^ 3, cada valor impar se ajusta a 1 y, por lo tanto, es su propio recíproco (para (1 + 2k) ^ 2 = 1 + 2 ^ 2 (k + k ^ 2), y como k + k ^ 2 siempre es par, esto es 1 mod 2 ^ 3). Entonces -5 ^ 3 = -5 = 3 mod 8 y por lo tanto b = 3.

Y así, el resto que buscamos es 1 + 5 ^ 3 * 3 = 376.

[matemáticas] 2 ^ {100} = (2 ^ {10}) ^ {10} = (1024) ^ {10} = 24 ^ {10} (mod 1000) ≡ 576 ^ 5 (mod 1000) ≡ 776 ^ 2.576 (mod 1000) ≡ 176 * 576 (mod 1000) ≡ 376 (mod 1000) [/ matemática]
Entonces el resto es [matemáticas] 376 [/ matemáticas].