Autor Tema: Encuentre los dos últimos dígitos de 2^1000

0 Usuarios y 1 Visitante están viendo este tema.

20 Octubre, 2010, 02:55 pm
Leído 1506 veces

Tanius

  • Lathi
  • Mensajes: 4,649
  • Karma: +0/-0
  • Sexo: Masculino
Encuentre los dos últimos dígitos de \( 2^{1000} \).

¿Alguien podría explicarme cómo resolver este ejercicio?

Gracias  :)

20 Octubre, 2010, 03:28 pm
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 El problema equivale a el residuo \( 2^{1000} \) mod \( 100 \). Es decir encontrar \( 0\leq r<100 \) con

 \( 2^{1000}=100k+r \)

 Pero de ahí deducimos que \( r \) es múltiplo de \( 4. \) y el problema equivale a:

 \( 2^{998}=25k+r' \) con \( r'=r/4 \)

 Ahora por el Teorema de Euler:

 \( 2^{20}\equiv 1\quad mod\quad 25 \)

 Termina...

Saludos.

21 Octubre, 2010, 05:42 am
Respuesta #2

Tanius

  • Lathi
  • Mensajes: 4,649
  • Karma: +0/-0
  • Sexo: Masculino
Aunque no conocía esos teoremas de esa manera ni a la función \( \phi \) de Euler, creo que tengo claro el procedimiento que realizas, sin embargo no entiendo por qué el problema equivale a hallar el residuo de \( 2^{1000} \) mod \( 100 \).

¿Qué quiere decir \( 2^{1000} \) mod \( 100 \)? (yo sólo conocía cosas como \( x\equiv{b}  \) mod \( n \))

Pero de ahí deducimos que \( r \) es múltiplo de \( 4. \) y el problema equivale a:

 \( 2^{998}=25k+r' \) con \( r'=r/4 \)

 Ahora por el Teorema de Euler:

 \( 2^{20}\equiv 1\quad mod\quad 25 \)

No sé cómo proseguir  ??? si fueras tan amable manco.


Gracias de nuevo por todo, un saludo  :)

21 Octubre, 2010, 07:34 am
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 ¿Si no conocías los teoremas de esa manera?¿Cómo los conocías?¿Qué resultados puedes usar?.

\(  2^{1000}\quad mod\quad 100 \) es el residuo de \( 2^{1000} \) módulo \( 100 \), es decir, el resto que resulta de dividir un número por \( 100. \)

 Esto corresponde a las dos últimas cifras de un número; por ejemplo si hallamos el resto módulo\(  100 \) de \( 98423 \):

 \( 98423=984\cdot 100+23 \)

 es claro que su resto es \( 23 \).

 En cuanto a cómo proseguir, si:

\( 2^{20}\equiv 1\quad mod\quad 25 \)

 entonces trabajando módulo \( 25 \):

\(  2^{998}\equiv 2^{20\cdot 49+18}\equiv (2^{20})^{49}2^{18}\equiv 1^{49}2^{18}\equiv 2^{18} \)

 Ahora:

 \( 2^5=32\equiv 7 \)
 \( 2^{10}\equiv (2^5)^2\equiv 7^2\equiv 49\equiv 24\equiv -1 \)
 \(  2^{18}=2^{10}2^{5}2^{3}\equiv (-1)\cdot 7\cdot 8\equiv -56\equiv 19 \)

 Por tanto:

\(  2^{998}=25k+19 \)

 y finalmente el resto módulo \( 100 \) es \( 19\cdot 4=76 \).

Saludos.

21 Octubre, 2010, 07:35 am
Respuesta #4

pepito

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,625
  • Karma: +0/-0
  • Sexo: Masculino
Otra forma (muchisimo más trucha, pero que usa menos conocimientos previos) es simplemente notar que \( 2^{25}=33554432 \), o sea que podés hacer:

\( 2^{1000}=(2^{25})^{40}=33554432^{40}\equiv 32^{40}=(2^5)^{40}=2^{200}=(2^{25})^8=33554432^8\equiv \\ \equiv 32^8=(2^5)^8=2^{40}=2^{25}\times 2^{15}=33554432\times 32768\equiv 32\times 68=2176\equiv \\ \\ \equiv 76\quad \mod {100} \)
"...parecido pero nada que ver"

21 Octubre, 2010, 08:33 pm
Respuesta #5

Tanius

  • Lathi
  • Mensajes: 4,649
  • Karma: +0/-0
  • Sexo: Masculino
Muchísimas gracias manco, por tu paciencia. Y también gracias pepito, siempre es útil conocer más formas de solucionar un problema (aunque, si me permites decirlo, ocupas muchos "trucos raros" xD, pero gracias).

21 Octubre, 2010, 09:54 pm
Respuesta #6

pepito

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,625
  • Karma: +0/-0
  • Sexo: Masculino
Igual, fijate, las únicas propiedades de congruencias que usé son estas dos, muy básicas:

\( a\equiv b \mod {c}\quad\Rightarrow\quad a^n\equiv b^n\mod {c}  \) para todo exponente \( n\in\mathbb{N} \) (en la primera y segunda congruencia)

y

\( a_1\equiv a_2 \mod {c}\quad \wedge \quad b_1\equiv b_2 \mod {c}\quad\Rightarrow\quad a_1b_1\equiv a_2b_2 \mod {c} \) (en la tercera congruencia)

Después, son todas propiedades elementales de potencias.
"...parecido pero nada que ver"