[R_Gauss]

Buen día,

Estoy realizando unos ejercicios propuestos sobre clases de equivalente, dice así:

1. Encuentre la clase de equivalencia de \( n \) en \( \mathbb{Z}_m \) con  \( n=-584 \) y \( m=191 \).

Lo que hice fue sacar el MCD(584,191}=1, pero no sé cómo podría proseguir para encontrar dicha clase. ¿Se podría aplicar el Teorema de Euler o el pequeño Teorema de Fermat? ¿Cómo podría aplicarlo?


2. Encuentre \( [101]^{-1} \) en \( \mathbb{Z}_{191} \) ¿Tiene sentido \( [101^{-1}]? \)


Agradezco sus colaboraciones,

saludos,

[Masacroso]

1. La clase de equivalencia de un \( n \) en \( \Bbb Z_m \) es la que se suele representar por \( n\bmod m \), es decir, el menor resto positivo (entero) al dividir por 191.

Al obtener un resto negativo \( r \) entonces el menor resto positivo de esa clase de equivalencia viene dado por \( m+r \).

NOTA: aquí estoy tomando los representantes de las clases de equivalencia dados por los menores restos positivos, es decir por los números del \( 1 \) al \( m \). Los representantes de una clase de equivalencia pueden ser tomados de cualquier otro modo. De hecho la clase de equivalencia de un \( n \) en \( \Bbb Z_m \) se puede simbolizar por \( [n] \), y está formada por todos los \( s\in\Bbb Z \) que tienen la forma \( s=n+k m \) para todo \( k\in\Bbb Z \), o expresado de otro modo: \( [n]=n+m\Bbb Z \).

[manooooh]

Hola

2. Encuentre \( [101]^{-1} \) en \( \mathbb{Z}_{191} \) ¿Tiene sentido \( [101^{-1}]? \)

Entiendo que \( [101^{-1}]=[\frac1{101}] \).

¿Existe la clase de equivalencia de una fracción? Sí, por ejemplo, como

\( 2\cdot4\equiv1\quad3\cdot3\equiv2\quad6\cdot6\equiv1\pmod7, \)

luego

\( \displaystyle\frac12\equiv4\;(\text o\;\frac14\equiv2)\quad\frac23\equiv3\quad\frac16\equiv6\pmod7. \)

Sin embargo, \( 101 \) es primo, por lo que sus divisores son únicamente \( 1 \) y él mismo. Por tanto no tiene sentido calcular \( [101^{-1}]_{191} \).

Para \( [101]^{-1} \) supongo que será el inverso (simétrico) de \( 101 \) en \( \Bbb Z_{191} \), pero no estoy seguro. Esperá a alguien más.

Saludos

P.D. Es recomendable que nos muestres tus intentos para poder corregirte y no lanzar ideas propias, para ayudarte mejor.

[feriva]

Agradezco sus colaboraciones,

Yo entiendo esto.

\( -584\equiv c\,(191)\Rightarrow191|(-584-c)
  \)

\( c=180
  \)

180 sería una respuesta posible tomando "c" como resto; pero también podemos tomar c como un negativo, que es donde yo dudo; a lo mejor estoy interpretando mal quién es "n".

O sea, nos situamos 158 unidades a la izquierda de cero; la pregunta es, ¿cuántas unidades hay que contar hasta llegar a un múltiplo de 191? Pues hay dos posibilidades, según se cuente a la derecha o a la izquierda.

Supongo que lo normal es considerar el resto propiamente dicho, o sea, el valor positivo de la equivalencia (además lo nombra con la letra "n", lo cual no es definitivo pero suele indicar un natural). Esto último no, que me estaba confundiendo bailando las letras en la cabeza sin releer el enunciado, "n" lo define como negativo precisamente

Saludos.

[Luis Fuentes]

Hola

Entiendo que \( [101^{-1}]=[\frac1{101}] \).

¿Existe la clase de equivalencia de una fracción? Sí, por ejemplo, como

\( 2\cdot4\equiv1\quad3\cdot3\equiv2\quad6\cdot6\equiv1\pmod7, \)

luego

\( \displaystyle\frac12\equiv4\;(\text o\;\frac14\equiv2)\quad\frac23\equiv3\quad\frac16\equiv6\pmod7. \)

No, no está bien. La relación de equivalencia "módulo \( n \)" en principio se define en los enteros. Y en todo caso si se extiende a los racionales (e incluso a los reales) sería:

\( x\equiv y\mod\,n\quad \Leftrightarrow{}\quad x-y=kn \) para \( k \) entero

y no sería cierto por ejemplo que \( \dfrac{1}{2}\equiv 4 \) mod \( 7 \)

Para \( [101]^{-1} \) supongo que será el inverso (simétrico) de \( 101 \) en \( \Bbb Z_{191} \), pero no estoy seguro. Esperá a alguien más.

Si; se tendría que \( [101]^{-1}= [m] \) en \( \mathbb{Z}_{191} \) si se cumple que \( 101m\equiv 1\mod 191 \) es decir si existe un entero \( k \) tal que:

\( 101m-1=191k \)  (*)

La ecuación tiene solución si y sólo si \( 101 \) es coprimo con \( 191 \); en general un elemento \( [ x] \) tiene inverso en \( \mathbb{Z}_n \) si y sólo si \( x \) y \( n \) son coprimos.

El procedimiento para resolver una ecuación diofántica lineal como (*) está explicado aquí:

http://rinconmatematico.com/foros/index.php?topic=26781.0

Saludos.

[R_Gauss]

Hola, gracias por sus respuestas:

Respecto al primer punto,

Buen día,

Estoy realizando unos ejercicios propuestos sobre clases de equivalente, dice así:

1. Encuentre la clase de equivalencia de \( n \) en \( \mathbb{Z}_m \) con  \( n=-584 \) y \( m=191 \).

Lo que hice fue sacar el MCD(584,191}=1, pero no sé cómo podría proseguir para encontrar dicha clase. ¿Se podría aplicar el Teorema de Euler o el pequeño Teorema de Fermat? ¿Cómo podría aplicarlo?

Lo que comprendo es que al aplicar el algoritmo de la división el residuo es el correspondiente a la clase de equivalencia, es decir:
\( 584 = 191*3+11 \) luego, la clase de equivalencia de \( n=-584 \) en \( \mathbb{Z}_m \)  es \( [11] \) ¿Es correcto?

2. Encuentre \( [101]^{-1} \) en \( \mathbb{Z}_{191} \) ¿Tiene sentido \( [101^{-1}]? \)

En este punto, ¿solo bastaría con resolver la ecuación diofántica lineal?, es decir:

\( 101m−191k=1 \) 

Al aplicar el algoritmo de Euclides y encontrar \( m=87 \) y \( k=46 \) una solución particular de \( (m_0,k_0)=(87,46) \) ¿Qué significa ello?



Saludos,

[manooooh]

Hola

Entiendo que \( [101^{-1}]=[\frac1{101}] \).

¿Existe la clase de equivalencia de una fracción? Sí, por ejemplo, como

\( 2\cdot4\equiv1\quad3\cdot3\equiv2\quad6\cdot6\equiv1\pmod7, \)

luego

\( \displaystyle\frac12\equiv4\;(\text o\;\frac14\equiv2)\quad\frac23\equiv3\quad\frac16\equiv6\pmod7. \)

No, no está bien. La relación de equivalencia "módulo \( n \)" en principio se define en los enteros. Y en todo caso si se extiende a los racionales (e incluso a los reales) sería:

\( x\equiv y\mod\,n\quad \Leftrightarrow{}\quad x-y=kn \) para \( k \) entero

y no sería cierto por ejemplo que \( \dfrac{1}{2}\equiv 4 \) mod \( 7 \)

¡Gracias Luis! En realidad lo leí de la wiki de Wolfram, ni yo nunca había trabajado con clases fraccionarias . Perdón por la confusión.

Lo que comprendo es que al aplicar el algoritmo de la división el residuo es el correspondiente a la clase de equivalencia, es decir:
\( 584 = 191*3+11 \) luego, la clase de equivalencia de \( n=-584 \) en \( \mathbb{Z}_m \)  es \( [11] \) ¿Es correcto?

No. Masacroso (*) y feriva lo expusieron claramente:

Al obtener un resto negativo \( r \) entonces el menor resto positivo de esa clase de equivalencia viene dado por \( m+r \).

\( -584\equiv c\,(191)\Rightarrow191|(-584-c)
  \)

\( c=180
  \)

La clase de \( [-584]_{191}=[191]-[11]=[180] \).

En este punto, ¿solo bastaría con resolver la ecuación diofántica lineal?, es decir:

\( 101m−191k=1 \) 

Al aplicar el algoritmo de Euclides y encontrar \( m=87 \) y \( k=46 \) una solución particular de \( (m_0,k_0)=(87,46) \) (...)

Sí, debés resolver la ecuación como Luis indicó aquí:

Se tendría que \( [101]^{-1}= [m] \) en \( \mathbb{Z}_{191} \) si se cumple que \( 101m\equiv 1\mod 191 \) es decir si existe un entero \( k \) tal que:

\( 101m-1=191k \)  (*)

La ecuación tiene solución si y sólo si \( 101 \) es coprimo con \( 191 \); en general un elemento \( [ x] \) tiene inverso en \( \mathbb{Z}_n \) si y sólo si \( x \) y \( n \) son coprimos.

El procedimiento para resolver una ecuación diofántica lineal como (*) está explicado aquí:

http://rinconmatematico.com/foros/index.php?topic=26781.0

(...) ¿Qué significa ello?

Pues... que \( m=87 \) es ¿una? solución (la \( k \) no te interesa) . Lo de "una solución" y no "la solución" no estoy seguro, esperá a alguien más.

Saludos


(*) No sé si se quería referir a \( m-r \), pues el resto siempre es positivo, y estaríamos sumando \( [191]+[11] \) en vez de \( [191]-[11] \) .

[Luis Fuentes]

Hola

Pues... que \( m=87 \) es ¿una? solución (la \( k \) no te interesa) . Lo de "una solución" y no "la solución" no estoy seguro, esperá a alguien más.

El inverso si existe es único, asi que es "la solución". En concreto lo que se deduce es que \( [101]^{-1}=[87] \). Igualmente sería correcto poner:

\( [101]^{-1}=[87]=[87+191]=[87+2\cdot 191]=\ldots \)

Porque una misma clase en \( Z_{191} \) puede denotarse por varios representantes ( y esto tiene que ver con el primer apartado). Lo que ocurre es que suele prefrerise en \( Z_n \) dar un representante \( [k ] \) de la clase en el intervalo \( 0\leq k<n \).

Saludos.

[feriva]

\( -584\equiv c\,(191)\Rightarrow191|(-584-c)
  \)

\( c=180
  \)

La clase de \( [-584]_{191}=[191]-[11]=[180] \).

Gracias por la confirmación, manooooh.

No tenía seguridad porque no sabía si se podrían considerar clases de equivalencias negativas, además de las de los restos tal cual se entienden, que de ésas sí sabía.

Saludos.

[feriva]

Al aplicar el algoritmo de Euclides y encontrar \( m=87 \) y \( k=46 \) una solución particular de \( (m_0,k_0)=(87,46) \) ¿Qué significa ello?

Con un ejemplo con números pequeños lo puedes ver bien

Pongamos que dividmos 23 entre 5, el resto es 3 y entonces escribimos

\( 23=4\cdot5+3
  \)

Lo cual puede expresar expresa así

\( 23\equiv3(mod\,5)
  \)

Donde 23 es, digamos, el dividendo, 3 es el resto que resulta de dividir 23 entre 5 y 5 es el “divisor”, el módulo (la palabra divisor se reserva en estas cuestiones para cuando el módulo divide exactamente dejando resto cero, de ahí las comillas).

Al escribirlo de esta forma, en vez de ésta \( 23=4\cdot5+3
  \), no aparece el 4; esa es la principal diferencia; porque no nos importa tanto tratar con el cuarto múltiplo de 5 ni ninguno en particular, nos basta con indicar que es un múltiplo, el que sea, del módulo.

Ahora, el inverso multiplicativo es un número tal que mutliplicado por el resto se tranforma en resto 1; pero hay que multiplicar 23 también por el inverso en la equivalencia, hay que multiplicar a ambos lados para que se mantenga ésta:

Si llamamos x al inverso, por ejemplo, queda

\( 23x\equiv3x\,(mod\,5)
  \)

tal que al hacer el producto 3x=1, es esto

\( 23x\equiv1\,(mod\,5)
  \)

Y no sabemos cuál es hasta que no se resuelve la ecuación.

Luego si volvemos a esta expresión, \( 23=4\cdot5+3
  \), vemos que lo que buscamos resolver es la ecuación diofántica \( 23x=5y+1
  \); el 4 ha cambiado por la “y”, porque ahora tendrá que ser otro número, claro.

Las soluciones son x=5k+2; y=23k+9.

Si pruebas haciendo k=1, entonces x=7 y puedes probar que aquí

\( 23x\equiv1\,(mod\,5)
  \) tienes que si divides \( 23\cdot7=161
  \) entre 5, deja, en efecto, resto 1; lo cual es inmediato de ver pues trivialmente se observa que 160 es múltiplo de 5; luego 161 es un múltiplo de 5 más 1.

Saludos.