¿Cuál es el resto cuando 71 ^ 99/1000?

Answer 1

Sabemos que [matemáticas] 1000 = 10 ^ 3 = 2 ^ 3 * 5 ^ 3 [/ matemáticas]

---

[matemáticas] 71 ^ {99} \ equiv (72-1) ^ {99} \ text {(mod} 8) [/ matemáticas]

[matemáticas] 71 ^ {99} \ equiv (-1) ^ {99} \ text {(mod} 8) [/ matemáticas]

[matemáticas] 71 ^ {99} \ equiv-1 \ text {(mod} 8) [/ matemáticas]

[matemáticas] 71 ^ {99} \ equiv7 \ text {(mod} 8) [/ matemáticas]

---

[matemáticas] 71 ^ {99} \ equiv (71 * 71) ^ {49} * 71 \ text {(mod} 125) [/ matemáticas]

[matemática] 71 ^ {99} \ equiv (41) ^ {49} * 71 \ text {(mod} 125) [/ matemática]

[matemáticas] 71 ^ {99} \ equiv (41 * 41 * 41 * 41) ^ {12} * (71 * 41) \ text {(mod} 125) [/ matemáticas]

[matemáticas] 71 ^ {99} \ equiv (11) ^ {12} * (36) \ text {(mod} 125) [/ matemáticas]

[matemáticas] 71 ^ {99} \ equiv (11 * 11) ^ 6 * (36) \ text {(mod} 125) [/ matemáticas]

[matemáticas] 71 ^ {99} \ equiv (-4) ^ 6 * (36) \ text {(mod} 125) [/ matemáticas]

[matemáticas] 71 ^ {99} \ equiv 4 ^ 7 * 9 \ text {(mod} 125) [/ matemáticas]

[matemáticas] 71 ^ {99} \ equiv (2 ^ 7) * (2 ^ 7) * 9 \ text {(mod} 125) [/ matemáticas]

[matemáticas] 71 ^ {99} \ equiv 81 \ text {(mod} 125) [/ matemáticas]

---

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

[matemáticas] 2 ^ {- 3} \ equiv2 ^ {97} \ equiv (128) ^ {13} * 2 ^ 6 \ equiv3 ^ {13} 2 ^ 6 \ equiv (243) ^ 2 (1728) [/ matemáticas ]

[matemáticas] 49 * (- 22) \ equiv (-78) \ equiv47 [/ matemáticas]

[matemáticas] 2 ^ {- 3} \ equiv47 \ text {(mod} 125) [/ matemáticas]

---

[matemáticas] \ phi (8) = 4 [/ matemáticas]

[matemáticas] 5 ^ {- 3} \ equiv5 \ text {(mod} 8) [/ matemáticas]

---

[matemáticas] x [/ matemáticas] es [matemáticas] 71 ^ {99} \ mod1000 [/ matemáticas]

[matemáticas] x \ equiv7 \ text {(mod} 8) [/ matemáticas]

[matemáticas] 5 ^ {- 3} \ equiv5 \ text {(mod} 8) [/ matemáticas]

[matemáticas] x \ equiv 81 \ texto {(mod} 125) [/ matemáticas]

[matemáticas] 2 ^ {- 3} \ equiv47 \ text {(mod} 125) [/ matemáticas]

¡Ahora combine estos utilizando el Teorema del resto chino!

[matemáticas] x \ equiv \ left [(7) (5) (5 ^ 3) + (81) (47) (2 ^ 3) \ right] \ text {(mod} 2 ^ 3 * 5 ^ 3) [ /matemáticas]

[matemáticas] x \ equiv34831 \ text {(mod} 1000) [/ matemáticas]

[matemáticas] \ en caja {x \ equiv831 \ text {(mod} 1000)} [/ matemáticas]

Por lo tanto, el resto será 831

¡Espero eso ayude!

Answer 2

Sabes, Wolfram Alpha solo calculará 71 ^ 99 por ti (Computational Knowledge Engine). Entonces, si solo desea la respuesta, Quora no parece ser la forma más eficiente de obtenerla; y si quieres una explicación, ¿quizás las notas de clase serían más útiles?

Si cree que comprende la razón de la pregunta original, no dude en explicarla en los comentarios.

Answer 3

Por el teorema de Euler Totient, tenga en cuenta que 71 ^ 100 es congruente con 1 mod 250, mientras que 71 ^ 100 también es congruente con 1 mod 4.

Sea x congruente con 1 tanto para el mod 250 como para el mod 4. Por observación está claro que x = 1001 satisface este sistema de ecuaciones de congruencia.

Esto implica que 71 ^ 100 es congruente con 1001 es congruente con 1 mod 1000.

Entonces 71 ^ 99 × 71 es congruente a 1000n +1, para algún número natural n.

Tenga en cuenta que queremos encontrar una n donde 1000n + 1 sea divisible por 71.
1000 n + 1 es congruente con 6n + 1, que es divisible por 71 cuando n = 59. Entonces 71 ^ 99 × 71 es congruente con 59001 implica 71 ^ 99 es congurente con 831. Eso es el resto.