Autor Tema: Aritmética Modular

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

26 Enero, 2008, 07:36 pm
Leído 3083 veces

santius

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 36
  • Karma: +0/-0
  • Sexo: Masculino
Buenas tardes, necesito saber si alguien me puede ayudar en esto, tengo exámen el jueves y estoy trancado con un tema, que debe ser sencillo, necesito saber la forma de resolver este problema:

Tengo ejercicios del tipo:

1234 ^ 500 mod 8 ?????

O sea, tengo varias cosas de este tipo para resolver, la mayoría son

x ^ y mod z

Ok, es solo notacion, no se si hay que elevar x a la y realmente, en wikipedia dice que x es congruente con y modulo z si x e y dividido z tienen el mismo resto, pero en este caso no se si es así, pòrque en Wikipedia escriben x = y mod z

Bueno! a ver si hay alguien que me salve la vida!

Saludos y gracias desde ya!
Las matemáticas no mienten, lo que hay son muchos matemáticos mentirosos.

27 Enero, 2008, 10:35 am
Respuesta #1

Luis Fuentes

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

 Calcular

 \( x^y \) mod z

 equivale a calcular el resto de dividir \( x^y  \) entre \( z \).

 Por ejemplo:

 \( 2^3=2 \) mod 3

 porque

\(  2^3=8=2\cdot 3+2 \)

 Bien, la cosa es que como hacer este cálculo de la manera más rápida. Si tenemos que hallar:

\( 1234^{500} \) mod 8

como tengamos que elevar 1234 a la 500 vamos listos.

No se que cosas sabes de aritmética modular. Desde luego la propiedad más inmediata que necesitas es esta:

 si \( x=x' \) mod z entonces \( x^y=x'^y \) mod z

 Por ejemplo en tu caso:

\(  1234=154*8+2 \)

 Luego:

 \( 1234^{500}=2^{500} \) mod 8

 Ahora puedes calcular potencias bajas del 2 modulo 8 para simplificar. En tu caso es fácil:

 \( 2^3=8=0 \) mod 8

 Luego:

 \( 1234^{500}=2^{500}=2^{3*500}*2^2=(2^3)^{500}*4=0*4=0 \) mod 8

 También para casos más complicados son útiles el Teorema de Euler   y  la función de Euler.

Saludos.

27 Enero, 2008, 04:29 pm
Respuesta #2

santius

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 36
  • Karma: +0/-0
  • Sexo: Masculino
Muchas gracias, la verdad que admirable tu respuesta, me han explicado en otros foros pero la verdad que ahora si entiendo bien.
El tema era que yo sabía que x mod y es el resto de la división entera, pero no sabía como hacer con los exponentes tan grandes que tengo, algún truco tenía que haber.
Bueno! Muchas gracias nuevamente, espero algún día poder ayudar de esa manera (Cosa difícil en esta área)...

Saludos,

Santiago
Las matemáticas no mienten, lo que hay son muchos matemáticos mentirosos.

27 Enero, 2008, 08:25 pm
Respuesta #3

santius

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 36
  • Karma: +0/-0
  • Sexo: Masculino
Buenas nuevamente,

Estoy haciendo un ejercicio nuevo,sobre este tema, y note que cosas no me quedaron claras... estoy  :banghead: desde hoy...

Bueno, tengo 4525^1200 mod 8

4525 = 565 * 8 + 4

4525^1200 = 4^1200 mod 8

Ahora, tendría que buscar potencias bajas de 4... La mas baja es 4^1

Entonces: 4^1 = 4 = 4 mod 8

Segun la solucion que puso el profesor (Solución, no resolución) el resultado sería 1 . . .

Entonces... 4 mod 8 me da 4, no 1...  ???

 Estoy trancado acá... si podés darme una mano, estaría muy agradecido...

Saludos!  ;D
Las matemáticas no mienten, lo que hay son muchos matemáticos mentirosos.

28 Enero, 2008, 05:30 am
Respuesta #4

León

  • Lathi
  • Mensajes: 903
  • Karma: +0/-0
  • Sexo: Masculino
Cita de: santius link=topic=9709.msg40353#msg40353
4525 = 565 * 8 + 4
4525 = 565 * 8 + 5