Autor Tema: División en igualdades que involucran congruencia

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

06 Abril, 2021, 08:03 pm
Leído 286 veces

Juan Miguel Barga

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 20
  • País: es
  • Karma: +0/-0
Este mensaje quiere matizar la siguiente observación:

Citar
Observación importante: La división en general no está permitida en las igualdades que involucran congruencias.

que se hace en este hilo:

https://foro.rinconmatematico.com/index.php?topic=34174.msg134826#msg134826

Ha sido separado por la administración para mayor comodidad y claridad en su lectura.



Citar
Observación importante: La división en general no está permitida en las igualdades que involucran congruencias.

Buenas tardes:  esta  observación es matizable:
investigando un tema me  he  visto en la necesidad de  resolver  \( X=(a/b) \) mod \( c \) , donde  \( a \) es muuuuy grande, y no es viable la división.

Lo he  resuelto,  con un cambio de  módulo, y seguidamente con una  descomposición de  \( a \) en varios productos,
un ejemplo fácil : \( X=12/3 \) mod \( 3\quad \Rightarrow{}X=1 \),   el cambio es el siguiente: \( (12\textsf{ mod }9)/3=1 \).
en mi caso \( a/b=((2^{52})\cdot 17+2^4)/(3^4)  \) tengo que calcular \( (a/b) \) mod \( 3 \), y el resultado es "0".
si ves esto interesante, puedes contactar y paso la demostración general.

Mensaje corregido desde la administración.

Bienvenido al foro.

Recuerda leer y seguir  las reglas del mismo así como el tutorial del LaTeX para escribir las fórmulas matemáticas correctamente.

09 Abril, 2021, 08:37 pm
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 49,030
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Este mensaje quiere matizar la siguiente observación:

Citar
Observación importante: La división en general no está permitida en las igualdades que involucran congruencias.

que se hace en este hilo:

https://foro.rinconmatematico.com/index.php?topic=34174.msg134826#msg134826

Ha sido separado por la administración para mayor comodidad y claridad en su lectura.



Citar
Observación importante: La división en general no está permitida en las igualdades que involucran congruencias.

Buenas tardes:  esta  observación es matizable:
investigando un tema me  he  visto en la necesidad de  resolver  \( X=(a/b) \) mod \( c \) , donde  \( a \) es muuuuy grande, y no es viable la división.

Lo he  resuelto,  con un cambio de  módulo, y seguidamente con una  descomposición de  \( a \) en varios productos,
un ejemplo fácil : \( X=12/3 \) mod \( 3\quad \Rightarrow{}X=1 \),   el cambio es el siguiente: \( (12\textsf{ mod }9)/3=1 \).
en mi caso \( a/b=((2^{52})\cdot 17+2^4)/(3^4)  \) tengo que calcular \( (a/b) \) mod \( 3 \), y el resultado es "0".
si ves esto interesante, puedes contactar y paso la demostración general.

A lo que se refiere la observación es que \( a/b \) no siempre está definido módulo \( k \), en cuanto a que no existe un \( x \) tal que \( xb=a \) mod \( k \).

Por ejemplo módulo \( 6 \) no existe \( x \) tal que \( 2x=5 \) mod \( 6 \). Por tanto no existe \( 5/2 \) mod \( 6 \).Sin embargo si trabajamos módulo un primo \( p \) esa división está siempre definida (siempre que el dividendo no sea cero módulo \( p \)). Por ejemplo \( 1/2 \) si está definido modulo \( 3 \). Sería \( 2 \), porque \( 2\cdot 2=1 \) mod \( 3 \).

Lo que tu planteas es interesante, pero es diferente. Y es calcular el resto de \( (a/b) \) mod \( k \), cuando \( a/b \) es un número entero y \( a,b \) son múltiplos de \( k \).

Saludos.

11 Abril, 2021, 07:59 pm
Respuesta #2

Juan Miguel Barga

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 20
  • País: es
  • Karma: +0/-0
Gracias Luis por responder:

Y si imaginásemos por un momento que  la  aritmética modular no tiene porque estar restringida a números enteros????....

en tu ejemplo: \( 1=1 \) mod \( 3=(2\cdot 1/2) \) mod \( 3=(2\cdot 1/2 mod 3) \) mod \( 3\Rightarrow \) todos estos números \( (3\cdot i-2)/2=\{1/2, 2, 7/2, 5, 13/2, 8,\ldots\} \). son congruentes con \( 1/2 \) mod \( 3 \). Y si el valor \( x \) módulo \( 3 \) esta definido como un número entre \( 0 \) y \( 3 \).  tanto lo cumple \( 1/2 \) como \( 2 \).
Y sin embargo como bien dices en \( 5/2 \) mod \( 6 \), \( (6\cdot i-1)/2=\{5/2, 17/2, 29/2\ldots \} \) no hay enteros, pero todos  esos números siguen siendo congruentes con \( 5/2 \) mod \( 6 \).

lo que hago es expresar el modulo como una serie: decir a es congruente con "\( b \) mod \( c \)" es lo mismo que decir \( a=a_i=c\cdot i-(c-b) \) \( \forall{} \) \( i \) perteneciente a \( \Bbb N \),  y viceversa, y en las series nada impide que \( c \) o \( b \) no sean enteros.

 \( x=a/b \) mod \( c \) \( \Rightarrow \)  \( x=c\cdot i-(c-a/b) \) \( \Rightarrow \) \( x=(c\cdot b\cdot i-(c\cdot b-a))/b \) \( \Rightarrow \) \( a/b \) mod \( c \) = (\( a \) mod \( (c\cdot b))/b \)

Mensaje corregido desde la administración.

12 Abril, 2021, 09:57 am
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 49,030
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Gracias Luis por responder:

Y si imaginásemos por un momento que  la  aritmética modular no tiene porque estar restringida a números enteros????....

en tu ejemplo: \( 1=1 \) mod \( 3=(2\cdot 1/2) \) mod \( 3=(2\cdot 1/2 mod 3) \) mod \( 3\Rightarrow \) todos estos números \( (3\cdot i-2)/2=\{1/2, 2, 7/2, 5, 13/2, 8,\ldots\} \). son congruentes con \( 1/2 \) mod \( 3 \).

Supongo que quisiste decir \( (3\cdot i+\color{red}1/2\color{black})=\{1/2,7/2,13/2,\ldots\} \). No es cierto que \( 2=1/2 \) mod 3.

El problema es que si tratas de extender la relación de congruencia a los racionales no funciona bien. Por ejemplo, si admitimos que \( 1/2=7/2 \) mod \( 3 \).

\( (1/2)\cdot (1/2)=(1/4) \) mod \( 3 \)

Pero:

\( (1/2)\cdot (7/2)=(7/4) \) mod \( 3 \)

Y \( (1/4)\neq (7/4) \) mod \( 3 \).

Saludos.

17 Abril, 2021, 01:26 am
Respuesta #4

Juan Miguel Barga

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 20
  • País: es
  • Karma: +0/-0
Por favor, de manera teórica , como se resolvería la ecuación:

\( (X+a)/b \) congruente con \( d \) mod \( c \),  donde \( a,b,c,d \) y \( X \) son enteros.  ¿Cuáles serían los valores de  \( X \), expresados como un módulo?

Gracias.

19 Abril, 2021, 08:22 pm
Respuesta #5

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 49,030
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Por favor, de manera teórica , como se resolvería la ecuación:

\( (X+a)/b \) congruente con \( d \) mod \( c \),  donde \( a,b,c,d \) y \( X \) son enteros.  ¿Cuáles serían los valores de  \( X \), expresados como un módulo?

¿Exactamente qué estás entendiendo que \( (X+a)/b \) congruente con \( d \) mod \( c \)?. ¿Esto:

\( X+a=bd \) mod \( c \) ?

Sospecho que otra cosa pero no me queda claro que. Pon uno o varios ejemplos.

Saludos.

22 Abril, 2021, 07:32 pm
Respuesta #6

Juan Miguel Barga

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 20
  • País: es
  • Karma: +0/-0
No, no es eso, intento expresarlo más claramente:

Por ejemplo:

X congruente con 2 mod 3,\( (X\equiv{} 2 \) mod 3\( ) \) significa que  X mod 3=2, con lo que \( X=3*i +2 = \) {2,5,8,11......}

Si decimos:  \( (X+1)/2 \) congruente con \( 1 \) mod \( 3 \), significa que \( ((X+1)/2) \) mod 3 = 1 \( \Rightarrow{} X= \){1,7,13,.....}

(Evidentemente no es lo mismo que \( (X+1) \) = \( 1\cdot{}2 \) mod \( 3 \) donde  X={1,5,7,10,13....})

La pregunta es, entonces, como se resuelve \( (X+a)/b \) mod \( c=d \)
     

         

23 Abril, 2021, 09:32 am
Respuesta #7

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 49,030
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

No, no es eso, intento expresarlo más claramente:

Por ejemplo:

X congruente con 2 mod 3,\( (X\equiv{} 2 \) mod 3\( ) \) significa que  X mod 3=2, con lo que \( X=3*i +2 = \) {2,5,8,11......}

Si decimos:  \( (X+1)/2 \) congruente con \( 1 \) mod \( 3 \), significa que \( ((X+1)/2) \) mod 3 = 1 \( \Rightarrow{} X= \){1,7,13,.....}

(Evidentemente no es lo mismo que \( (X+1) \) = \( 1\cdot{}2 \) mod \( 3 \) donde  X={1,5,7,10,13....})

La pregunta es, entonces, como se resuelve     

Pues con esa interpretación simplemente:

\( (X+a)/b \) mod \( c=d \)   equivale a \( \dfrac{X+a}{b}=d+kc \)

de donde:

\( X=b(d+kc)-a \) para \( k\in \Bbb Z \)

Saludos.

23 Abril, 2021, 06:40 pm
Respuesta #8

Juan Miguel Barga

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 20
  • País: es
  • Karma: +0/-0
¡¡¡¡¡ Exacto ¡¡¡¡

\( a/b \) mod \( c=d \)   equivale a:  \( \dfrac{a}{b}=d+kc \)

Y del mismo modo que hemos pasado de un módulo a una serie, podemos pasar de una serie a un módulo.

\( \dfrac{a}{b}=d+kc\Rightarrow{} \) \( a=b(d+kc)=bd+cbk \)   equivale a: \( a \) mod \( cb=bd\Rightarrow{} \) (\( a \) mod \( cb)/b=d\Rightarrow{} \)

\( a/b \) mod \( c=(a \) mod \( cb)/b \)
 
Que es la formula con la que iniciábamos este hilo..  que podrá utilizarse  cuando por algún motivo no sea posible realizar la división a/b

Gracias y un cordial saludos.

23 Abril, 2021, 07:00 pm
Respuesta #9

feriva

  • $$\Large \color{#a53f54}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 9,642
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino

Y del mismo modo que hemos pasado de un módulo a una serie, podemos pasa de una serie a un módulo.

\( \dfrac{a}{b}=d+kc\Rightarrow{} \) \( a=b(d+kc)=bd+cbk \)   equivale a: \( a \) mod \( cb=bd\Rightarrow{} \) (\( a \) mod \( cb)/b=d\Rightarrow{} \)

\( a/b \) mod \( c=(a \) mod \( cb)/b \)
 
Que es la formula con la que iniciábamos este hilo..  que podrá utilizarse  cuando por algún motivo no sea posible realizar la división a/b


Pero no entiendo muy bien el objetivo (perdona que intervenga, es que me gustan estas cosas).

...

Fíjate en esta respuesta que te escribió Luis; que da la sensación de haber pasado un poco desapercibida.

https://foro.rinconmatematico.com/index.php?topic=116414.msg465530#msg465530

Los restos tienen que ser (son) equivalentes entre ellos respecto de un mismo módulo (quiero decir los representantes de los mismos restos 1,7, 13..., son equivalentes todos entre ellos módulo 6)

Saludos.