¿Cuál es el resto cuando 117 ^ 513 dividido por 100?

Answer 1

[matemáticas] 117 ^ {513} \ mod 100 [/ matemáticas]

[matemáticas] \ phi (100) = 40 [/ matemáticas]

[matemáticas] (117 \ mod100) ^ {(513 \ mod40)} \ mod 100 [/ matemáticas]

[matemáticas] 17 ^ {33} \ mod100 [/ matemáticas]

[matemáticas] 17 * (289) ^ {16} \ mod 100 [/ matemáticas]

[matemáticas] 17 * 11 ^ {16} \ mod 100 [/ matemáticas]

[matemáticas] 17 * 41 ^ 4 \ mod 100 [/ matemáticas]

[matemáticas] 17 * 19 ^ 2 \ mod 100 [/ matemáticas]

[matemáticas] = 37 [/ matemáticas]

---

metodo alternativo,

[matemáticas] 100 = 4 * 25 [/ matemáticas]

[matemáticas] 117 ^ {513} = x [/ matemáticas]

[matemáticas] x \ mod 4 = 1 [/ matemáticas]

[matemáticas] x \ mod 25 = -8 ^ {13} \ mod 25 = -128 ^ 5 * 16 = 9 * 243 = 12 [/ matemáticas]

[matemáticas] x = 4a + 1 = 25b + 12 [/ matemáticas]

[matemáticas] 4a = 25b + 11 = 25b + 36 [/ matemáticas]

[matemáticas] a = 25c + 9 [/ matemáticas]

entonces, [matemáticas] x = 4 (25c + 9) + 1 = 100c + 37 [/ matemáticas]

---

el método 1 se llama Totient de Euler y el método 2 es el teorema del resto chino

Answer 2

Requisito previo :

• Conocimiento de la expansión binomial.

El resto cuando un número se divide entre [matemáticas] 100 [/ matemáticas], no es más que los últimos [matemáticas] 2 [/ matemáticas] dígitos. Esto se puede probar usando la expansión

Simplemente amplíelo y se dará cuenta de que los términos que tienen poderes de [math] 100 [/ math] son ​​irrelevantes, ya que no desempeñarán ningún papel en la determinación de los últimos dígitos [math] 2 [/ math]. El único término significativo será [matemáticas] 17 ^ {513} [/ matemáticas] en uno de los extremos de la expansión.

Entonces, necesitamos enfocarnos solo en [matemáticas] 17 ^ {513} [/ matemáticas]. Los últimos [math] 2 [/ math] dígitos dependerán de [math] 17 \ times 17 ^ {512} [/ math]. Aquí [math] 512 [/ math] es un múltiplo de [math] 4 [/ math], por lo que podemos hacer la siguiente simplificación.

[matemáticas] 17 ^ {512} [/ matemáticas] = [matemáticas] (17 ^ 4) ^ {128} [/ matemáticas] -> [matemáticas] (17 ^ 2 \ veces 17 ^ 2) ^ {128} [/ matemáticas] -> [matemáticas] (289 \ veces 289) ^ {128} [/ matemáticas] -> [matemáticas] (89 ^ 2) ^ {128} [/ matemáticas] -> [matemáticas] (11 ^ 2) ^ {128} [/ matemáticas] -> [matemáticas] 21 ^ {128} [/ matemáticas]

Es útil saber que pares como [matemáticas] (11 ^ 2, 89 ^ 2) [/ matemáticas], [matemáticas] (17 ^ 2, 83 ^ 2) [/ matemáticas], donde las bases se suman a un múltiplo de [matemáticas ] 50 [/ math], comparte los mismos últimos [math] 2 [/ math] dígitos.

Por ahora, podemos centrarnos en los últimos [matemáticos] 2 [/ matemáticos] dígitos de [matemáticos] 21 ^ {128} [/ matemáticos]. Los números que terminan en [matemáticas] 1 [/ matemáticas] son ​​mucho más fáciles de manejar, nuevamente debido a la expansión. Podemos observar que los únicos términos contribuyentes en la expansión de [matemáticas] (20 + 1) ^ {128} [/ matemáticas] serán [matemáticas] ^ {128} C_ {1} 20 + 1 [/ matemáticas], que denos los últimos dígitos [matemáticos] 2 [/ matemáticos] como [matemáticos] 61 [/ matemáticos].

Ahora solo tenemos que verificar los últimos [matemáticos] 2 [/ matemáticos] dígitos de la multiplicación [matemática] 17 \ veces 61 [/ matemática] que es bastante sencillo.

Respuesta requerida = [matemáticas] 37 [/ matemáticas]

---

Puede ver más de mis respuestas sobre las preguntas restantes aquí:

Respuestas relacionadas de Kumar Pushpesh en publicaciones

Answer 3

(110 + 7) ^ 513
Si se expande arriba usando el teorema binomial, todos los términos excepto:
513C1 * 110 * (7 ^ 512) + (513C0 * 7 ^ 513) tendrán una potencia mínima de 2 para 110, por lo que son múltiplos de 100.
Término anterior = 510 * 110 * (7 ^ 512) + 3 * 110 * (7 ^ 512) + (7 ^ 513)
Al tomar mod 100, el primer término se convierte en 0, por lo que ahora necesita el resto de abajo con 100
330 * (7 ^ 512) + (7 ^ 513)
o 337 * (7 ^ 512)
Ahora, 7 ^ 512 = (7 ^ 4) ^ 108 = 2401 ^ 108 = (2400 + 1) ^ 108.
Aplicando una lógica similar a la anterior,
el resto cuando 2401 ^ 108 se divide por 100 es solo el último término de expansión binomial = 1.
Entonces, la respuesta final = 337 mod 100 = 37

Answer 4

117 ^ 513/100
Si el divisor es 100, solo encuentra los dos últimos dígitos del número
Nos preocupan solo los últimos dos dígitos del número

17 ^ 513
17 ^ 512 * 17
(17 ^ 2) ^ 256 * 17
(Xxx89) ^ 256 * 17
89 ^ 256 * 17
(89 ^ 2) ^ 128 * 17
Xxx21 ^ 128 * 17
Últimos dos dígitos de (xxxa1) ^ xxxb
= (último dígito de a * b) 1
Entonces
21 ^ 128 * 17
= 61 * 17
= xxx37
= 37 resto