Autor Tema: Problema con identidad de Bezout y aritmetica modular

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

02 Febrero, 2011, 05:40 pm
Leído 2584 veces

JesusMax

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 9
  • Karma: +0/-0
  • Sexo: Masculino
Ando aqui estudiando aritmetica entera-modular y me he quedado atascado en un punto, así que me he animado a entrar en este foro y preguntaros a vosotros  :D.

El problema es el siguiente: Estoy intentando encontrar el inversor de 5 en Z12 y para ello se que lo primero es que mediante el algoritmo de Euclides tengo que hallar la identidad de Bezout, lo hago y veo que me da:

12×2 - 5×5 = 1

Bien, es aqui donde viene el problema. "Se" que esto da la congruencia  5×5 ≡ 1 (mod 12) ,pero porque da esa congruencia? que es lo que hay que hacer para llegar a esa conclusion? ¿que tendria que hacer a continuacion?

Esto que acabo es hacer es siempre igual, es decir, si me dicen hallar el inversor de 9 en Z30, es lo mismo? o no siempre es el mismo metodo para hallar el inverso?

Muchas gracias  :).

02 Febrero, 2011, 08:03 pm
Respuesta #1

Teón

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,369
  • Karma: +0/-0
  • Sexo: Masculino
  • C:.J:.T:.
Hola.

En realidad es:

\( 5\times 5 -2\times 12=1 \)

De donde tenemos

\( 5\times 5=2\times 12+1 \)

En consecuencia

\( 5\times 5\equiv 1 \mod 12 \) es decir el resto de dividir 25 por 12 es 1.

La conclusión de esto es que 5 es inverso de 5 módulo 12.
Saludos.
Eram quod es, eris quod sum.

02 Febrero, 2011, 08:05 pm
Respuesta #2

Héctor Manuel

  • Lathi
  • Mensajes: 3,701
  • País: mx
  • Karma: +0/-0
  • Sexo: Masculino
Hola JesusMax.  Bienvenido al foro.

Tienes un error: no es 12x2-5x5=1; es 5x5-12x2=1.

Ahora bien.  Lo anterior se reescribe como \( 5\cdot 5-1=12\cdot 2 \).  Por definición, esto significa que \( 12|5\cdot5-1 \), que también por definición, significa que \( 5\cdot5-1\equiv0(mod12) \), o equivalentemente ("pasando el 1 del otro lado sumando", como en las ecuaciones) esto se puede expresar como \( 5\cdot 5\equiv1(mod12) \).

En general, si tienes la combinación lineal \( ax+by=1 \), tendrás, repitiendo un proceso análogo al que acabo de describir, que \( ax\equiv 1(modb) \).

En cuanto a lo que preguntas sobre si el método es el mismo siempre, no conozco algún otro.  Sin embargo, en la práctica tampoco es un gran método, ya que involucra el hallar una expresión del tipo \( ax+by=1 \) y eso significa hacer muchas cuentas.

Normalmente lo que se hace es hallar los inversos al tanteo.

Saludos.

Teón se adelantó  ;D

02 Febrero, 2011, 08:09 pm
Respuesta #3

Teón

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,369
  • Karma: +0/-0
  • Sexo: Masculino
  • C:.J:.T:.
Hola.


Normalmente lo que se hace es hallar los inversos al tanteo.


En realidad para llegar al inverso modular, se lo hace mediante el algoritmo de Euclides, que es muy económico ya que no presupone el conocimiento de los factores de los números involucrados.

Saludos.
Eram quod es, eris quod sum.

02 Febrero, 2011, 08:26 pm
Respuesta #4

Héctor Manuel

  • Lathi
  • Mensajes: 3,701
  • País: mx
  • Karma: +0/-0
  • Sexo: Masculino

En realidad para llegar al inverso modular, se lo hace mediante el algoritmo de Euclides, que es muy económico ya que no presupone el conocimiento de los factores de los números involucrados.


Si.  Pero para números grandes este mismo algoritmo se vuelve tedioso.

Saludos.

03 Febrero, 2011, 11:00 am
Respuesta #5

JesusMax

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 9
  • Karma: +0/-0
  • Sexo: Masculino
Muchas gracias¡, la verdad, ayer al final consegui sacarlo pero no entendia bien como llegaba a ese punto, con vosotros ya lo entendi perfectamente  ;).

Una ultima cosa, vi por algun lado que para que existe un inverso por ejemplo de:  a en Zb, a y b deben ser coprimos no?

03 Febrero, 2011, 11:29 am
Respuesta #6

Teón

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,369
  • Karma: +0/-0
  • Sexo: Masculino
  • C:.J:.T:.
Hola.


Una ultima cosa, vi por algun lado que para que existe un inverso por ejemplo de:  a en Zb, a y b deben ser coprimos no?

Correcto.

Saludos.
Eram quod es, eris quod sum.