La solución para los dos últimos dígitos de un gran número de $3^{1000}$?

Question

He encontrado esta pregunta a encontrar los dos últimos dígitos de $3^{1000}$ de mis profesores en edad de notas y de revisión de las guías.

¿De qué material debo saber para resolver este tipo de problemas con los restos.Sé Wilson del Teorema y se menciona en este paquete de el Teorema de Euler. Iba yo a ver en que para ser capaz de resolver problemas como este? ¿Por qué podemos resolver problemas como este.

En resumen, me decidí a buscar un poco por delante y, mientras tanto, fresco consejos y sugerencias sería ideal para esta área de futuro tipo de material', que será cubierto.

Answer 1

No hay casi seguramente una mejor manera, pero en la parte superior de mi cabeza así es como yo lo haría. Encontrar los dos últimos dígitos de $3^{1000}$ es equivalente al cálculo de $3^{1000}\mod100$. Como $3^5=243$ tenemos que $3^5=43\mod100$. Del mismo modo se puede comprobar que el $43^2=49\mod100$, y, a continuación,$49^2=1\mod100$. Por lo tanto, tenemos que $3^{20}=1\mod100$. Elevando ambos lados al poder de la $50$, llegamos a la conclusión de que $3^{1000}=1\mod100$, es decir, los dos últimos dígitos de $3^{1000}$$01$.

Answer 2

Yo acababa de empezar a multiplicar y a ver qué pasa con los dos últimos dígitos; son ciertas para el ciclo en torno a algún punto:

3,9,27,81,43,29,87,61,83,49,47,41,23,69,07,21,63,89,67,01,03,09,27,...

Sí, ahí está ... y lo vemos ciclos con una longitud de ciclo de 20, y desde el 20 es 01, el 1000 será 01 así.

Pero, por supuesto, eso es bastante tonto método ... no sé cualquier método más avanzado.

Answer 3

Utilizando la función de Euler obtendrá phi(100)= 40

                   3^40 = 1 (mod 100).

Desde el 1000 = 40 x 25... a partir de ahí, usted puede sacar su propia conclusión.

Answer 4

Uno podría aplicar el teorema del binomio aquí: $$ 3^{1000} = 9^{500} = (10-1)^{500} = \sum_{k=0}^{500} {500 \elija k}10^k (-1)^{500-k} $$ La tercera igualdad se sigue del teorema del binomio. Todos los poderes de $10^k$ modulo $100$ desaparecen cuando se $k >= 2$. Así, sólo los dos primeros términos de la suma son: $$ 3^{1000} \pmod {100} \equiv (10^0 (-1)^{500} + 10^1 (-1)^{499} \ 500) \pmod {100} \equiv 1 \pmod {100} $$