Autor Tema: Residuos

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

10 Octubre, 2010, 08:13 pm
Leído 1761 veces

aura

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 534
  • Karma: +0/-0
  • Sexo: Femenino
Saludos. Les agradecere mucho si porfavor me explican como calcular este tipo de residuos.

Encontrar el residuo de \( 16^53 \) al dividir entre 7

10 Octubre, 2010, 08:40 pm
Respuesta #1

Phicar

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 513
  • Karma: +1/-0
  • Sexo: Masculino
    • redinfocol.org
Me imagino que debe ser
\( 16^{53} \mbox{ mod }7 \)

primero mira que 7 es primo..y 7 no divide a 16..

luego usando el teorema petit de fermat que dice..

\( \mbox{si p primo y p no divide a a entonces }a^{p-1} \mbox{ mod }p = 1 \)

entonces puedes expresar tu expresion como

\( 16^{7*7}*16^4 \mbox{ mod }7 \)

ahi sabras que hacer
redinfocol.org

18 Octubre, 2010, 12:18 am
Respuesta #2

aura

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 534
  • Karma: +0/-0
  • Sexo: Femenino
Lo que he intentado hacer es

\( 16^4^9\equiv{1}mod7 \)

\( 16^4^9\cdot{16^4}\Rightarrow{1\cdot{16^4}} \)

pero de aquí no se que hacer para encontrar el residuo.

18 Octubre, 2010, 02:23 am
Respuesta #3

Jorge klan

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,741
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
Hola

\( 16^4^9\equiv{1}mod7 \)

Esta igualdad no es cierta. Fermat dice

\( a^{p}\equiv a \pmod p \)

En tu caso, se tiene que \( 16^{7}\equiv 16\equiv 2 \pmod 7  \), lo cual implica que \( 16^{49}\equiv(16^{7})^{2}\equiv 2^{2}\pmod 7 \). Nota que \( 16^{53}=16^{49}\cdot 16^{4} \), también ten en cuenta que \( 16\equiv 2 \pmod 7 \), así puedes reducir un poco más tu problema


Saludos

PD: Para poner \( 16^{49} \) basta que pongas [tex]16^{49}[/tex] en vez de [tex]16^4^9[/tex]

18 Octubre, 2010, 02:59 am
Respuesta #4

aura

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 534
  • Karma: +0/-0
  • Sexo: Femenino
Hola Jorge. Gracias por tu explicación.

\( 16^{49}\equiv{4}mod(7) \) intentando concluir para calcular el residuo:

\( 16^{49}\cdot{16^{4}}=4\cdot{16^4}mod7 \) pero no entiendo como encontrar el residuo  ???

18 Octubre, 2010, 03:09 am
Respuesta #5

Jorge klan

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,741
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
Por esto dije que tuvieras en cuenta lo siguiente:

también ten en cuenta que \( 16\equiv 2 \pmod 7 \), así puedes reducir un poco más tu problema

Además, recuerda que si \( a\equiv b \pmod n \), entonces, \( a^{k}\equiv b^{k} \pmod n \) para todo \( k\in \mathbb{N} \).

Spoiler
Luego, \( 16^{4}\equiv 2^{4} \pmod 7 \)
[cerrar]


De hecho, al principio de tu ejercicio ya pudiste haber aplicado esta equivalencia (la que cito), de modo que tú ejercicio redujera un poco más su dificultad.   


Saludos

18 Octubre, 2010, 03:31 am
Respuesta #6

aura

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 534
  • Karma: +0/-0
  • Sexo: Femenino
Hola Jorge, muchas gracias.

Una molestia mas, segun yo el residuo deberia de estar entre 0,1,...,6

Pero haciendo esto \( 16^{49}\cdot{16^{4}}=4\cdot{2} \)
Entonces el residuo seria 8  ??? asi que debo estar haciendo mal algo

18 Octubre, 2010, 03:43 am
Respuesta #7

Jorge klan

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,741
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
Uffff, acabo de pasar un gol feo aquí


Citar
En tu caso, se tiene que \( 16^{7}\equiv 16\equiv 2 \pmod 7  \), lo cual implica que \( 16^{49}\equiv(16^{7})^{2}\equiv 2^{2}\pmod 7 \)

debiese ser: ... lo cual implica que \( 16^{49}\equiv(16^{7})^{\color{red}7\color{black}}\equiv 2^{\color{red}7 \color{black}}\pmod 7 \). Luego, nos queda

\( 16^{53}\equiv 16^{49}\cdot 16^{4}\equiv 2^{7}\cdot 2^{4}\equiv 2 \cdot 2\equiv 4 \pmod 7  \)

Nota que \( 2^{7}\equiv 2 \pmod 7 \), nuevamente aplicando Fermat.

En una congruencia simpre que tengas \( n>m \), existe \( k<m \) tal que  \( n\equiv k \pmod m \) (más precisamente, \( k \) es el resto al dividir \( n \) por \( m \)). En el caso en que te ubiese quedado \( 8 \), éste pudiste haberlo reducido a \( 1 \)... lo cual no ocurrió, ya que mis cálculos anteriores estaban malos

Saludos

18 Octubre, 2010, 03:54 am
Respuesta #8

aura

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 534
  • Karma: +0/-0
  • Sexo: Femenino
Muchas Gracias Jorge   :o

Una pregunta  :-[, algún lugar donde pueda checar como reducir los residuos, osea como tu me decias, reducir 8 a 1.

Y de nuevo muchas gracias Jorge 

18 Octubre, 2010, 04:25 am
Respuesta #9

Jorge klan

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,741
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino

Una pregunta  :-[, algún lugar donde pueda checar como reducir los residuos, osea como tu me decias, reducir 8 a 1.


En general, si \( n>m \), entonces existen \( q,r\in \mathbb{Z} \) tales que \( n=mq+r \), donde \( 0\leq r<m \) (algoritmo de la división o también conocido como algoritmo de Euclídes), Luego

\( n\equiv mq+r \pmod m\;\Leftrightarrow{}\;n\equiv 0+r\equiv r \pmod m \)

Ejemplos:

1) \( 15=8\cdot 1+7 \), luego \( 15\equiv 8\cdot 1+7 \pmod 8 \;\Leftrightarrow{}\;15\equiv 7 \pmod 8 \)

2) \( 352=7\cdot 50+2 \), luego  \( 352\equiv 7\cdot 50+2 \pmod 7 \;\Leftrightarrow{}\;352\equiv 2 \pmod 7 \)

Para negativos, puedes usar métodos más primitivos (algunas veces más comodos). Por ejemplo; si quiero saber a cuanto equivale -11 módulo 7 hago lo siguiente:

\( -11\equiv r\pmod7 \Leftrightarrow{} 3\equiv-11+7\cdot 2 \equiv r+7\cdot 2 \equiv r \pmod7  \). Luego, \( -11\equiv 3\pmod7 \). La idea es sumar por la menor potencia de \( 7 \)  de modo que al sumarsela a \( -11 \) el resultado sea un número positivo entre 1 y 6.

¿Se entiende?

Dejando un poco de lado la informalidad, en la web encontrarás muchos textos de teoría de números donde lo expliquen mejor (es cosa que pongas en un bucador lo que quieres)



Saludos